0

プログラミング演習として、Pythonでパズルゲームを解こうとしています。このために、私は再帰的アルゴリズムを使用しています。これは、深さ優先探索の実装であると考えました。私の問題は、最大再帰制限に達するとランタイムエラーが発生し、それを解決する方法がわからないことです。

ゲームとアルゴリズムの両方についてさまざまな投稿を見てきましたが、この設定で再コーディングするのではなく、自分が書いたものについて役立つ洞察を得たいと思っていました。これが私のコードの疑似簡略化バージョンです。

# Keep track of paths that I have found for given states. 
best_paths = dict()

def find_path(state, previous_states = set()):

  # The output is a tuple of the length of the path and the path.
  if state in previous_states:
    return (infty,None)
  previous_states = copy and update with state

  if state in target_states: 
    best_paths[state] = (0,[])

  if state in best_paths:
    return best_paths[state]

  possible_moves = set((piece,spaces) that can be moved)
  (shortest_moves,shortest_path) = (infty,None)
  for (piece,spaces) in possible_moves:
    move_piece(piece,spaces)
    try_state = the resulting state after moving the piece
    (try_moves,try_path) = find_path(try_state,previous_states)

    if try_moves < shortest_moves:
      shortest_moves = try_moves + 1
      shortest_path  = try_path + [(piece,spaces)]

    # Undo the move for the next call
    move_piece(piece,-spaces)

  if shortest_moves < infty:
    best_paths[state] = shortest_path

  return (best_moves, shortest_path)

だから私の質問は、forループの外側に戻ると、再帰が最大になる原因は何ですか？
ご協力ありがとうございました。

    -
4

1 に答える 1

0

再帰の深さが例外を超えている場合は、コードに問題があるか、別のアルゴリズムが必要です。アルゴリズムはO（N * N）のようです。ここで、Nはノードの数です。制限に達するために、Nをそれほど大きくする必要はありません。

問題へのより良いアプローチがあります。

于 2012-08-15T14:17:28.410 に答える