Как я могу ускорить мой алгоритм 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() функция подсчета только плитки, которая была перемещена, а не всех плиток каждый раз. Здесь должно быть хорошо.

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

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

• В 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 сбивают с толку, потому что один — генератор, а другой — размер головоломки. Подумайте о том, чтобы давать более значимые имена.
• Глобалы: постарайтесь максимально сократить использование глобальных переменных, так как это затрудняет тестирование кода.

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

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

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

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')