チェビシェフ距離のダイクストラアルゴリズム

Question

プリンストン大学アルゴリズム第2部で与えられたグラフAPIの最短経路を見つけるためにダイクストラアルゴリズムを使用していますが、私はチェビシェフ距離でパスを見つける方法を考え出しました。

コストが1でノードのいずれかの側に移動することはできますが、トータルコストには影響ありませんが、グラフによれば、赤い円、なぜパス探索行がジグザグなくジグザグ移動するのですか？まっすぐ動く？

A *アルゴリズムを使用すると同じことが繰り返されますか？

Answer 1

あなたは「直線」を優先させたい場合は、アカウントに、前のステップの方向性を取る必要があります。考えられる方法の1つは、グラフG'(V', E')を作成することです。ここで、V'はすべての隣接する頂点のペアで構成されます。例えば、頂点v = (v_prev, v_cur)は、パス内の頂点を定義し、v_curはパスの最後の頂点であり、v_prevは前の頂点です。次に、最短経路アルゴリズムの「距離の更新」ステップで、最良の（変化しない）方向の最良の距離を選択することができます。

また、方向の変更の数に等しい距離にプロパティを追加し、最小限の方向変更数で最小距離の方法を見つけることができます。

Answer 2

DijkstraまたはA *によると、といっても、それは総コストには影響しません。ところで、特に無駄なジグザグを避けたいと思っており、一般的に以前の動きと同じ方向に進む動きは特にありません。

DijkstraとA *には「奇妙なパス」の組み込みの嫌悪感はなく、明示的にコストを気にかけているだけで、暗黙のうちに同じコストをどのように扱うかを意識しています。 2つのノードが等しいコスト（GまたはF、あなたはダイクストラまたはAやっているかどうかに応じて*持っている時はいつでも彼らはまっすぐ移動を好む作るためにタイブレーク

1. 用途：あなたはそれについて行うことができます物事のカップルがあります。 ）。最終的に等しい長さのパスにつながる2つの選択肢が必ずしも同じFスコアを持つとは限らないため、障害を回避するためにいくつかの問題があります。それは決してあなたに準最適なパスを与えることはありません。
2. わずかにあなたの対角線コストを増やすには、直線では10、対角線では11といっても過言ではありません。これは、ショートカットではない斜めの移動を避けるだけです。しかし明らかに、それが実際のコストと一致しない場合は、準最適なパスを見つけることができます。コスト差が大きいほど、それだけ多くのことが起こります。実際には、それは比較的まれであり、パスは十分に長くなければならない（十分なコスト差を累積してから、余分な移動全体の価値がある）。