2

PythonでBFSを実装しようとしています。アルゴリズムがどのように機能するかは理解していますが、プログラミングの経験はあまりありません。私は何時間もかけて、すべてを表現するための最良の方法と、可能な限り効率的にする方法について考えてきました。開始ノードから目標ノードへのパスを取得する方法を理解できませんでした。

私は何年もの間、他の人々のアルゴリズムの実装を調べたり調べたりしてきましたが、私のアプリケーションは少し異なり、これは私を混乱させます。人々がBFSを実装しているとき、彼らは彼らにグラフが与えられていると想定しています（BFSに関するウィキペディアの記事もそうです）。私の問題では、到達したい初期状態と目標状態がありますが、グラフやツリーがないため、ノードを生成しています。

例えば：

def BFS(initial, goal):

    q = [initial]
    visited = []

    while q:
        n = q.pop()
        states = generate_states(n)

        for state in states:
            if state == goal:
                pass #placeholder
            q.append(state)
            visited.append(state)

何かに問題があるため、適切に具体化されていません。具体的には何であるかわかりません... initialとgoalがノードであり、コードの他の場所に次のような構造体型クラスを記述している場合。

class node:
    state = None
    parent = None

これはノードを表すのに適した方法だと思います。したがって、ノードオブジェクトをキューからポップすると、生成元の場所に関する情報があり、generate_states関数によって初期化されます。次に、forループは、これらの新しいノードのそれぞれをキューに追加し、キューにアクセスします。生成されたノードの1つで繰り返され、目標の状態と一致する状態になります。

ゴールノードが見つかったので、訪問したノードのリストがありますが、パスをゴールノードから逆方向にトレースすると、アルゴリズムの速度が低下しませんか？目標が見つかったら、その親を調べ、訪問先リストでその親を見つけ、次に親の親を調べます。パス= [ノードオブジェクト、ノードオブジェクト、... ]初期ノードからゴールノードへ。

これにより、別の問題が発生します。ノードオブジェクトを作成すると、whileループの1回の反復でしか持続しません。オブジェクトを配列に格納するにはどうすればよいですか。オブジェクトにはそれぞれ一意の名前が必要であり、これを行うための明確な方法は（私には）ありません。これは私が前に述べた問題であり、私にはよくわかりませんでした。したがって、ノードを作成しているように見えますが、node.stateをキューに格納するだけです。これは、ノードオブジェクトがnode.parentにアクセスする必要があるため無意味です...

なぜ私はこれがとても難しいと思うのですか、私は何か明白なものを見逃しているのですか、それともこれを複雑にしすぎているのですか？

読んでくれてありがとう。

4

3 に答える 3

1

あなたが何をしようとしているのか完全には理解していないので、これについてコメントすることはできません-あなたが言うように、通常、BFSはすでにそこにグラフを持っているので、あなたがどのように提案しているのかわかりませんあなたが行くようにそれを構築します。しかし、私はこのビットに返信する必要があります：

オブジェクトを配列に格納するにはどうすればよいですか。それぞれに一意の名前が必要です。

これは間違いなく誤りです。リストに保存したいだけの場合は、名前を付ける必要はまったくありません。名前を追加するだけです。後でそれを見つけることができるかどうか心配している場合、グラフで行う通常のことは、ノードを定義するたびに増やす単一のカウンターを介して、各ノードに番号を付けることです。繰り返しになりますが、ノードをリストに保存しているだけの場合、ノードは自動的に一意の番号、つまりリスト内の位置を取得します。

于 2012-04-14T14:41:20.997 に答える
0

あなたのアプローチは私にはうまく見えます。

検出パスを取得するために、各ノードの親を追跡できます。たとえば、検出したノードに設定されている属性を指定します。そうすれば、ディスカバリーパスをさかのぼるリンクリストが得られます。目標に到達したら戻って歩くためにあなたはすることができます

def get_parents(node):
    if node.parent is None:
        return []

    yield node.parent
    get_parents(node)

生成されたノード（変数n）を追跡するには、状態だけでなく、検出したノードをリストに追加するだけです。

    n = q.pop()
    states = generate_states(n)

    for state in states:
        m = node()
        m.state = state
        m.parent = n
        if state == goal:
            pass #placeholder
        q.append(m)
        visited.append(m)
于 2012-04-14T14:48:11.690 に答える
0

一般的に、あなたが持っているものは大丈夫です。

いくつかの混乱がありますが、それについて説明しようと思います。まず、ノードを状態ではなくキューに格納できます。ノードには親があるため、前のノードにアクセスできるため、ノードを失うことはありません。第二に、親をさかのぼって追跡することは、効率を上げるために心配する必要はありません。成功した場合にのみ実行します（また、名前は必要ありません。リストとマップを混同しているように聞こえますか？）。

したがって、コードに欠けているのは、ノードを作成していないことだけです。状態を取得したら、状態を保存するのではなく、ノードを作成してノードを保存します。その後、すべてが機能します。

于 2012-04-14T14:52:01.363 に答える