4

私は、一般化された AI の問題に対して多くの検索アルゴリズムを試しています。そのうちの 1 つは深さ優先検索です。幅優先検索、欲張り検索、および A* 検索を自然な再帰形式から反復型検索に変換しましたが、深さ優先検索でそれを行うのにもう少し問題がcleanlyあります (私の能力を超えているわけではありませんが、私は.そうするための最もpythonicな方法がわからないので、質問です）。

中規模の問題であっても、CPython の 1000 回の再帰呼び出し制限で問題が発生しています。後続の状態は遅延生成され (_generate_statesはジェネレーターであり、リストではありません)、初期状態からのパスが必要です。

コール スタックの使用から明示的なスタックに移行する最も Pythonic な方法は何ですか? スタックにどのくらいの情報を格納する必要がありますか? バックトラックするとき (状態が空でないリストを返さないとき)、スタックの先頭から死んだ情報をポップする最良の方法は何ですか?

def dfs(initial, closed_set, goal, capacity):
    if initial == goal:
        return [initial]

    for state in _generate_states(initial, capacity):
        if state not in closed_set:
            result = dfs(state, [initial] + closed_set, goal, capacity)
            if result:
                return [state] + result
    return []
4

3 に答える 3

4

必要な遅延プロパティを維持するためにジェネレーターを維持するソリューションを次に示します。

def dfs(initial, goal, capacity):
    # These three variables form the "stack".
    closed_set = {initial}
    stack = [initial]
    gens = [_generate_states(initial, capacity)]

    while stack:
        cur = stack[-1]
        gen = gens[-1]
        try:
            state = next(gen)
        except StopIteration:
            # This node is done
            closed_set.discard(cur)
            gens.pop()
            stack.pop()
            continue

        if state == goal:
            return stack

        if state not in closed_set:
            closed_set.add(state)
            stack.append(state)
            gens.append(_generate_states(state, capacity))

    return None

スタックは、現在のノードに到達するためにアクセスしたノードの記録であるため、ターゲットが見つかったときのパスはスタックであることに注意してください。

于 2012-10-02T16:20:43.497 に答える
3

スタックを使用して反復的に DFS を実装する方法を知っていると仮定します (基本的には BFS の場合と同じで、FIFO ではなく LIFO のみです)。そのため、いくつかの一般的なヒントを投稿します。

  • DFS を反復的に実装する場合はcollections.deque、要素をすばやく追加およびポップするために最適化されたスタックを使用する必要があります。
  • closed_setリストの代わりにセットを使用する必要があります。(または、最短経路を見つけたい場合はマップ {state: depth}。)
  • パスを追跡するために、現在の状態と前の状態への参照 (基本的には状態のリンクされたリスト) をカプセル化するラッパー クラスを作成するか、先行する状態のマップを使用できます。

ただし、この場合にジェネレーターを使用する方法がわからないため、スタックは深さ x 分岐係数要素まで保持されます...または、実際の要素の代わりにジェネレーターをスタックに配置できますか? ただのアイデア...

于 2012-10-02T15:50:55.700 に答える
1

反復的な深さ優先検索を作成する方法は次のとおりです。candidate_states次に探索する必要がある状態のスタックとして使用します。parentsディクショナリを使用して、訪問したノードから最初のノードまでのパスを再構築できます。

def reconstruct_path(state, parents):
    path = []
    while state != None:
        path.append(state)
        state = parents[state]
    path.reverse()
    return path

def dfs(initial, goal):
    visited_states = set()
    candidate_states = [initial]
    parents = {initial: None}
    while len(candidate_states) > 0:
        cur_state = candidate_states.pop()
        if cur_state in visited_states: continue
        if cur_state == goal:
            return reconstruct_path(cur_state, parents)
        for state in _generate_states(cur_state):
            parents[state] = cur_state
            candidate_states.append(state)
    return None
于 2012-10-02T15:49:27.227 に答える