Есть ли более эффективный алгоритм для расчета манхэттенского расстояния в игре с 8 головоломками?

Question

В настоящее время я пишу алгоритм, который решает игру из 8 головоломок с помощью алгоритма поиска A * с Python. Однако, когда я проверяю время выполнения кода, я обнаруживаю, что get_manhattan_distance занимает очень много времени.

Я запустил свой код с cProfile для Python, и результаты ниже того, что распечатывается программой. Вот суть для моей проблемы.

Я уже сделал свою программу более эффективной, копируя с помощью Numpy Arrays вместо списков Python. Я не совсем знаю, как сделать этот шаг более эффективным. Мой текущий код для get_manhattan_distance

def get_manhattan(self):
    """Returns the Manhattan heuristic for this board

    Will attempt to use the cached Manhattan value for speed, but if it hasn't 
    already been calculated, then it will need to calculate it (which is 
    extremely costly!).
    """
    if self.cached_manhattan != -1:
      return self.cached_manhattan

    # Set the value to zero, so we can add elements based off them being out of
    # place.
    self.cached_manhattan = 0

    for r in range(self.get_dimension()):
      for c in range(self.get_dimension()):
        if self.board[r][c] != 0:
          num = self.board[r][c]

          # Solves for what row and column this number should be in.
          correct_row, correct_col = np.divmod(num - 1, self.get_dimension())

          # Adds the Manhattan distance from its current position to its correct
          # position.
          manhattan_dist = abs(correct_col - c) + abs(correct_row - r)
          self.cached_manhattan += manhattan_dist

    return self.cached_manhattan

Идея, стоящая за этим, заключается в следующем: загадка цели для сетки 3x3 заключается в следующем:

 1  2  3
 4  5  6
 7  8 

Там, где есть пустая плитка (пустая плитка представлена ​​0 в массиве int). Итак, если у нас есть загадка:

 3  2  1
 4  6  5
 7  8   

У Манхэттена должно быть расстояние 6. Это потому, что 3 находится в двух местах от того места, где оно должно быть. 1 в двух местах от того, где он должен быть. 5 - одно место от того, где оно должно быть, а 6 - одно место от того, где оно должно быть. Следовательно, 2 + 2 + 1 + 1 = 6.

К сожалению, этот расчет занимает очень много времени, потому что существуют сотни тысяч различных плат. Есть ли способ ускорить этот расчет?

Answer 1

Мне кажется, вам нужно только рассчитать полную сумму Манхэттенского расстояния для всей доски один раз - для первой доски.После этого вы создаете новые Board сущности из существующих, меняя местами два соседних числа.Общее Манхэттенское расстояние на новой доске будет отличаться только суммой изменений Манхэттенского расстояния для этих двух чисел.

Если одно из чисел пустое (0), то общее расстояние изменяется наминус один или один в зависимости от того, переместилось ли непустое число ближе к правильному месту или дальше от него.Если оба числа непустые, как, например, при создании «двойников», общее расстояние изменяется на минус два, ноль или два.

Вот что я бы сделал: добавьте manhattan_distance = Noneаргумент Board.__init__.Если это не дано, рассчитайте общее расстояние Манхэттена от доски;в противном случае просто сохраните данное расстояние.Создайте свою первую доску без этого аргумента.Когда вы создаете новую доску из существующей, рассчитайте изменение общего расстояния и передайте результат на новую доску.(cached_manhattan становится неактуальным.)

Это должно немного уменьшить общее количество вычислений, связанных с расстоянием - я ожидал бы, что это ускорит процесс в несколько раз, чем больше размер вашей платы.