Welcome to homework assignment #4 in CS373.
To remind you, we covered A-star and dynamic programming in class.
Let's start with an A-star question.
We learned in class that we can use heuristics,
and a heuristic is a admissible if the heuristic value is no larger
than the actual cost it takes to get to the goal.
In a maze, we know that the number of steps in the maze is a good heuristic,
because obstacles will make the path only longer, not shorter.
Consider a maze of size 3 x 3 and say there's a single goal state,
and the cost of moving is 1.
Is the function shown here admissible or not?
Please check one of the two radio buttons.
CS373の課題4へようこそ
講義では A*探索と
ダイナミック・プログラミングについて学びました
まずはA*の質問から始めましょう
ヒューリスティックという方法では
n値がゴールへたどり着く実際のコストよりも
大きくない場合に許容できます
迷路の中でのステップ数は
よいヒューリスティックだと言えます
障害は進路の距離を長くすることはあっても
短くはしないからです
ここにゴールが1つの3×3の迷路があって
動作コストは1だとします
この関数は許容できるでしょうか?
どちらか1つをチェックしてください