問題タブ [hamiltonian-cycle]

そのため、私はこの仕事を与えられましたが、費用に関する情報をどのように使用すればよいかわかりません。これは要件であり、追加情報はありません。

直交方向の移動のみを許可する均一なコスト グリッドを使用しています。これは、ヘビが常に移動してボード上のリンゴを食べようとするゲームのヘビのベースとして使用されます。食べ物の位置と衝突回避は、古典的な AStar アルゴリズムを使用して行われ、ヘビの頭と食べ物の間の最短経路を見つけます。ただし、この方法では、ヘビが次の餌への明確な道筋を持たない餌を求めてしまうことがあります。ヘビは不規則な形の長方形に閉じ込められてしまい、この時点では将来のシミュレーションはありません。

私の質問は次のとおりです。不規則な長方形の内側で最長の動きの連鎖を見つけて、最も長く生き続け、おそらくヘビの尾が次の食べ物への道を塞ぐのを止める方法はありますか? ハミルトン アルゴリズムを調べてすべてのノードにアクセスしようとしましたが、不規則な形状の解決策がないようです。解決策は完璧である必要はありませんが、常にヘビが罠から逃れる可能性を最大限に高めるように努めるべきです。

何かご意見は？