# Как я могу ускорить мой алгоритм IDA * для N-puzzle?

Я пытаюсь решить проблему N-Puzzle, используя алгоритм IDA * с эвристикой Manhattan. Я уже реализовал алгоритм из псевдокода на этой странице Википедии (связь).

Вот мой код:

``````class Node():
def __init__(self, state, manhattan):
self.state = state
self.heuristic = manhattan

def __str__(self):
return f"state=n{self.state}nheuristic={int(self.heuristic)}"

def __eq__(self, other):
return np.array_equal(self.state, other.state)

def customSort(node):
return node.heuristic

def nextnodes(node):
zero = np.where(node.state == 0)

y,x = zero
y = int(y)
x = int(x)

directions = []
if y > 0:
directions.append((y - 1, x))
if x > 0:
directions.append((y, x - 1))
if y < constant.SIZE2 - 1:
directions.append((y + 1, x))
if x < constant.SIZE2 - 1:
directions.append((y, x + 1))

arr = []
for direction in directions:
tmp = np.copy(node.state)
goal = np.where(constant.GOAL_STATE == tmp[direction])

tmp[direction], tmp[zero] = tmp[zero], tmp[direction]

tile1_score = manhattan_distance(direction, goal)
tile2_score = manhattan_distance(zero, goal)

arr.append(Node(tmp, node.heuristic - tile1_score + tile2_score))

arr.sort(key=customSort)

return arr

def manhattan_distance(a, b):
return abs(b[0] - a[0]) + abs(b[1] - a[1])

def count_distance(number, state1, state2):
position1 = np.where(state1 == number)
position2 = np.where(state2 == number)

return manhattan_distance(position1, position2)

def manhattan_heuristic(state):
distances = [count_distance(num, state, constant.GOAL_STATE) for num in constant.SIZE]
return sum(distances)

def search(path, g, threshold):
node = path[-1]
f = g + node.heuristic

if f > threshold:
return f
if np.array_equal(node.state, constant.GOAL_STATE):
return True

minimum = float('inf')
for n in nextnodes(node):
if n not in path:
path.append(n)
tmp = search(path, g + 1, threshold)
if tmp == True:
return True
if tmp < minimum:
minimum = tmp
path.pop()

return minimum

def solve(initial_state):path = solve(initial_state)
initial_node = Node(initial_state, manhattan_heuristic(initial_state))
threshold = initial_node.heuristic

path = [initial_node]

while 1:
tmp = search(path, 0, threshold)
if tmp == True:
print(f"GOOD!")
return path
elif tmp == float('inf'):
print(f"WRONG!")
return False
threshold = tmp
``````

Вы можете позвонить в `solve()` функцию (и создайте необходимые глобальные переменные) следующим образом:

``````def define_goal_state(n):
global GOAL_STATE
global SIZE
global SIZE2
global ZERO

m = [[0] * n for i in range(n)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
x, y, c = 0, -1, 1
for i in range(n + n - 2):
for j in range((n + n - i) // 2):
x += dx[i % 4]
y += dy[i % 4]
m[x][y] = c
c += 1

GOAL_STATE = np.array(m)
SIZE = range(1, len(GOAL_STATE) ** 2)
SIZE2 = len(GOAL_STATE)
ZERO = np.where(GOAL_STATE == 0)

initial_state = np.array([8 7 3],[4 1 2],[0 5 6])
define_goal_state(len(initial_state))
path = solve(initial_state)

``````

Моя реализация псевдокода Википедии работает, и я получаю довольно быстрые результаты в задаче 8-Puzzle. Но это становится очень медленным с задачей из 15 головоломок и выше. Взяв во внимание `solve()` и `search()` функции, я думаю, я почти идентично уважаю псевдокод. Я также оптимизировал свой `nextnodes()` функция подсчета только плитки, которая была перемещена, а не всех плиток каждый раз. Здесь должно быть хорошо.

Так в чем же подвох? Почему моя реализация занимает так много времени? У кого-нибудь есть ключ ?

## 1 ответ

Код не компилируется как есть:

• В `solve` подпись функции содержит ненужный код
``````def solve(initial_state):path = solve(initial_state)
``````
• Массив NumPy не может быть инициализирован как `np.array([8 7 3],[4 1 2],[0 5 6])`
• Глобалы не инициализируются
• `constant.GOAL_STATE` не определено

## Рассмотрение

• В методе `search`, проверка `if n not in path` — дорогостоящая операция, которую можно оптимизировать с помощью набора или словаря. Это снижает время выполнения на моей машине на 70%. Словарь кажется хорошим вариантом, поскольку он сохраняет порядок вставки (если Python> = 3.7) и может использоваться в качестве очереди.
• `manhattan_heuristic` использует много раз `np.where`, его можно оптимизировать. Можно выполнить итерацию по головоломке, и когда элемент отличается от цели, вычислить разницу. Преобразование `GOAL_STATE` в словарь также улучшит производительность, вместо вызова `position1 = np.where(state1 == number)` каждый раз.
• `nextnodes` также использует `np.where` два раза, которых можно избежать. Например, вместо звонка `zero = np.where(node.state == 0)` каждый раз, `Node` может содержать нулевые координаты как свойство класса.
• Именование: Переменная `SIZE` и `SIZE2` сбивают с толку, потому что один — генератор, а другой — размер головоломки. Подумайте о том, чтобы давать более значимые имена.
• Глобалы: постарайтесь максимально сократить использование глобальных переменных, так как это затрудняет тестирование кода.

Примечание: это не исчерпывающий обзор, я думаю, что еще есть возможности для улучшения, надеюсь, вы получите больше отзывов.

Время выполнения после доработок:

ГоловоломкаОригиналУлучшенный
3 х 30,696 с0,097 с
4×47,021 с0,549 с

## Переработанный код:

``````from time import perf_counter as pc

import numpy as np

GOAL_STATE = [[]]
GLOBAL_STATE_DICT = {}
N = 0

class Node:
def __init__(self, state, manhattan, zero_pos):
self.state = state
self.heuristic = manhattan
self.zero_pos = zero_pos

def __str__(self):
return f"state=n{self.state}nheuristic={int(self.heuristic)}"

def __eq__(self, other):
return np.array_equal(self.state, other.state)

def __repr__(self):
return f"state=n{self.state}nheuristic={int(self.heuristic)}"

def __hash__(self):
return hash(self.state.tobytes())

def customSort(node):
return node.heuristic

def nextnodes(node):
zero = node.zero_pos

r, c = map(int, zero)
directions = ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1))
nodes = []
for direction in directions:
if 0 <= direction[0] < N and 0 <= direction[1] < N:
tmp = np.copy(node.state)
goal = GLOBAL_STATE_DICT[tmp[direction]]

tmp[direction], tmp[zero] = tmp[zero], tmp[direction]

dir_goal_distance = manhattan_distance(direction, goal)
goal_zero_distance = manhattan_distance(goal, (r, c))

nodes.append(Node(tmp, node.heuristic - dir_goal_distance + goal_zero_distance, direction))
return sorted(nodes, key=customSort)

def manhattan_distance(a, b):
return abs(b[0] - a[0]) + abs(b[1] - a[1])

def manhattan_heuristic(state):
distance = 0
for i in range(N):
for j in range(N):
num = state[i][j]
if num != GOAL_STATE[i][j] and num != 0:
goal = GLOBAL_STATE_DICT[num]
distance += manhattan_distance((i, j), goal)
return distance

def search(path, g, threshold):
node = list(path.keys())[-1]

f = g + node.heuristic

if f > threshold:
return f
if np.array_equal(node.state, GOAL_STATE):
return True

minimum = float('inf')
for n in nextnodes(node):
if n not in path:
path[n] = None
tmp = search(path, g + 1, threshold)
if tmp == True:
return True
if tmp < minimum:
minimum = tmp
path.popitem()

return minimum

def solve(initial_state):
zero = np.where(initial_state == 0)
initial_node = Node(initial_state, manhattan_heuristic(initial_state), zero)
threshold = initial_node.heuristic
# The dictionary keeps insertion order since Python 3.7 so it can be used as a queue
path = {initial_node: None}
while 1:
tmp = search(path, 0, threshold)
if tmp == True:
print("GOOD!")
return path.keys()
elif tmp == float('inf'):
print("WRONG!")
return False
threshold = tmp

def define_goal_state(n):
global GOAL_STATE
global N
global GLOBAL_STATE_DICT

m = [[0] * n for i in range(n)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
x, y, c = 0, -1, 1
for i in range(n + n - 2):
for j in range((n + n - i) // 2):
x += dx[i % 4]
y += dy[i % 4]
m[x][y] = c
c += 1

GOAL_STATE = np.array(m)
N = len(GOAL_STATE)
GLOBAL_STATE_DICT = {m[r][c]: (r, c) for r in range(N) for c in range(N)}

tests = {'3x3': np.array([[8, 7, 3], [4, 1, 2], [0, 5, 6]]),
'4x4': np.array([[13, 2, 10, 3],
[1, 12, 8, 4],
[5, 0, 9, 6],
[15, 14, 11, 7]])}

for name, puzzle in tests.items():
define_goal_state(len(puzzle))
print('Puzzle:n', puzzle)
t0 = pc()
path = solve(puzzle)
t1 = pc()
print(f'{name} depth:{len(path)} runtime:{round(t1 - t0, 3)} s')

``````