พูดคุย:การแก้ปัญหาแบบศึกษาสำนึก

ย้ายออกมาจาก บทความเนื่องจากเป็นข้อความอังกฤษทั้งหมดที่ยังไม่ผ่านการแปลเป็นไทย

Finding heuristics

The problem of finding an admissible heuristic with a low branching factor for common search tasks has been extensively researched in the AI community. A number of common techniques are used:

• Solution costs of sub-problems often serve as useful estimates of the overall solution cost. These are always admissible. For example, a heuristic for a 10-puzzle might be the cost of moving tiles 1-5 into their correct places. A common idea is to use a pattern database that stores the exact solution cost of every subproblem instance.

• The solution of a relaxed problem often serves as a useful admissible estimate of the original. For example manhattan distance is a relaxed version of the n-puzzle problem, because we assume we can move each tile to its position in a single step.

• Given a set of admissible heuristic functions $h_{1}(n),h_{2}(n)\ldots h_{i}(n)$, the function $h(n)=max\{h_{1}(n),h_{2}(n)...h_{i}(n)\}$ is an admissible heuristic that dominates all of them.

Using these techniques a program called ABSOLVER was written (1993) by A.E. Prieditis for automatically generating heuristics for a given problem. ABSOLVER generated a new heuristic for the 8-puzzle better than any pre-existing heuristic and found the first useful heuristic for solving the Rubik's Cube.