Methodology

The program solves this puzzle using three test cases: 1) three chickens and wolves, 2) eleven chickens and ten wolves, and 3) one-hundred chickens and ninety-five wolves. The search methods used are Breadth First Search (BFS), Depth First Search (DFS), and Iterative Deepening Depth First Search (IDDFS). The program also records the runtime of each method for each problem.

BFS

• Parameters (Initial state, Goal state, output file, temp [ ], solution).
• The algorithm is a loop that stops once the first solution is found.
• It pops out the first node in temp[ ] (the first node placed in temp[ ] is the root node that holds the Initial state), and this node is put through a function that consists of many "if" statements, each representing the different actions that could be done in the puzzle. Every time there is a valid action, a new node, representing the changed state, is created.
• The program then checks to see if the state was already repeated by checking the state of its parent, its parent’s parent, and so forth.
• If the state is a repeat, it is ignored. Otherwise, it is checked to see if the goal state is achieved. If yes, the action is added to the solution and outputted along with the parents that led up to it.
• If the node is not a repeat, but also not the solution, then it is considered a child node and placed in temp[ ].
• Temp[ ] list is ordered from oldest to newest nodes (parent to child), and we pop from the left end (temp.pop(0)) and send that node through the action function.
• If a node does not have a possible action, the program moves on to the next node in temp[ ]. If there are no more nodes in temp[ ], there is no solution.

DFS

• Parameters (Initial state, Goal state, output file, temp [ ], solution).
• Algorithm is similar to BFS, with one difference in the action function — instead of adding the child node to temp[ ] after checking if it isn’t repeated, we recursively call the action function again for the child node.
• In this way, we travel down a single path down — child’s path — until a solution is found or come to a dead end.

IDDFS

• Parameters (Initial state, Goal state, output file, temp [ ], solution, depth).
• Algorithm is similar to the two previous searches, except we have a depth variable.
• Depth defaults as the level of the first root node (which is 0).
• Program recursively calls action function for child nodes unless it is at the specified “depth”. Then root node is placed back in temp [ ].
• Program continues call action function but with depth incremented one more level. This is repeated until a solution is found or comes to a dead end.

A-Star

• Parameters (Initial state, Goal state, output file, temp [ ], solution, comparison [ ]).
• Similar to BFS, but all child nodes found on each level are compared with each other in comparison [ ], and only one (or sometimes multiple if they had same value) is chosen to be put in temp [ ].
• Value = (Number of items on left-bank in goal state – number of items on left bank in node) + level/depth.
• Followed f(n) = h(n) + g(n) where h(n) is distance away from goal and g(n) is distance away from starting node.

Results

Discussion

As expected, the evidence shows that BFS and A-Star were faster and more efficient in comparison to DFS and IDDFS, especially as the problems became more complicated. I predicted greedy algorithms would fall behind as the tree got deeper. What I did not expect is that the algorithms found the same paths (or at least very similar paths). The searches had the same number of steps in test case 2, and almost the same in test case 1. In terms of runtime, it is interesting that DFS and BFS were dead even with the less complicated problems. I surmised that DFS would have some advantage with shallow trees because it is designed to work through simple problems quickly.

Conclusion

The results prove that greedier uniformed algorithms get worse as the tree deepens. Also, informed algorithms have an edge over uniformed algorithms, which is expected. Knowing the answer or goal of a problem makes it easier to find a path from a starting point quickly and this experiment supports that conclusion.

Want to View My Code?

Click here to access the Google Drive folder containing this project.