algorithm - A* のウォータージャグヒューリスティック関数

Question

古典的な水差しの検索問題の場合、3 つ以上の水差しの場合でも、A* 検索アルゴリズムに使用できる許容関数はどれですか?

編集：

http://www.dave-reed.com/csc550.S02/HW/HW4.htmlについては知っていますが、その機能は明らかに一貫していません。

score 3 · Accepted Answer

許容ヒューリスティックを設計する一般的な方法は 2 つあります。どちらも、より単純な問題を解決することで機能します。ヒューリスティック値は、より単純な問題のゴールまでの距離です。

1. リラクゼーション

問題は、負の影響を忘れることによって単純化されます。たとえば、かつて 1 クォートの水があった場合、必要なときにいつでも利用できます。

いくつかの詳細を無視することで、問題は単純化されます。たとえば、より単純な目標では、最後に最後の水差しの水の量を無視できます。

事前に計算されたヒューリスティック値をパターンデータベースに格納できます。キーはより単純な抽象的な問題であり、値はヒューリスティックな値です。