FIT5047 – Intelligent Systems Week 2

Week 2 – search algorithms.I implemented A Breadth first search in Python for application to the Missionaries and cannibals problem.

—–>>>>      Python script:  http://mchost/sourcecode/MandC.py <<<<-—-

To run install python 2.7 then open terminal/cmd and $ python -i MandC.py

The game is not that simple: Play Missionaries and Cannibals game

The other search algorithms that we discussed in the week 2 lecture were:

• Breadth first search
• Depth First search
• Hill climbing
• Simulated annelaing
• Graph search (A*)

The most important assessment criteria for search algorithms are:

• Completeness [If there is a solution will it be found?]
• Optimality [Will the algorithm find the best solution (lowest path cost)]
• Time/Space complexity [Processing power and memory requirements]

Also introduced were heuristics [warmer colder hints for the search], two key characteristics:

• Admissibility [the cost of reaching the goal is never overestimated]
• Monotonicity [The estimated cost to goal from N1 is not greater than the step cost to N2 plus estimate to goal from N2 (aka consistency]