Моделирование графика в Python

Я пытаюсь решить проблему, связанную с графиками в Python. Поскольку у меня проблема с предсказуемым программированием, я не использую другие сторонние пакеты.

Задача представляет собой график в виде квадратной сетки 5 X 5. Предполагается, что бот находится в поставленном пользователем положении на сетке. Сетка индексируется в (0,0) в верхнем левом углу и (4,4) в правом нижнем углу. Каждая ячейка в сетке представлена любым из следующих трех символов. 'b (значение ascii 98) указывает текущую позицию ботов,' d (значение ascii 100) указывает на грязную ячейку, а '-' (значение ascii 45) указывает на чистую ячейку в сетке. Ниже приведен пример сетки, где бот находится в 0 0:

b---d
-d--d
--dd-
--d--
----d

Цель состоит в том, чтобы очистить все ячейки в сетке с минимальным количеством шагов. Шаг определяется как задача, в которой либо i) Бот меняет свое положение ii) Бот меняет состояние ячейки (от d до -)

Предположим, что изначально позиция, помеченная как b, не нуждается в очистке. Боту разрешено перемещать UP, DOWN, LEFT и RIGHT.

Мой подход

Я прочитал пару руководств по графикам и решил смоделировать график как матрицу смежности 25 X 25 с 0, не представляющую путей, и 1 представляющий пути в матрице (поскольку мы можем перемещаться только в 4 направлениях). Затем я решил применить Floyd Warshell к каждому парному алгоритму кратчайшего пути, а затем суммировать значения путей. Но у меня такое чувство, что это не сработает. Я уверен, что проблема заключается в следующем:

i) Минимальное связующее дерево (которое я не могу сделать, поскольку я не могу моделировать и хранить сетку в виде графика).

ii) A * Search (Опять дикая догадка, но та же проблема здесь, я не могу правильно моделировать сетку как график).

Я был бы признателен, если бы вы могли предложить хороший подход при таких проблемах. Кроме того, некоторые подсказки и psuedocode о различных формах проблем на основе графа (или ссылок на них) были бы полезны. Спасибо

Ответ 1

Думаю, вы задаете здесь два вопроса.

1. Как представить эту проблему в виде графика в Python?

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

# Code is untested and may contain typos. :-)

# A list of the (x, y) coordinates of all of the dirty squares.
dirty_squares = [(0, 4), (1, 1), etc.]
n = len(dirty_squares)    

# Everywhere after here, refer to dirty squares by their index
# into dirty_squares.

def compute_distance(i, j):
  return (abs(dirty_squares[i][0] - dirty_squares[j][0])
          + abs(dirty_squares[i][1] - dirty_squares[j][1]))

# distances[i][j] is the cost to move from dirty square i to
# dirty square j.
distances = []
for i in range(n):
  distances.append([compute_distance(i, j) for j in range(n)])

# The x, y coordinates of where the robot starts.
start_node = (0, 0)

# first_move_distances[i] is the cost to move from the robot's
# start location to dirty square i.
first_move_distances = [
  abs(start_node[0] - dirty_squares[i][0])
      + abs(start_node[1] - dirty_squares[i][1]))
  for i in range(n)]

# order is a list of the dirty squares.
def cost(order):
  if not order:
    return 0  # Cleaning 0 dirty squares is free.
  return (first_move_distances[order[0]]
          + sum(distances[order[i]][order[i+1]]
                for i in range(len(order)-1)))

Ваша цель - найти способ переупорядочить список (диапазон (n)), который минимизирует стоимость.

2. Как найти минимальное количество шагов для решения этой проблемы?

Как указывали другие, обобщенная форма этой проблемы неразрешима (NP-Hard). У вас есть две части информации, которые помогают ограничить проблему, чтобы сделать ее доступной:

График - это сетка.
Не более 24 грязных квадратов.

Мне нравится ваш инстинкт использовать A * здесь. Он часто хорош для решения проблем с поиском минимального числа перемещений. Однако A * требует достаточного количества кода. Я думаю, что вам лучше пойти с подходом "Разделение и привязка" (иногда называемым "Разделение и удаление" ), которое должно быть почти таким же эффективным, но гораздо проще реализовать.

Идея состоит в том, чтобы начать перечисление всех возможных решений с помощью поиска по глубине, например:

  # Each list represents a sequence of dirty nodes.
  []
  [1]
  [1, 2]
  [1, 2, 3]
  [1, 3]
  [1, 3, 2]
  [2]
  [2, 1]
  [2, 1, 3]

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

Если это недостаточно эффективно, добавьте функцию для вычисления нижней границы оставшейся стоимости. Тогда, если стоимость ([2]) + lower_bound (set ([1, 3])) дороже, чем самое дешевое решение, найденное до сих пор, вы можете пропустить всю ветку. Чем жестче lower_bound(), тем больше ветвей вы можете пропустить.

Ответ 2

Скажем V={v|v=b or v=d} и получим полный связный граф G(V,E). Вы можете рассчитать стоимость каждого ребра в E с временной сложностью O(n^2). Впоследствии проблема становится такой же, как: Начать в указанной вершине и найти кратчайший путь G, который охватывает V.

Мы называем это Проблема с коммивояжером (TSP) с 1832 года.

Ответ 3

Проблема может быть сохранена в виде графика. Стоимость между узлами (грязными ячейками) составляет их расстояние Манхэттена. Игнорируйте стоимость очистки ячеек, потому что общая стоимость будет одинаковой независимо от того, какой путь был сделан.

Ответ 4

Эта проблема выглядит как проблема Minimum Rectilinear Steiner Tree. К сожалению, проблема NP трудна, поэтому вам нужно придумать приближение (минимальное связующее дерево на основе расстояния Манхэттена), если я прав.