Robert Anderson's Blog

Idea #1: Heuristic Pruning

The easiest and most common use for heuristic functions is to prune the search space. Assume the problem is to find the solution with the minimum total cost. With an admissible heuristic function, if the cost of the current solution thus far is A, and the heuristic function returns B, then the best possible solution which is a child of the current solution is A+B. If the a solution has been found with cost C, where C < A+B, there is no reason to continue searching for a solution from this state.

This is simple to code and debug (assuming one starts with a working, but slow, program, which is how this should be used) and can yield immense returns in terms of run-time. It is especially helpful with depth-first search with iterative deepening.

Idea #2: Best-First Search

The way to think of best-search is as greedy depth-first search.

Instead of expanding the children in an arbitrary order, a best-first search expands them in order of their ``goodness,'' as defined by the heuristic function. Unlike greedy search, which only tries the most promising path, best-first search tries the most promising path first, but later tries less promising ones. When combined with the pruning described above, this can yield very good results.

Idea #3: A* Search

The A* Search is akin to the greedy breadth-first search.

Breadth-first search always expands the node with minimum cost. A* search, on the other hand, expands the node which looks the most promising (that is, the cost of reaching that state plus the heuristic value of that state is minimum).

The states are kept in a priority queue, with their priority the sum of their cost plus the heuristic evaluation. At each step, the algorithm removes the lowest priority item and places all of its children into the queue with the appropriate priority.

With an admissible heuristic function, the first end state that A* finds is guaranteed to be optimal.

以上轉自USACO

今天上課上Heuristic的問題

主要就是有一個Actual Cost還有一個Estimate Cost(Where EC <= 最終的AC)

用他去評估應該要先搜尋哪個點

IDA*的話就是你可以先設定一個Actual Cost上限

萬一他不行呢

再去Deepen