Pythonの幅広い検索実装

Question

私はPythonでBFSを実装しようとしていますが、アルゴリズムの仕組みを理解していますが、プログラミングの経験はあまりありません。私はすべてを表現する最善の方法とできるだけ効率的になる方法について何時間も考えました。私は、スタートノードからゴールノードへのパスを取得する方法を理解することができませんでした。

私は周りにグーグルを見て、他の人々のアルゴリズムの実装を見てきましたが、私のアプリケーションは少し異なり、これは私を混乱させる。人々がBFSを実装しているとき、彼らは彼らに与えられたグラフを持っていると仮定しています（BFSのwikipedia記事もそうです）。私の問題では、私は最初の状態と私が到達したい目標状態を持っていますが、グラフやツリーはありませんので、私はノードを生成しています。例えば

：私は何かに問題を抱えているので、それが適切に肉付けいない

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) 

、私はそれが特異的のいずれかである何...最初のゴールは、ノードの場合はわからない、と私

class node: 
    state = None 
    parent = None 

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

私は目標ノードを見つけたので、私は訪問先ノードのリストを持っていますが、目標ノードからのパスを逆方向にトレースすると、アルゴリズムは遅くなりませんか？目標が見つかったら、私はその親を見て、訪問先のリストでその親を見つけ、次に親の親を見て、など...まで、私はパス= [ノードオブジェクト、ノードオブジェクト、... ]を初期ノードからゴールノードに送信する。

これは別の問題に繋がります。ノードオブジェクトを作成すると、それはwhileループの1回の繰り返しでのみ持続します。どのようにオブジェクトを配列に格納するのか、それぞれ固有の名前が必要であり、これを行うための明白な方法はありません。これは私が前に私が確信していなかったことに言及した問題でした。だから、私はノードを作成しているようですが、node.starentをキューに格納するだけです。ノードオブジェクトがnode.parentにアクセスする必要があるため、無意味です...

なぜこれが難しいのですか？明白な何かを見逃したり、これを複雑すぎるものにしていますか？

読んでいただきありがとうございます。

Answer 1

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

私は、配列内のオブジェクトを格納するためのものていますどのように、彼らはそれぞれこれは間違いなく偽である

一意の名前が必要になります。リストに格納するだけの場合は名前を付ける必要はありません。追加するだけです。後で見つけられるのではないかと心配しているのであれば、グラフで行う通常のことは、定義するたびに増加する単一のカウンタを使用して、各ノードに数値を与えることだけです。繰り返しますが、ノードをリストに格納するだけであれば、自動的に固有の番号（リスト内の位置）を取得します。

Answer 2

あなたのアプローチはうまくいくようです。

検出パスを取得するために、各ノードの親ノードを追跡することができます。それを発見したノードに設定されている属性を与えます。そうすれば、発見パスをたどるリンクされたリストが得られます。あなたは（変数n）生成されたノードを追跡するための

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

    yield node.parent 
    get_parents(node) 

を行うことができ、目標に到達したら、戻って歩くために、ちょうどあなたがリストに発見したノードだけでなく、状態を置きます。

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) 

Answer 3

一般に、あなたが持っているものは問題ありません。

しかし、私は説明しようとするいくつかの混乱があります。まず、状態ではなくキューにノードを格納します。ノードには親があるため、以前のノードにアクセスできるので、それらを失っていません。第二に、親を通して戻ってくることは、あなたが効率を心配する必要があるものではありません。あなたが成功したときに行うだけです（また、名前を必要とせず、リストを地図と混同しているように思えます）。

コードから唯一欠けていることは、実際にはノードを作成していないことです。状態を取得したら、ノードを作成し、状態ではなくノードを保存します。すべてがうまくいくでしょう。