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.
Rule 1 (S, R) And S <7 à (7, r) 7 kg bottle dissatisfied filling 2 (s, r) and r <3 à (s, 3) 3 kg bottle dissatisfaction filling 3 (S, r) and S> 0 à (0, r) 7 kg of bottles, empty 4 (s, r) and r> 0 à (s, 0) 3 kg bottle is empty 5 (s , R) and S> 0 and S R ≤ 3à (0, s r) 7 kg bottle in the oil into 3 kg bottle 6 (s, r) and r> 0 and s r ≤7à (S R 0) 3 kg in the bottle, the oil is poured into 7 kg of bottles 7 (S, R) and S <7 and S R ≥7 à (7, S R -7) with 3 kg bottle oil to 7 pounds 8 ( S, r) and r <3 and S r ≥ 3 ≥ (S R-3, 3) with 7 kg bottle oil to load 3 pounds
Third, 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 of the program: Bottle class, used to describe the status of the bottle and some behaviors 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; // The total capacity of the bottle int current = 0; // The amount of oil in the current bottle int Remain = 0; // The remaining amount in the bottle
// Pour the behavior action of the oil PUBLIC VOID ADD (INT VAL) {Current = Val; Remain - = Val;}
// Behavior of Pour Oil 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) // Determine whether to reach the target status {int Random = R.Next (1, 7); // Random with randomly generated number to determine the next one Child state
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 (UnvisIndbttsarr.count> = 0) // If there is no access table, if a knot continues loop search, {TREENODE N = (Treenode) UnvisIndbttsarr [0]; BOOL flag = true;
// Check if Foreach (Treenode I in HaveVisitedbttsarr) {if (i.text.equals (n.text)) {havevisitedbttsarr.add (unvisitedbttsarr [0]); unvisitedbttsarr.removeat (0); Flag = false; Break;}} // If you have traversed, you don't 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 (BottleState ()); UNVITEDBTTSARR.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;} }
