8- Python中的拼图模式数据库

Question

我最初试图为15个拼图创建一个不相交(6-6-3)的模式数据库，但我一直在苦苦挣扎，以至于我首先尝试为8个拼图创建一个完整的模式数据库，这意味着我想要将8个拼图的所有可能排列保存到一个文件中，以便在尝试用A*算法解决这个难题时创建一个启发式方法。

8字谜的目标状态是1，2，3，4，5，6，7，8，0，其中0是空格。为了创建排列，我从目标状态使用广度优先搜索，并将每个排列保存为拼图状态和从目标状态到达它的成本(移动次数)的元组。

我的代码如下：

import math
import json
from collections import deque
from copy import deepcopy
from timeit import default_timer

# Goal state of the puzzle
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]


# Calculates the possible moves of the blank tile.
def get_moves(puzzle):
    # Lists potential moves in order: up, right, down, left.
    potential_moves = [-3, 1, 3, -1]

    # Checks which moves are possible.
    possible_moves = []
    for pm in potential_moves:
        pos = puzzle.index(0)
        pos += pm
        if pos in range(8):
            possible_moves += [pm]

    return possible_moves


# Moves the blank tile in the puzzle.
def move(puzzle, direction):
    # Creates a copy of the new_puzzle to change it.
    new_puzzle = deepcopy(puzzle)
    pos = puzzle.index(0)

    # Swaps blank tile with tile in direction.
    if direction == -3:
        new_puzzle[pos], new_puzzle[pos-3] = new_puzzle[pos-3], new_puzzle[pos]
    elif direction == 1:
        new_puzzle[pos], new_puzzle[pos+1] = new_puzzle[pos+1], new_puzzle[pos]
    elif direction == 3:
        new_puzzle[pos], new_puzzle[pos+3] = new_puzzle[pos+3], new_puzzle[pos]
    elif direction == -1:
        new_puzzle[pos], new_puzzle[pos-1] = new_puzzle[pos-1], new_puzzle[pos]

    return new_puzzle


# Transforms a puzzle to a string.
def puzzle_to_string(puzzle):
    string = ""
    for t in puzzle:
        string += str(t)

    return string


# Creates the database.
def create_database():
    # Initializes a timer, starting state, queue and visited set.
    begin = default_timer()
    start = goal
    queue = deque([[start, 0]])
    visited = set()
    visited.add((puzzle_to_string(start), 0))

    print("Generating database...")
    print("Collecting entries...")
    # BFS taking into account a state and the cost to reach it from the starting state.
    while queue:
        states = queue.popleft()
        state = states[0]
        cost = states[1]

        for m in get_moves(state):
            next_state = move(state, m)
            cost += 1

            if not any(s for s in visited if s[0] == puzzle_to_string(next_state)):
                queue.append([next_state, cost])
                visited.add((puzzle_to_string(next_state), cost))

        # Print a progress for every x entries in visited.
        if len(visited) % 10000 == 0:
            print("Entries collected: " + str(len(visited)))

        # Exit loop when all permutations for the puzzle have been found.
        if len(visited) >= math.factorial(9)/2:
            break

    print("Writing entries to database...")
    # Writes entries to the text file, sorted by cost in ascending order .
    with open("database.txt", "w") as f:
        for entry in sorted(visited, key=lambda c: c[1]):
            json.dump(entry, f)
            f.write("\n")

    end = default_timer()
    minutes = math.floor((end-begin)/60)
    seconds = math.floor((end-begin) % 60)
    return "Generated database in " + str(minutes) + " minute(s) and " + str(seconds) + " second(s)."


print(create_database())

现在，问题是填满条目(仍然)需要很长的时间，这可能是不应该的，因为8字谜只有9!/2 = 181440种可能的排列，所以应该可以相当快地创建一个完整的数据库。

我非常感谢对这个问题的任何形式的输入，如果可能的话，也会在为15个拼图创建不相交模式数据库的方向上提供一些提示。

提前感谢！

编辑:我发现了这个问题，当我从15行的拼图转换时，我设法弄乱了移动函数，它使用了4行而不是1维的字符串。此外，我还搞砸了在这条线上某处增加状态的成本。

下面是更新后的工作代码，它可以在我的机器上在15秒内生成完整的8-puzzle数据库。

import json
import math
from collections import deque
from copy import deepcopy
from timeit import default_timer

# Goal state of the puzzle
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]


# Calculates the possible moves of the blank tile.
def get_moves(puzzle):
    pos = puzzle.index(0)

    if pos == 0:
        possible_moves = [1, 3]
    elif pos == 1:
        possible_moves = [1, 3, -1]
    elif pos == 2:
        possible_moves = [3, -1]
    elif pos == 3:
        possible_moves = [-3, 1, 3]
    elif pos == 4:
        possible_moves = [-3, 1, 3, -1]
    elif pos == 5:
        possible_moves = [-3, 3, -1]
    elif pos == 6:
        possible_moves = [-3, 1]
    elif pos == 7:
        possible_moves = [-3, 1, -1]
    else:
        possible_moves = [-3, -1]

    return possible_moves


# Moves the blank tile in the puzzle.
def move(puzzle, direction):
    # Creates a copy of the new_puzzle to change it.
    new_puzzle = deepcopy(puzzle)
    pos = puzzle.index(0)
    # Position blank tile will move to.
    new_pos = pos + direction
    # Swap tiles.
    new_puzzle[pos], new_puzzle[new_pos] = new_puzzle[new_pos], new_puzzle[pos]

    return new_puzzle


# Creates the database.
def create_database():
    # Initializes a timer, starting state, queue and visited set.
    begin = default_timer()
    start = goal
    queue = deque([[start, 0]])
    entries = set()
    visited = set()

    print("Generating database...")
    print("Collecting entries...")
    # BFS taking into account a state and the cost (number of moves) to reach it from the starting state.
    while queue:
        state_cost = queue.popleft()
        state = state_cost[0]
        cost = state_cost[1]

        for m in get_moves(state):
            next_state = move(state, m)

            # Increases cost if blank tile swapped with number tile.
            pos = state.index(0)
            if next_state[pos] > 0:
                next_state_cost = [next_state, cost+1]
            else:
                next_state_cost = [next_state, cost]

            if not "".join(str(t) for t in next_state) in visited:
                queue.append(next_state_cost)

            entries.add(("".join(str(t) for t in state), cost))
            visited.add("".join(str(t) for t in state))

        # Print a progress for every x entries in visited.
        if len(entries) % 10000 == 0:
            print("Entries collected: " + str(len(entries)))

        # Exit loop when all permutations for the puzzle have been found.
        if len(entries) >= 181440:
            break

    print("Writing entries to database...")
    # Writes entries to the text file, sorted by cost in ascending order .
    with open("database.txt", "w") as f:
        for entry in sorted(entries, key=lambda c: c[1]):
            json.dump(entry, f)
            f.write("\n")

    end = default_timer()
    minutes = math.floor((end-begin)/60)
    seconds = math.floor((end-begin) % 60)
    return "Generated database in " + str(minutes) + " minute(s) and " + str(seconds) + " second(s)."


print(create_database())

Answer 1

似乎在move函数中，direction只提供了potential_moves和pattern是相同的。它可以帮助用just替换所有其他的东西，

tmp = pos + direction 
new_puzzle[pos], new_puzzle[tmp] = new_puzzle[tmp], new_puzzle[pos]

使用预先计算的值，math.factorial(9)/2外部循环与位移位。您可以将函数内容移入循环本身并删除函数调用。https://nyu-cds.github.io/python-performance-tips/04-functions/

删除puzzle_to_string函数并将整型列表转换为字符串内联。

在get动作中使用，

pos = puzzle.index(0) + pm

这可能会让情况变得更糟。您还可以尝试删除所有puzzle_to_string函数调用，并将goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)替换为元组。然后在move函数中通过在赋值前转换为list并在返回前转换回tuple来处理它。