5

Python で深さ優先検索を実行しようとしていますが、うまくいきません。

基本的に、ペグ ソリティア ボードがあります。

[1,1,1,1,1,0,1,1,1,1]

1 はペグを表し、0 はオープン スポットです。ペグを一度に 2 つのスロットを後方または前方に 1 つずつ空の場所に移動する必要があります。その過程で別のペグを飛び越えると、それは空のスロットになります。ペグが 1 つ残るまでこれを行います。基本的に、ゲームは次のようになります。

[1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1] #etc until only 1 peg left

ここに私が持っているものがあります:

class MiniPeg():
    def start(self):
        ''' returns the starting board '''
        board = [1,1,1,1,1,0,1,1,1,1]
        return board

    def goal(self, node):
        pegs = 0

        for pos in node:
            if pos == 1:
                pegs += 1

        return (pegs == 1) # returns True if there is only 1 peg

    def succ(self, node):
        pos = 0
        for peg in node:
            if peg == 1:                
                if pos < (len(node) - 2):  # try to go forward
                    if node[pos+2] == 0 and node[pos+1] == 1:
                        return create_new_node(node, pos, pos+2)

                if pos > 2: # try to go backwards 
                    if node[pos-2] == 0 and node[pos-1] == 1:
                        return create_new_node(node, pos, pos-2)
        pos += 1

def create_new_node(node, fr, to):
    node[fr] = 0
    node[to] = 1
    if fr > to:
        node[fr-1] = 0
    else:
        node[fr+1] = 0
    return node

if __name__ == "__main__":
    s = MiniPeg()
    b = s.start()

    while not s.goal(b):
        print b
        b = s.succ(b)

だから、今私の質問：

  1. これは、これに対して深さ優先検索を行う正しい方法ですか?
  2. アルゴリズムが機能しません!!! 行き詰まります。ここで質問するまで何日も苦労してきたので、助けてください。
  3. 私は DRY に従っていないようですが、何か提案はありますか?
  4. ああ、助けて？
4

4 に答える 4

10

各ステップが「ボード位置」から可能な次の位置への「移動」である状況で、目標に到達するまで DFS を実装する通常の方法は、次のとおりです (疑似コード)。

seenpositions = set()
currentpositions = set([startingposition])
while currentpositions:
  nextpositions = set()
  for p in currentpositions:
    seenpositions.add(p)
    succ = possiblesuccessors(p)
    for np in succ:
      if np in seenpositions: continue
      if isending(np): raise FoundSolution(np)
      nextpositions.add(np)
  currentpositions = nextpositions
raise NoSolutionExists()

最後に、見つかったソリューション (存在する場合) につながる一連の動きを出力できるように、後方リンクを保持したい場合もありますが、これは補助的な問題です。

あなたのコードには、この一般的な構造 (またはその合理的な変形) の痕跡は見当たりません。このように記録してみませんか？possiblesuccessorsコード化するだけでisending済みます (位置をリストとして保持することを主張する場合は、それをタプルに変換して、セット内のメンバーシップを確認し、セットに追加する必要がありますが、それはかなりマイナーです;-)。

于 2010-01-26T06:17:07.337 に答える
1

既存のノードを再利用しているだけで、新しいノードを作成しているようには見えません。DFS には、何らかの種類のスタック (コール スタックまたは独自のスタック) が必要です。それはどこですか？

于 2010-01-26T06:05:33.703 に答える
0

まず、深さ優先検索はツリーを前提としています。ほとんどの場合、いくつかの可能な動きがあるので、ここでは理にかなっています。深さ優先探索は、成功するかそれ以上の可能な手がなくなるまで、最初の可能な手、次に新しい状況で最初の可能な手、そしてその新しい状況の最初の可能な手のことを単純に試行します。試したことのない動きを見つけて、再びダウンします。

それを行う「正しい」方法は、再帰を使用することです。私が見る限り、あなたのシステムには再帰はありません。

このようなものはうまくいきます（pythonic psuedo codeish english）：

def try_next_move(self, board):
    for each of the pegs in the board:
        if the peg can be moved:
            new_board = board with the peg moved
            if new_board is solved:
                return True
            if self.try_next_move(new_board):
                return True
            # That move didn't lead to a solution. Try the next.
    # No move  worked.
    return False
于 2010-01-26T06:11:42.497 に答える
0

アルゴリズムの基本的な問題は、このsucc関数が常に、特定のボードの状態に対して可能な動きを 1 つだけ生成することです。複数の可能な動きがある場合でも、succ関数は最初に見つけたものを返すだけです。深さ優先検索では、各状態で可能なすべての動きを処理する必要があります。

create_new_nodeは、その名前にもかかわらず、実際には新しいノードを作成するのではなく、既存のノードを変更するという事実から、さらなる問題が発生する可能性があります。前のノードを保持したい深さ優先検索の場合、この関数が実際にパラメーターとして取得したリストのコピーを作成した方がよいでしょう。

また、 で逆戻りする可能性をチェックするときはsucc、 の場合にのみそうしようとしますpos > 2。それはあまりにも限定的ですが、pos > 1大丈夫でしょう。

于 2010-01-26T06:19:56.823 に答える