Gross oil problem
-,Problem Description
Substrate Problem: Two children go to oil, one person brought a jade bottle and another with a seven or two or two empty bottles. Originally planned to play a pound of oil, but because the money belled is not enough, I have to combat a pound of oil, on the way home, two people want to score this pound of oil, but there is no other tool. It is now only used to accurately divide two half pounds of oil in this three bottles (one pounds, seven, three or three two).
Second, the algorithm description
F algorithm selection
By analyzing the characteristics of the topic and combined with depth priority, breadth priority and iterative deepening the characteristics of the algorithm and the disadvantage, here is the extensive priority algorithm to solve the oil problem. If a depth priority algorithm is used, since its blindness causes a search to fall into a local trap, it is not necessarily possible that it is not necessarily an optimal solution that is not necessarily an optimum solution, and thus this algorithm is not used. The iterative deepening search is a strategy for depth and wide search in a fixed depth to search, so that the single depth search cannot obtain the disadvantage, but finding is not necessarily the optimal solution. Singapore prioritizes to sacrifice the space cost and time cost in exchange for optimal solution. Since this problem is not complicated, even if the breadth priority algorithm does not have too many space and time, in order to obtain the optimal solution here, select a broad-scale priority algorithm to solve.
F algorithm description
1. Use unvisitedbttsarr to indicate the list of initial nodes (to be expanded, this is a dynamic array)
2. If unvisitedbttsarr is empty set, exit and give failed signals
3. N is taken as the first node of UnvisitedBTTSARR, and delete node n in UnvisIndbttsarr, put it in the list of access nodes HaveVisitedbttsarr
4. If n is the target node, exit and give a successful signal
5. Otherwise, add N the child node to the end of N, and return 2) step
F problem analysis
l Selecting a suitable data structure representation status
F is indicated by vector (T, S, R) state -t represents the amount of oil in the two bottles, and s represents the amount of oil in the two bottles, and R represents the amount of oil in the two bottles.
F problem start state: (10, 0, 0).
F problem Target state: (5, 2, 3) or (5, 3, 2) or (5, 5, 0).
l Determine the intelligent operator to indicate the rules of the change state. Since the total amount of oil is 10 two, and the 10 two bottles can be filled with all the oil, so the 10 two bottles can be used as a large oil barrel, so that this question is to be a problem with the previous question 8/6 . Therefore, only the state of the 7, 3 bottles is given when the change is described, and the state of 10 bottles is 10-S-R. However, due to the consistency on the program processing, I still handle 10, 8, 6 bottle of 10, 8, 6 in the implementation of the program, rather than in two states.
number
rule
Explanation
1
(S, r) and s <7 à (7, r)
7 pounds bottle is full
2
(S, R) And R <3 à (s, 3)
3 kg of bottles are filled
3
(S, r) and s> 0 à (0, r)
7 pounds of bottles empty
4
(S, r) and r> 0 à (s, 0)
3 kg of bottles are empty
5
(S, r) and s> 0 and s r ≤3à (0, s r)
7 pounds in the bottle in the oil into 3 kg bottles
6
(S, r) and r> 0 and s r ≤7à (S R, 0)
3 pounds in the bottle, pour the 7 kg bottle
Seduce
(S, r) and s <7 and s r ≥7 à (7, S R -7)
3 kg bottle oil is filled with 7 pounds
8
(S, R) AND R <3 and S R ≥ 3 à (S R-3, 3)
Use 7 kg bottles of oil to 3 pounds of bottles, program design
The algorithm is implemented using the C # language. The procedure is mainly implemented in accordance with the description of the breadth priority algorithm provided above. There are four classes in the program:
Bottle class, used to describe the status of the bottle and some behavior and attributes.
WidthSearch class, is a class of breadth priority search algorithms
The DEPTHSEARCH class is the implementation class of depth priority search algorithm.
The mainform class is a class of interface design.
The implementation of two algorithms here is mainly for a contrast.
The following mainly describes the program implementation of several core algorithms.
/ / Bottle
Public Class Bottle
{
INT CAPABILITY = 0; // Total capacity of bottles
INT Current = 0; // The amount of oil in the current bottle
INT remain = 0; // The amount remaining in the bottle
// Pour the behavior action
Public void add (int val)
{
Current = Val;
REMAIN - = VAL;
}
// Put out the behavior action
Public Void Sub (INT VAL)
{
Current - = VAL;
REMAIN = VAL;
}
// Depth priority algorithm implementation
Public Class DepthSearch
Public void searching ()
{
Random r = new random ();
While (bottle_10.currentval! = 5) // Judgment to achieve the target status
{
INT random = r.next (1, 7); // Randomly determine the next sub-state with random number
Switch (Random)
{
Case 1:
FlowTo (Bottle_03, Bottle_07);
Break;
Case 2:
FlowTo (Bottle_10, Bottle_03);
Break;
Case 3:
FlowTo (Bottle_07, Bottle_03);
Break;
Case 4:
FlowTo (Bottle_10, Bottle_07);
Break;
Case 5:
FlowTo (Bottle_03, Bottle_10);
Break;
Case 6:
FlowTo (Bottle_07, Bottle_10);
Break;
DEFAULT:
Break;
}
IF (! Statearr.Contains))))
{
Statearr.Add (BottleSstate ());
}
Else
{
ReturntopRestate ();
}
}
}
// Follow the action. Here is from Bottle1 to Bottle2
Private Void Flowto (Bottle Bottle1, Bottle Bottle2)
{
IF (Bottle1.currentVal> bottle2.remainval)
{
Bottle1.sub (bottle2.remainval);
Bottle2.currentval = Bottle2.capabilityVal;
}
Else
{
Bottle2.add (Bottle1.currentVal);
Bottle1.currentVal = 0;
}
}
// Scenary priority search implementation class
Public Class WidthSearch
Public void s (Treenode Node)
{
While (unvisitedbttsarr.count> = 0) // In the unsuccessful table, if a node continues loop search, otherwise jump out
{
Treenode n = (Treenode) unvisitedbttsarr [0];
Bool flag = true;
/ / Check if you have visited
Foreach (Treenode I in Havevisitedbttsarr) {
I.Text.Equals (n.text))
{
Havevisitedbttsarr.add (unvisitedbttsarr [0]);
Unvisitedbttsarr.removeat (0);
Flag = false;
Break;
}
}
// If you have traversed it, you need to continue traverse to the next
IF (Flag)
{
IF (Search (n))
{
Return;
}
}
}
}
// Create a sub-node and join in UnvisIndbttsarr.
Private Bool Createnode (Treenode Node)
{
Treenode n = new Treenode (BottleSstate ());
UnvisitedBTTSARR.Add (n);
IF (bottle_10.currentval == 5)
{
Node.Nodes.Add (n);
SetPath (n);
Return True;
}
Node.Nodes.Add (n);
Return False;
}
// Retrieving the best path
Private void setpath (Treenode N)
{
While (n.parent! = null)
{
Path = n.text "->" path;
n.forecolor = system.drawing.color.blue;
N = n.parent;
}
}
Fourth, test results
The following is the test results:
1) Search path for depth priority random generating sub-nodes
2) Exception of Guangsian priority algorithm
From the above two results, if there is a solziness, the broadness can always find the best solution, but from time to see the depth priority and breadth priority needs to traverse each node, the time space is more cost-effective, so time There is a lot of affirmation. But you can guarantee the best solution. This problem is much simpler, the complexity is not high, only the best solution is found in the ninth step, so the depth is preferred, but if it is in some complex issues, this algorithm may lead to a combination explosion. The occupancy space is too large to cause the algorithm.
Please give a point. Email of the source program gives me, the code is not optimized.
