Ответ 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(), тем больше ветвей вы можете пропустить.