База данных шаблонов из 8 пазлов на Python
Первоначально я пытался создать непересекающуюся (6-6-3) базу данных шаблонов для головоломки 15, но я так много боролся, что сначала прибег к попытке создать полную базу данных шаблонов для головоломки 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 строки вместо одномерной строки. Вдобавок я еще где-то напортачил, увеличивая стоимость состояний.
Вот обновленный рабочий код, который генерирует полную базу данных для 8-головоломки за ~15 секунд на моей машине.
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())
1 ответ
Похоже в функции перемещения directionобеспечивает только потенциальные_движения, и шаблон такой же. Это могло бы помочь заменить все остальное на просто,
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 function и Convert int list to string inline.
Используйте в ходах,
pos = puzzle.index(0) + pm
Это могло сделать еще хуже. Вы также можете попробовать удалить всеpuzzle_to_string вызовы функций и замена goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)как кортеж. Затем обработайте его в функции перемещения, преобразовав в список перед назначением и преобразовав обратно в кортеж перед возвратом.