ツリーで検索する場合、均一コスト検索についての私の理解では、(10, 5, 7) のコストが関連付けられた子ノード B、C、D を持つ特定のノード A に対して、私のアルゴリズムは C を選択します。より低いコストで。C を展開すると、コストが (40、50、60) のノード E、F、G が表示されます。両方の 3 から最小値があるため、40 が選択されます。
では、常に最良のアクションと思われるものを選択する貪欲な検索を行うのと同じではありませんか?
また、特定のノードから別のノードに移動するコストを定義する場合、ツリーの先頭から現在のノードまでのコスト全体を考慮する必要がありますか?それとも、ノード n からノード n' に移動するコスト自体だけを考慮する必要がありますか?
ありがとう
いいえ。あなたの理解はまったく正しくありません。
均一コスト検索の場合に訪問される次のノードは、ルートからの総コストが最も低い (40+5=45 ではなく 7) ため、D になります。
Greedy Search はツリーを遡らず、最も低い値を選択してそれにコミットします。Uniform-Cost は、ツリー全体から総コストが最も低いものを選択します。
一様コスト検索では、見たノードに接続されているノードだけでなく、これまでに見たすべての未訪問ノードを常に考慮します。したがって、あなたの例では、C を選択した後、G にアクセスすると 40 + 5 = 45 の合計コストがかかることがわかります。これは、ルートから再度開始して D にアクセスするコストよりも高く、コストは 7 です。次にD.
それらの違いは、貪欲が最小のヒューリスティック値を持つノードを選択するのに対し、UCS は最小のアクション コストを持つノードを選択することです。次のグラフを検討してください。
両方のアルゴリズムを実行すると、次のようになります。
ピック: S (コスト 0)、B (コスト 1)、A (コスト 2)、D (コスト 3)、C (コスト 5)、G (コスト 7)
答え: S->A->D->G
* B の代わりに A を選択すると仮定します。A と B のヒューリスティック値は同じです
ピック: S、A (h = 3)、C (h = 1)、G (h = 0)
答え: S->A->C->G
そのため、問題定義の理解に基づいて、ノードに追加される情報であるヒューリスティック値からノードに到達するためのアクション コストを区別することが重要です。