Search Optimisation Flashcards
1
Q
What is cycle checking?
A
Search prunes path ending in node already in the path.
2
Q
What is multiple path pruning?
A
Prune a path to node n, if the search has already found a path to node n.
3
Q
How do we ensure multiple path pruning not remove optimal solutions?
A
- 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.
4
Q
What are tabu lists?
A
Store the last k assignments, dont allow assignments in the tabu.
