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]

 

some search algorithms (source: week 2 lecture notes)

<a href=”http://www.novelgames.com/flashgames/game.php?id=54&l=e”>Missionaries and Cannibals</a>