时间戳

首页 > 解决方案 > 移动功能不适用于 N-Puzzle 问题

python - 移动功能不适用于 N-Puzzle 问题

问题描述

我正在尝试为一个 n-puzzle 问题制作一个 IDDFS 算法。但是，移动功能无法正常工作。它将输出下一步，但会更改前一个（参数）的值。任何有关如何防止这种情况发生的建议将不胜感激:)

def move_blank(i, j, n):
    if i + 1 < n:
        yield i + 1, j
    elif i - 1 >= 0:
        yield i - 1, j
    elif j + 1 < n:
        yield i, j + 1
    elif j - 1 >= 0:
        yield i, j - 1


def move(state):
    [i, j, grid] = state
    n = len(grid)
    for pos in move_blank(i, j, n):
        i1, j1 = pos
        grid[i][j], grid[i1][j1] = grid[i1][j1], grid[i][j]
        yield [i1, j1, grid]
        grid[i][j], grid[i1][j1] = grid[i1][j1], grid[i][j]


def is_goal(state, goal):
    return state == goal


def dfs_rec(puz, goal):
    if is_goal(puz[-1], goal):
        return puz
    else:
        for next_state in move(puz[-1]):
            if next_state not in puz:
                next_path = puz + [next_state]
                solution = dfs_rec(next_path, goal)
                if solution != None:
                    return solution
    return None

goal = [0, 2, [[3, 2, 0], [6, 1, 8], [4, 7, 5]]]
test = [0, 0, [[0, 7, 1], [4, 3, 2], [8, 6, 5]]]
path = dfs_rec([test], goal)

标签： pythonalgorithm

解决方案

The problem is in move_blank. The generated moves are not mutually exclusive, yet only one of them will be generated. Replace all elifs with a simple if:

def move_blank(i, j, n):
    if i + 1 < n:
        yield i + 1, j
    if i - 1 >= 0:
        yield i - 1, j
    if j + 1 < n:
        yield i, j + 1
    if j - 1 >= 0:
        yield i, j - 1

There are other, less critical, issues with implementation:

  • if next_state not in puz is awfully expensive. Enumerating states and storing their id in a set would be much better (there are 362k states for an 8-puzzle, list lookup is faster than set only up to ~30 elements)
  • reliance on mutable arguments isn't a good practice. No immediate issues here but it might bite when you don't expect. Storing state as a 9-tuple would fix this and the previous concern.
  • solution = dfs_rec(next_path, goal) This problem is solvable and would be much cheaper without recursion. Yes, wikipedia pseudocode is not optimal.
  • it is not IDDFS - there is no depth limit per iteration

推荐阅读