8 つの方向のいずれかに移動できる正方形のタイルのマップがあります。隣接するタイルから別のタイルに移動するコストを示す関数が呼び出されcost(tile1, tile2)た場合、許容可能で一貫性のあるヒューリスティック関数 h(y, goal) をどのように見つけますか? costこの設定でヒューリスティックを見つける方法を一般化できますか、それとも機能 によって異なるのでしょうか?
37985 次
3 に答える
17
Amit のチュートリアルは、私が A* (Amit のページ)で見た中で最高のものの 1 つです。このページには、ヒューリスティックに関する非常に役立つヒントがいくつかあります。
あなたの問題についての引用は次のとおりです。
8 方向に移動できる正方形のグリッドでは、対角距離 (L∞) を使用します。
于 2011-04-16T16:32:03.700 に答える
6
于 2011-04-16T16:34:51.687 に答える
0
Yes, the heuristic is dependent on the cost function, in a couple of ways. First, it must be in the same units. Second, you can't have a lower-cost path through actual nodes than the cost of the heuristic.
In the real world, used for things like navigation on a road network, your heuristic might be "the time a car would take on a direct path at 1.5x the speed limit." The cost for each road segment would use the actual speed limit, which will give a higher cost.
So, what is your cost function between tiles? Is it based on physical properties, or defined outside of your graph?
于 2011-04-16T16:36:25.600 に答える