最小桁数がの最短経路を返すようにA *を修正することはできますか？Path Finding - 最小ターン数を持つA *
1つの複雑さ：ノードは、親ノードが将来の順番を決定するのに関連しているので、もはやその位置だけで区別することはできません。
しかし、私が抱えている主な問題は、ターン数を部分パスコスト（g）にする方法です。 gをターン数（t）で掛け算すると、奇妙なことが起こっているようです。Nターンが終わり近くにある長いパスは、Nターンが始まり近くの短いパスよりも優先されます。
最短パスを計算した後、最短パスのx/y範囲内に制限された（パスコスト式が異なる）2番目のA *繰り返しを実行することができました、最小のターンでパスを返します。他のアイデア？
検索の現在の「状態」は、実際には、現在のノードと、直面している方向の2つによって表されます。あなたが望むのは、それらの状態のそれぞれを別々のノードに分けることです。
したがって、初期グラフの各ノードについて、それをE個の別個のノードに分割する。ここで、Eは入ってくるエッジの数である。これらの新しいノードの各々は、古いノードを表すが、異なる方向に向いている。これらの新しいノードの出力エッジは、すべて古い出力エッジと同じですが、異なる重みを持ちます。エッジががターンを表していない場合は、古い重量がw、そして...
w同様w + εです。ここで、εは最小の重量よりもかなり小さい数値です。次に、通常のA *検索を行います。重みのいずれも減少していないので、ヒューリスティックは依然としてadmissibleであるため、同じヒューリスティックを使用することはできます。
本当にターン数を最小限に抑えたいのであれば（ターンとパスの長さの間に良いトレードオフを見つけるのではなく）、障害のない直線で接続されたノードのすべてのペアに対してエッジを追加して、 ;これらはあなたがターンを経ずに旅行することができるペアです。ノードごとにこのようなエッジがあるので、新しいグラフはエッジの点でO（n ）です。これは、A *解をO（n ）と同じくらい時間をかけて作ります。
マンハッタン距離はA *のヒューリスティックでよいかもしれません。