Search Optimisation

Question 1

What is cycle checking?

Answer 1

Search prunes path ending in node already in the path.

Question 2

What is multiple path pruning?

Answer 2

Prune a path to node n, if the search has already found a path to node n.

Question 3

How do we ensure multiple path pruning not remove optimal solutions?

Answer 3

• Make sure first path found is optimal.
• Remove only the longer path when pruning.
• Change the inital segments of paths on the frontier to the new shorter path.

Question 4

What are tabu lists?

Answer 4

Store the last k assignments, dont allow assignments in the tabu.