欲張りグラフで点Aから点Bまでを検索

Question

私の教科書の質問は、Mehadiaからブカレストへの経路を計算して、1）欲張り探索と2）均一コスト検索によって求めました。

*ここでは、一貫したコスト検索で経路を完全に説明し解決することができましたが、私の欲張り検索は非常に似ています。どのように私は "欲張り"の検索を介してルートを計算することができます上の任意のアイデア？

UPDATE 私は散らかっ貪欲algotithmを適用したし、私の均一価格からの最短ルート対異なるルートを頂いております。

これは私の欲張りアルゴリズムによって出力されたルートです。アルゴリズムはちょうどチェックし、最小のローカル値を選択します。誰かに私の新しい質問：このルートは私の欲張りアルゴリズムの出力として受け入れられますか？私。私の解決策が法的に貪欲であるとみなされる可能性もありますか？ >ルゴジ - - >ティミショアラ - >アラド - > Zerind - >オラデア - >シビウ - > リムニクビルチャ - >ピテシュティ - >ブカレスト

Answer 1

Mehadia：私の新しいアルゴリズムに基づいて

ルートユニフォーム・コスト・サーチを使用すると、Mehadiaからすべてのノードまでの最短経路が計算されますので、Mehadia-Bucharestパスが最適であることがわかります（このアルゴリズムは完全で最適です）。 Greedy Search Algorithmを使用すると、ローカルで最も良い オプションが選択され、ノードごとに他のものが破棄されます。このアルゴリズムは完全でも最適でもありません。 あなたの質問に答えるには、あなたの解決策は欲張りとみなされます。

これが役に立ちます。