反復深化検索 (IDS) または反復深化深度優先検索 (IDDFS)

コンピューターサイエンスと人工知能に不可欠な要素は、検索アルゴリズムです。これらは、チェスやチェッカーなどのゲームのプレイから地図上の最短ルートの検索に至るまで、さまざまな問題を解決するために使用されます。最も一般的な検索アルゴリズムの 1 つである深さ優先検索 (DFS) 方法は、向きを変える前に各枝に沿ってできるだけ遠くまで移動することによって、ネットワークまたはツリーを検索します。ただし、DFS には重大な欠点があります。グラフにサイクルが含まれる場合、無限ループに陥る可能性があります。 Iterative Deepening Search (IDS) または Iterative Deepening Depth First Search を利用することは、この問題を解決する 1 つの手法 (IDDFS) です。

IDSとは何ですか?

IDS として知られる検索アルゴリズムは、DFS の利点と幅優先検索 (BFS) を組み合わせたものです。グラフは DFS を使用して探索されますが、ターゲットが特定されるまで深さの制限は着実に増加していきます。つまり、IDS は、望ましい結果が得られるまで、毎回深さ制限を上げながら DFS を継続的に実行します。反復深化は、検索が徹底的であること (つまり、解決策が存在する場合はそれを発見する) かつ効率的である (つまり、目標への最短経路を見つける) ことを保証する方法です。

IDS の疑似コードは次のように簡単です。

コード

 function iterativeDeepeningSearch(root, goal): depth = 0 while True: result = depthLimitedSearch(root, goal, depth) if result == FOUND: return goal if result == NOT_FOUND: return None depth = depth + 1 function depthLimitedSearch(node, goal, depth): if node == goal: return FOUND if depth == 0: return NOT_FOUND for child in node.children: result = depthLimitedSearch(child, goal, depth - 1) if result == FOUND: return FOUND return NOT_FOUND

IDSはどのように機能しますか?

iterativeDeepeningSearch 関数は、ルートノードとゴールノードを入力として使用して、目標が達成されるか検索スペースが使い果たされるまで、グラフ上で反復深化検索を実行します。これは、深さ制限を DFS に適用する DepthLimitedSearch 関数を定期的に使用することによって実現されます。ゴールが任意の深さにある場合、検索は終了し、ゴールノードを返します。検索スペースが使い果たされた場合 (深さ制限までのすべてのノードが調査された場合)、検索では None が返されます。

DepthLimitedSearch 関数は、ノード、宛先ノード、および深さ制限を入力として受け取ることにより、指定された深さ制限を持つグラフ上で DFS を実行します。目的のノードが現在の深さにある場合、検索は FOUND を返します。深さの制限に達してもゴールノードが見つからない場合、検索は NOT FOUND を返します。どちらの基準も当てはまらない場合、検索は繰り返しノードの子孫に進みます。

プログラム：

コード

 from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list) def add_edge(self, u, v): self.graph[u].append(v) def iddfs(self, start, goal, max_depth): for depth in range(max_depth+1): visited = set() if self.dls(start, goal, depth, visited): return True return False def dls(self, node, goal, depth, visited): if node == goal: return True if depth == 0: return False visited.add(node) for neighbor in self.graph[node]: if neighbor not in visited: if self.dls(neighbor, goal, depth-1, visited): return True return False # Example usage g = Graph() g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.add_edge(3, 3) start = 0 goal = 3 max_depth = 3 if g.iddfs(start, goal, max_depth): print(&apos;Path found&apos;) else: print(&apos;Path not found&apos;)

出力

 Path found

利点

IDS は、さまざまな点で他の検索アルゴリズムよりも優れています。 1 つ目の利点は、包括的であるため、検索スペース内に解決策が存在すれば、確実に解決策が見つかることです。これは、深さ制限 DFS を実行する IDS によって深さ制限が引き上げられる前に、特定の深さ制限の下にあるすべてのノードが調査されるようにするためです。
IDS はメモリ効率が高く、これが 2 番目の利点です。これは、IDS が検索領域内のすべてのノードをメモリに保存しないことで、アルゴリズムに必要なメモリを削減するためです。 IDS は、現在の深さ制限までのノードのみを格納することで、アルゴリズムのメモリフットプリントを最小限に抑えます。
IDS の 3 番目の利点は、ツリー検索とグラフ検索の両方に利用できることです。これは、IDS がツリーやグラフなどのあらゆる検索スペースで機能する汎用検索アルゴリズムであるためです。

短所

IDS には、特定のノードに複数回アクセスする可能性があり、検索が遅くなる可能性があるという欠点があります。完全性と最適性による利点は、多くの場合、この欠点を上回ります。さらに、メモリやキャッシュなどの戦略を採用することで、繰り返されるトリップを最小限に抑えることができます。