4

さまざまなアルゴリズムを使用して問題を解決しようとしていますが、実装が必要なアルゴリズムには、最急上昇ヒル クライミング (SAHC) と最優先探索の 2 つがあります。

ウィキペディアによると：

「最も急な上り坂のヒルクライムでは、すべての後継者が比較され、解決策に最も近いものが選択されます...」

「最も急な上り坂の登山は、1 つだけではなく、現在のパスのすべての可能な延長を試みる最善優先探索に似ています。」

SAHC : すべての後継が比較され、ソリューションに最も近いものが選択されます。
BestFS : 1 つだけではなく、現在のパスのすべての可能な拡張子を試します。

これらの違いがよくわかりません。できれば木を使った何らかの説明で、これを手伝ってもらえますか？

4

3 に答える 3

13

それらは非常に似ています。違いは、最適優先検索では開始ノードから終了ノードまでのすべてのパスが考慮されるのに対し、最急勾配の上り坂では検索中に1 つのパスしか記憶されないことです。

たとえば、次のようなグラフがあるとします。

start ---- A ---- B ---- end
  \                     /
   ------\    /---------
          \  /
           C

ここで、各エッジの重みは同じです: 私のくだらない ASCII アート スキルは無視してください :)。また、ヒューリスティック関数で、A が C よりも端に近いと見なされているとします (これは許容できるヒューリスティックであり、A の実際の距離を過小評価しているだけです)。

次に、最も急な上り坂のクライミングでは、最初に A が選択され (ヒューリスティック値が最も低いため)、次に B が選択され (ヒューリスティック値が開始ノードよりも低いため)、最後に終了ノードが選択されます。

一方、最善優先探索では、

  1. A と C をオープン リストに追加します。
  2. オープン リストから最良の値である A を取り出し、B を追加します。次に、OPEN = {B, C} です。
  3. 開いているリストから最良のノードを取り出し (B または C のいずれか、それについては後で詳しく説明します)、その後継である目標状態を追加します。
  4. 開いているリストから目標状態を取り出し、そこに到達したパスを返します。

ステップ 3 での B または C の選択は、使用している最適優先検索アルゴリズムによって異なります。A*はノードを、そこに到達するためのコストと最後に到達するための推定コストを足したものとして評価します。この場合、C が勝ちます (実際、許容可能なヒューリスティックを使用すると、A* は常に最適な結果を得ることが保証されます)。道）。「貪欲な最良優先検索」は、2 つのオプションから任意に選択します。いずれにせよ、検索では、単一の場所ではなく、移動可能な場所のリストが維持されます。

両者の違いがより明確になりましたか？

于 2013-02-07T00:04:51.833 に答える
4

SAHC は 1 つの (おそらく最適ではない) パスを貪欲に選択します。ターゲットに到達するまで、各ステップで最適なノードを選択するだけです。

一方、ベスト ファーストは検索ツリー全体を生成します。多くの場合 (A* の場合)、最適なソリューションが見つかりますが、これは SAHC では保証されません。

于 2013-02-07T00:18:40.407 に答える
0

フラグの付け方がわからないので貼り直しました、ごめんなさい。だからここに私が違いとして得たものがあります。

違いは、目標状態を探す上で何がより重要かを理解することにあります。

私たちの目的は何ですか...最終的な目標状態は何ですか? または目標状態に到達するための最良のパス

ベスト ファースト サーチは、現在のノードごとに隣接ノードの最適なヒューリスティック値を見つけることに基づいて、反復的に前進することによって体系性が達成される体系的な検索アルゴリズムです。

ここで、評価関数 (ヒューリスティック関数) は、目標状態に到達するための最善のパスを計算します。したがって、ここでは、ベスト ファースト検索が目標状態に到達するための最適なパスに関係していることがわかります。

しかし、「ゴールへの道」が問題ではない問題が多くあります。唯一の問題は、可能な方法またはパスで最終状態を達成することです。(例: 8 クイーン問題)。

したがって、このローカル検索アルゴリズムが使用されます。

ローカル検索アルゴリズムは、単一の現在のノードを使用して動作し、通常はそのノードの近隣にのみ移動します。

Hill Climbing アルゴリズムは、局所探索アルゴリズムです。したがって、ここでは、ヒルクライムを考えるときに到達するための最良の道ではなく、目標状態に到達するためのアプローチを理解する必要があります.

( AI-A Modern Approach,SR & PN に記載)

基本的に、ローカル検索を理解するには、状態空間ランドスケープを考慮する必要があります。

ランドスケープには両方があります

(i)場所(州によって定義される) および

(ii)高度(ヒューリスティック関数または目的関数の値によって定義される)

標高の 2 つのタイプを理解する必要があります。

(i)標高が目的関数に対応する場合、目的は最高のピーク、つまりグローバル最大値を見つけることです。

（したがって、これらのタイプの高度は、コストに関係なく、最良の瞬間的な動きを見つけることだけに関係するさまざまなシナリオで役立ちます）

(ii)標高がコストに対応する場合、目的は最低の谷、つまりグローバル ミニマムを見つけることです。

(これが一般的なことです。つまり、最も急勾配です(常により良い推定でステップアップします。つまり、プラトーの問題やその他のことはありません)。ヒルクライムは、ベストファーストサーチに似ています。ここで、標高関数は、最良の最小コストを提供するヒューリスティック関数です。そして、ヒルクライミングここでは、現在のノードのみに関係し、隣接するノードを反復して最小値を求め、Best First Search に似た最適なノードの拡張に進みます)

注:

ヒル クライミング アルゴリズムは、現在の状態の直近の近隣を超えて先を見ません。拡張するのに最適な隣接ノードのみが考慮されます。そして、最適な隣接ノードは上記の評価関数によって決定されます。

一方、ベスト ファースト サーチ アルゴリズムは、すぐ近くにあるものよりも先を見て、 (ヒューリスティック評価を使用して) ゴールへの最適なパスを見つけてから、最適なものに進みます。したがって、違いはローカル検索と体系的な検索アルゴリズムのアプローチにあります。

アプローチの違いを理解すると、両者の名前が異なる理由がわかります。

于 2015-11-17T09:59:53.400 に答える