我本来试图为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个难题的不连续模式数据库提供一些提示。
提前感谢！
编辑：我发现了问题，当我从使用4行而不是一维字符串的15难题转换时，我设法弄乱了move函数。另外，我还搞砸了增加沿线某个州的成本。
这里是更新的工作代码，它将在我的计算机上在约15秒内生成8个拼图的完整数据库。
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())
似乎就像在移动功能direction中一样，仅提供potential_moves，并且图案相同。如果只是用
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函数，并将int列表转换为内联字符串。
用于移动，
pos = puzzle.index(0) + pm
这会使情况变得更糟。您也可以尝试删除所有puzzle_to_string函数调用，并将goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)替换为元组。然后通过在移动函数中处理它，方法是在分配之前转换为列表，然后在返回之前转换回元组。