このWebアプリケーションでは、さまざまなグラフ探索アルゴリズムをグラフィカルに表示しながら、8つのパズルの中から好きな問題を解くことができます。
- 初期状態とゴール状態
- どの検索アルゴリズムを使用するか
- 情報検索アルゴリズムを使用する場合、どのヒューリスティック関数を使用するか
- シングルステップかバーストモードか
それぞれのオプションについては、以下でより詳細に説明しています。
Initial and Goal States
初期状態または目標状態を設定するには、’Edit state’ ボタンまたは状態のグラフィック表示のいずれかをクリックします。
検索アルゴリズム
N-Puzzleは5つの異なるグラフベースの検索アルゴリズムをサポートしています。 最初の3つはUninformed Search Algorithmsで、
- Breadth-first Search
- Depth-first Search
- Iterative Deepening Search
残りの2つはInformed Search Algorithmsである。
- A* Search
- Greedy Search
Informed Search Algorithmを選択した場合、ヒューリスティック関数も選択する必要があります。
Heuristic Function
N-Puzzleは3種類のヒューリスティック関数に対応しています。
- Euclidean Distance
- Manhattan Distance (City-Block distance)
- Tiles Out of Place
シングルステップまたはバーストモード
N-Puzzle では2種類のモードで使うことができます。 デフォルトはSingle-Stepモードで、一度に1ステップずつ検索を「巻き戻す」ことができます。 これは、検索アルゴリズムがどのように動作するかをよりよく理解するのに便利です。
もう1つのモードはバーストモードです。 一旦開始すると、Burst Modeはゴール状態が見つかるまで検索を実行し続けます。
サーチツリー
状態表現
サーチがアクティブな間、サーチツリーの視覚的表現を見ることができる。 このサーチツリーの各ノードはタイルの配置（または状態）を表し、4つのセクションに分割されたボックスとして描かれます。
次の図は、Greedy検索から取得したノードを示しています：
最大のセクションはパズル状態です。 その下には、2つの小さなセクションがあります。
パズル状態の下には、2つのセクションがあります。 左側のセクションは、ノードの深さです。 右側のセクションはヒューリスティックスコアです。 発見的スコアは Informed Search Algorithms でしか使用されないため、Breadth-first、Depth-first、Iterative Deepening Search を使用している場合、発見的スコアは省略されます。
最後のセクションは、ノードが展開された順序を記録しています。 たとえば、ルート ノードは常に「#1」になり、次に展開されるノードは「#2」としてマークされます。
ノード カラー
検索ツリーをより「読みやすく」するために、各ノードの境界はその現在の状態に基づいて色分けされています。
次の図は、A*アルゴリズム（ユークリッド距離ヒューリスティックを使用）を、わずか2手で解決できる問題に適用したものです：
色は次のように解釈できます。
| 色 | 意味 |
|---|---|
| 青 | ノードがオープンリストにある場合、それは青で強調表示されます。 |
| Red | 検索アルゴリズムの各反復の後、次に展開されるノードは赤で強調表示されます。 |
| Grey | 探索済みの状態がある場合、それはグレーアウトされます。 例えば、上の図のステップ2）では、初期状態がグレーに着色されており、探索済みであることを表している。 ステップ3）では、初期状態を表すノードが再発見されるが、初期状態はルート・ノードを介して展開されているため、展開されることはない。 |
| 金 | 目標状態を表すノードが見つかると、ルートノードに戻るパス上のすべてのノードが金でハイライトされます。 |
| 紫 | 反復深化検索を使用すると、最大の深さを超える未探索のノードはオープンリストには追加されません。 |
Open and Closed Lists
検索アルゴリズムが実行されている間、2つのリストが維持されます。 1つ目はOpen Listで、これは発見されたがまだ探索されていないノードを追跡するために使用される。
2つ目はClosed Listで、これは探索済みのノード、または他のノードを通じて既に探索された状態を表すため探索されないノードを追跡するために使用される。
検索がアクティブな場合、オープン リストとクローズド リストのノード数は左上隅に表示されます：
クレジット
。