พูดคุย:ศึกษาสำนึก

จากวิกิพีเดีย สารานุกรมเสรี

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

[แก้] 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{h1(n),h2(n)...hi(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.