6

よく知られているスライディング パズルのさまざまな可能な状態を持つツリーを作成しようとしています。

わからない場合は、次のようなものです。

[3 5 2]
[4   1]
[8 6 7]

このようにする必要がある場所：

[1 2 3]
[4 5 6]
[7 8  ]

基本的に、空白をどのように移動できるか (上、下、左、または右) に応じて、すべての状態が新しい状態を生成します。

私が望むのは、パズルの初期状態としてルートを指定してすべての状態でツリーを作成することですが、ツリーに子 (新しい状態) を追加するときは、その状態がツリーのどこにも追加されていないことを確認する必要があります。

それを達成するのを手伝ってくれませんか？前もって感謝します ：）

これがスローする現在のコードですRecursionError: maximum recursion depth exceeded while calling a Python object

ノード クラス:

class Node(object):
    def __init__(self, value, parent=None):
        self.parent = parent
        self.value = value
        self.children = []

    def append(self, obj):
        if obj is not self.parent and obj not in self.children and obj is not None:
            self.children.append(obj)

    def has_children(self):
        return len(self.children) > 0

    def __iter__(self):
        yield self.value
        for v in chain(*map(iter, self.children)):
            yield v

    def find_root(self):
        p = self
        while p.parent is not None:
            p = p.parent
        return p

木の生成方法（selfパズル状態と考える）：

def to_tree(self, parent=None):
        values = []
        if parent is not None:
            for child in parent.find_root():
                values.append(child)

        value = nd.Node(self, parent)

        if value not in values:
            children = [move[1].to_tree(value) for move in self.get_possible_movements()]
            for child in children:
                if child is not None:
                    value.append(child)
            return value
        else:
            return None
4

2 に答える 2

2

あなたの進歩を妨げているものに答えてみます。

RecursionError: maximum recursion depth exceeded while calling a Python object

これは、「アクティブな」関数呼び出し (およびそのローカル状態) の数が制限を超えていることを意味します。その制限を上げようとすることもできますが (これはどこかで構成できると確信しています)、それを修正するための別のより一般的な手法があります。

疑似コードでは、ツリーを介した検索 (これはあなたがしていることのようです) は次のようになります。

find(predicate, node):
    if predicate(node):
        return node # found it
    for child in node.children:
        res = find(predicate, child):
        if res:
            return res # found it
    return false # not found

はpredicate、検索されたノードが見つかったかどうかを示すブール値を返す関数で、この検索を一般化します。

ここでの問題は、ツリーの高さによって、ご覧のとおり、再帰の制限を超える可能性があることです。この制限を回避する別のアプローチは、再帰を使用しないことです。一時的な状態をスタックに保存する代わりに、専用のコンテナーを構築します。

find(predicate, node):
    temp = [node]
    while not temp.empty():
        node = temp.pop()
        if predicate(node):
            return node # found it
        for child in temp.children:
            temp.push(child)
    return false # not found

ここで重要な点は、呼び出しの深さがtempコンテナーに移動することです。ただし、pushandpopの呼び出しの詳細を見てみましょう。なぜなら、それらが何をするのか完全に明確ではないからです。上記の再帰バージョンを模倣したい場合は、スタック (LIFO) を使用する必要があります。さらに、逆の順序で子をスタックにプッシュする必要がありますが、子の順序はおそらく無関係です。これは、最初の反復の後、指定されたノードのすべての直接の子がコンテナー内にあることを意味します。2 回目の反復では、1 つの直接の子が削除されて処理され、そのノードの子が追加されます。言い換えれば、検索は最初にツリーの深さまで行われるため、「深さ優先検索」(DFS) と呼ばれます。

これのバリエーションは、「幅優先検索」(BFS) と呼ばれます。そこでは、コンテナーとしてスタック (LIFO) の代わりにキュー (FIFO) を使用します。最初の反復後の状態は同じで、指定されたノードのすべての直接の子です。ただし、その後これらの子をチェックし、それらの子をコンテナーに追加しますが、すべての子がチェックされて初めて孫のチェックを開始します。

この非再帰的アプローチについて一言: これは、さらなる開発のベースとして採用すると、同時にもう少し柔軟になります。たとえば、同じノードに到達する方法が複数ある場合 (つまり、ツリーではない場合)、ループを回避するために、既に到達したすべての子を 2 番目のコンテナーに格納できます。もう 1 つの方法は、解決策からの距離に応じて子を並べて、利益をもたらさないパスをたどらないようにすることです。

一般に、再帰はめったに使用されないツールです。それを理解すること、特に数学における再帰的定義を理解することは確かに重要ですが、コーディングでそれを使用することはしばしば非現実的です。異なる考え方をする人もいるでしょうが、これは確固たる主張というよりも意見に過ぎませんが、それを裏付けるために経験と成功を後押しすることはできます.

于 2018-03-13T06:33:16.463 に答える
1

最大再帰深度を超えることに加えて、実装が無限ループを生成している可能性もあります。リストのスコープはvalues各呼び出しにローカライズされるためto_tree、状態が既に訪問されている場合に検索するための中心的な場所はありません。これは、4 * 9 = 36 ビット整数に適合するパズル状態のビット表現を使用した、スタックベースの反復の例です。例えば：

123
456
780

次のように表されます。

0001 0010 0011
0100 0101 0110
0111 1000 0000

しかし、逆に連鎖:

   0|   8|   7|   6|   5|   4|   3|   2|   1
0000 1000 0111 0110 0101 0100 0011 0010 0001

0b000010000111011001010100001100100001
=> 2271560481

initialState()
=> 2271560481

状態を作成して表示する関数をいくつか追加しましょう。

from sys import stdout

def showState(state):
  mask = 15

  for i in xrange(9):
    if i % 3 == 0 and i > 0:
      stdout.write("\n")
    stdout.write(str((state & mask) >> 4 * i))
    mask = mask << 4

  stdout.write("\n")


def makeState(arr):
  state = 0

  for i in xrange(9):
    state = state | (arr[i] << 4 * i)

  return state


def initialState():
  return makeState([1,2,3,4,5,6,7,8,0])

次に、ゼロのインデックスを見つける必要があります。

def findZero(state):
  mask = 15
  i = 0

  while mask & state:
    mask = mask << 4
    i = i + 1

  return i

隣接する数字をゼロのセルに移動します。

def move(state, fromIdx, toIdx):
  x = (state & (15 << 4 * fromIdx)) >> 4 * fromIdx
  state = state & (2**36 - 1 ^ (15 << 4 * fromIdx) ^ (15 << 4 * toIdx))
  state = state | (x << 4 * toIdx)

  return state


def moves(idx):
  # 012
  # 345
  # 678
  return [
    [1,3], [0,2,4], [1,5],
    [0,4,6], [1,3,5,7], [2,4,8],
    [3,7], [4,6,8], [5,7]
  ][idx]

使用している Node クラスのバージョンを追加しましょう。 

class Node(object):
  def __init__(self, state, parent=None):
    self.parent = parent
    self.state = state
    self.children = []

  def append(self, obj):
    self.children.append(obj)

ルートとグローバル オブジェクト を設定します。states_to_nodesこれは、訪問した状態を、その状態を値として保持するノードにマップします。

root = Node(initialState())
states_to_nodes = {initialState(): root}

最大再帰深度エラーを回避するスタックベースの反復は次のとおりです。

stack = [root]

while stack:
  node = stack.pop()
  zero_index = findZero(node.state)

  for i in moves(zero_index):
    maybe_new_state = move(node.state, i, zero_index)

    if not maybe_new_state in states_to_nodes:
      new_node = Node(maybe_new_state)
      states_to_nodes[maybe_new_state] = new_node
      node.append(new_node)

      stack.append(new_node)

    else:
      node.append(states_to_nodes[maybe_new_state])

出力：

example_state = makeState([5,1,3,8,6,0,2,7,4])

print "Example state:\n"
showState(example_state)

print "\nChildren states:\n"

for child in states_to_nodes[example_state].children:
  showState(child.state)
  print

"""
Example state:

513
860
274

Children states:

510
863
274

513
806
274

513
864
270
"""
于 2018-03-17T14:07:59.970 に答える