AI, Predicate Logic

Prepared by: - Shimelis kassa; Id: - RMSC/145/06

Solution formulation for three state space search problems 1. Color planar map State: - Map with each region assigned a color or none, and no two adjacent states colored with the same color. Initial state: No Regions Coloured Goal state: - All regions coloured. Successor function: - Assign a color to an uncoloured region

2. Traveling sales person problem State: - find the shortest path to drive between N cities and back to the starting city. Initial state: - N unvisited cities Goal state: - find shortest path to visit N cities and come back to the starting city Successor function: - drive between cities

3. Missionaries and cannibals problem State: - three missionaries and three cannibals on the side of a river to cross that river. Initial state: - three missionaries, three cannibals, boat on the side of the river and 0 missionaries and zero cannibals crossed the river Goal state: - zero missionaries and zero cannibals are on the side of the river; and three missionaries, three cannibals and the boat crossed the river. Successor function: - boat takes 1 missionary across river (1m) –

boat takes 1 cannibal across river (1c)

–

boat takes 2 missionaries across river (2m)

–

boat takes 2 cannibals across river (2c)

–

boat takes 1 missionary and 1 cannibal across river (1m1c)