SE250:May 29

Example on State-space search

Mark started off with a problem:

Start State = 1

Legal Moves:
x <- 2*x
x <- x/3

Goal State = 13

NOTE: when deviding an interger, ignore the reminder.

Solution in 9 moves

state      move
1          *2(deviding 3 would end up a 0 and stucked)
2          *2( /3 would result a 1 which lead back to 1st state)
4          *2
8          *2
16         /3
5          *2
10         *2
20         *2
40         /3
13         YEAH

Then Mark showed us a graph on the problem.

General Search Procedure

• Start of the root
• Check the 2 children to see if they contain the goal state or the state we have been to before
• Go to the node we have not been to before, and continue above till the goal state is reached

Using this procedure we can get the smallest number of moves. This search procedure is called breath-first search.

Programming breath-first search

• We need some data structure storing the nodes(states) we have been to
• It is easy if the database size is fixed-size, similar to the maze project last year

"Think about this in your own time." Mark said.

Depth-first search

• Suitable to use for search without infinite path.
• Using a stach to store the next move.
• Less Memory used.
• Easier to program, using recrusive function.

Problem For Tomorow

Knapsack problem:

given a bag weight limit W.
different type of discrete obejects(plenty of each type).
type i has value Vi, weight Wi.
maximize total value chosen and not exceeding weight limit.

Plus, find an exapmple where the "greedy" strategy(filling the bag with the highest value) fails.

Minutes

• Minute-Taker: zyan057
• Please let me know if anything is incorrect.