Я работаю над проектом для моего университета, в котором мы должны запрограммировать машины Le go Mindstorms, чтобы исследовать вершины и ребра больших неориентированных графов, размещенных на полу. Для части проекта мы должны реализовать алгоритм кратчайшего пути, чтобы транспортное средство могло успешно пройти кратчайший путь от начальной вершины до целевой вершины на графике. Я выбрал алгоритм Дейкстры для своей реализации. Я попытаюсь объяснить свою проблему и то, как код и структуры данных функционируют максимально кратко, не упуская ничего важного.
Каждый график сохраняется в словаре, в котором ключи являются кортежами, представляющими координаты вершины графа. Каждое значение представляет собой словарь, который в свою очередь имеет максимум четыре клавиши, по одной для каждого направления компаса. Внутренние словари представляют ребра, которые простираются от каждой вершины / ключа. Значения внутреннего словаря представляют собой 3 кортежа, которые содержат направление компаса, из которого ребро входит в соседнюю вершину, координаты соседней вершины и вес ребра. Например, пара ключ-значение для вершины в точке (0, 3) с ребрами, простирающимися от нее на север и восток, может выглядеть так:
(0, 3): {
Direction.NORTH: ((0, 3), Direction.WEST, 1),
Direction.EAST: ((1, 3), Direction.WEST, 2)
}
Ее сосед в точке (1, 3) может выглядело это так:
(1, 3): {
Direction.WEST: ((0, 3), Direction.EAST, 2)
}
Моя проблема в том, что по какой-то причине я создаю экземпляр класса графа (называемый "Pl anet") в новом файле и запускаю в нем функцию shorttest_path. файл, он возвращает правильный ответ. Но если я создаю тот же самый график в файле, который был настроен для наших модульных тестов, а затем запускаю функцию, он не работает. Ниже моя реализация алгоритма Дейкстры:
def shortest_path(self, start: Tuple[int, int], target: Tuple[int, int]) -> Union[None, List[Tuple[Tuple[int, int], Direction]]]:
"""
Returns a shortest path between two nodes
Examples:
shortest_path((0,0), (2,2)) returns: [((0, 0), Direction.EAST), ((1, 0), Direction.NORTH)]
shortest_path((0,0), (1,2)) returns: None
:param start: 2-Tuple
:param target: 2-Tuple
:return: 2-Tuple[List, Direction]
"""
# Initializes the data structures necessary for Dijkstra's algorithm, calls the dijkstra_loop function, and then
# returns its result.
unvisited = {}
current_node = start
precursor_compass_dict = {}
shortest_path = []
for node in self.paths_from_nodes.keys():
if node is start:
unvisited[node] = 0
else:
unvisited[node] = math.inf
self.dijkstra_loop(start, unvisited, current_node, precursor_compass_dict, target, shortest_path)
return shortest_path
def dijkstra_loop(self, start: Tuple[int, int], unvisited: Dict, current: Tuple[int, int], precursor_compass: Dict,
target, shortest: List):
# Checks which unvisited nodes are neighbors of the current node, adds the weight of the path through the
# current node to the weight of the edge that leads to the respective neighbor, and changes the distance of the
# neighbor to this sum if the sum is smaller than the neighbor's current distance.
for (node, distance) in unvisited.items():
items = self.paths_from_nodes[current].items()
for (direction, path) in items:
if node in path:
neighbor_weight = path[2]
if unvisited[current] + neighbor_weight < distance:
distance = unvisited[current] + neighbor_weight
unvisited[node] = distance
precursor_compass[node] = (current, direction)
# Marks the current node as visited once the distances of all of its neighbors have been considered and, if
# necessary, recalculated.
unvisited.pop(current)
# Constructs and returns the shortest path if the target node has been marked as visited. Otherwise, finds the
# unvisited node with the lowest distance, changes the current node to this node, and calls dijkstra_loop again
# with the new parameter values.
if target not in unvisited:
if target in self.paths_from_nodes and target not in precursor_compass
print("Target is not reachable")
return
else:
shortest.append(precursor_compass[target])
for (coord, direc) in shortest:
if coord != start:
shortest.append(precursor_compass[coord])
return shortest.reverse()
else:
for (node, distance) in unvisited.items():
if distance is min(unvisited.values()):
current = node
self.dijkstra_loop(start, unvisited, current, precursor_compass, target, shortest)
По сути, после инициализации необходимых структур данных функция вызывает рекурсивную вспомогательную функцию, которая выполняет большую часть работы. Вспомогательная функция проверяет, какие не посещенные вершины являются соседями текущей вершины, и при необходимости изменяет их предполагаемые расстояния. Затем текущая вершина обновляется, и функция вызывает себя снова и так до тех пор, пока целевой узел не будет отмечен как посещенный.
Моя идея для возврата правильного результата состояла в том, чтобы создать словарь (precursor_compass), в котором каждый ключ является вершина и каждое значение - это кортеж, который содержит вершину-предшественник этой вершины (т. е. вершину, которая должна идти перед ней по кратчайшему пути) и направление компаса, из которого ребро покидает вершину-предшественник.
В if- блок для «если цель не в невидимом», кратчайший путь инициализируется из этого словаря, начиная с целевой вершины и затем работая в обратном направлении. Затем результат инвертируется (чтобы путь не был обратным) и возвращался.
Если кто-то захочет посмотреть, как я инициализирую графики, вот этот код:
def add_path(self, start: Tuple[Tuple[int, int], Direction], target: Tuple[Tuple[int, int], Direction],
weight: int):
"""
Adds a bidirectional path defined between the start and end coordinates to the map and assigns the weight to it
Example:
add_path(((0, 3), Direction.NORTH), ((0, 3), Direction.WEST), 1)
:param start: 2-Tuple
:param target: 2-Tuple
:param weight: Integer
:return: void
"""
# Assigns parameters to the path that is to be added to the planet.
new_path = Path(start[0], target[0], weight, start[1], target[1])
# Checks if the start coordinate of the new path is already a key in the planet dictionary. If so, adds the new
# path to the value dictionary of the start coordinate. Otherwise, adds the start coordinate to the planet
# dictionary as a key and then adds the new path to the value dictionary of the start coordinate.
if new_path.start in self.paths_from_nodes.keys():
self.paths_from_nodes[new_path.start].update(
{new_path.start_dir: (new_path.target, new_path.end_dir, new_path.weight)})
else:
self.paths_from_nodes[new_path.start] = {}
self.paths_from_nodes[new_path.start].update(
{new_path.start_dir: (new_path.target, new_path.end_dir, new_path.weight)})
if new_path.target in self.paths_from_nodes.keys():
self.paths_from_nodes[new_path.target].update(
{new_path.end_dir: (new_path.start, new_path.start_dir, new_path.weight)})
else:
self.paths_from_nodes[new_path.target] = {}
self.paths_from_nodes[new_path.target].update(
{new_path.end_dir: (new_path.start, new_path.start_dir, new_path.weight)})
Следующий код создает простой квадратный граф и вычисляет кратчайший путь между (0, 0) и (2, 2):
from planet import Planet, Direction
p = Planet()
p.add_path(((0, 0), Direction.EAST), ((2, 0), Direction.WEST), 2)
p.add_path(((0, 0), Direction.NORTH), ((0, 2), Direction.SOUTH), 1)
p.add_path(((0, 2), Direction.EAST), ((2, 2), Direction.WEST), 4)
p.add_path(((0, 2), Direction.SOUTH), ((0, 0), Direction.NORTH), 1)
p.add_path(((2, 2), Direction.WEST), ((0, 2), Direction.EAST), 4)
p.add_path(((2, 2), Direction.SOUTH), ((2, 0), Direction.NORTH), 2)
p.add_path(((2, 0), Direction.NORTH), ((2, 2), Direction.SOUTH), 2)
p.add_path(((2, 0), Direction.WEST), ((0, 0), Direction.EAST), 2)
p.add_path(((1, 2), Direction.WEST), ((1, 2), Direction.NORTH), 1)
p.add_path(((1, 2), Direction.NORTH), ((1, 2), Direction.WEST), 1)
print(p.shortest_path((0, 0), (2, 2)))
И возвращает, если не выполняется в модульных тестах, следующий результат:
[((0, 0), <Direction.EAST: 90>), ((2, 0), <Direction.NORTH: 0>)]
В заключение: благодаря моим собственным попыткам отладки я узнал, что если я запускаю модульное тестирование для алгоритма, словарь precursor_compass будет пустым в конце алгоритма, и функция возвращает пустой список для кратчайшего пути между (0, 0) и (2, 2). Ни одна из этих вещей не должна происходить, и, как упоминалось выше, ни одна из них не происходит, если я запускаю функцию в отдельном файле вне модульных тестов. При необходимости я могу предоставить некоторый код из модульных тестов, но я подумал, что было бы лучше подождать и посмотреть, понравится ли мне кто-нибудь, так как это уже очень долго. Спасибо за чтение, и я был бы очень признателен за любые предложения!