Как реализовать пропуск соседних узлов в модифицированном алгоритме Дейкстры ⇐ Python

[Anonymous]

Предположим, у нас есть связный взвешенный MultiDiGraph G, представляющий здание, каждый узел представляет комнату в здании, а каждое ребро, соединяющее пару узлов, представляет собой прямую связь между комнатами (через коридор, лестницу или лифт). Я хочу найти кратчайший путь между любыми двумя комнатами, используя алгоритм Дейкстры.
Веса, связанные с соединением типа «прихожая», являются константами, поэтому их легко обрабатывать, используя обычные Дейкстра.
Однако веса, связанные с соединением типа «лестница» и «лифт», зависят от количества этажей, на которые нам нужно подняться. В моем случае я поставил:

Код: Выделить всё

weight_elevator = 1.5*np.sqrt(x) #follows a root function

и Weight_Stairway = (1/2)*x**2 #следует полиномиальной функции, где x — количество этажей.
Дейкстра работает, проверяя каждый соседей узла и выбирая ближайшего соседа, и, повторяя этот локально оптимальный выбор, он может найти глобальный кратчайший путь.
Я хотел бы знать, можно ли написать модифицированный алгоритм Дейкстры, который :

• определяет тип кромки (легко)
• если тип кромки = 'прихожая', выполните обычную Дейкстру (просто)
• если тип края != 'прихожая' (то есть либо 'лестница', либо 'лифт'), 'перескакивает' на целевой этаж, вычисляет оба веса для 'лестницы' ' и "лифт" и выбирает лучший вариант (у меня возникли проблемы с "пропуском")

Например, пусть G быть nx.grid_graph(dim=(3,3,4)) с узлами: [a0, b0, ..., h3, i3]

• (один из) кратчайших путей от a0 до b3: (a0 -> b0 через коридор, b0 -> b3 через лифт)
• (один из) кратчайших путь от c1 до e2 будет: (c1 -> f1 с использованием коридора, f1 -> e1 с использованием коридора, e1 -> e2 с использованием лестницы)
  Использование обычного алгоритма Дейкстры для 1 дало бы мне (a0 -> b0 коридор, лестница b0->b1, лестница b1->b2, лестница b2->b3), которая на самом деле не оптимизирована...

Код: Выделить всё

#setting up the graph, I made an adjacency matrix first then created the graph with it
import networkx as nx
import numpy as np
from itertools import count
from heapq import heappush, heappop

room_names = ['000','010','020','100','110','120','200','210','220','001','011','021','101','111','121','201','211','221','002','012','022','102','112','122','202','212','222','003','013','023','103','113','123','203','213','223']
mx = np.zeros((len(room_names),len(room_names)), dtype=int) #adjacency matrix
weight = {} #empty weight dict
label = {} #empty label dict
for i in range(len(room_names)):
room = np.zeros(len(room_names)) #adjacencies of one room
for j in range(len(room_names)):
if room_names[i] == room_names[j]:
room[j] = 0 #same room
elif room_names[i][:2] == room_names[j][:2] and abs(int(room_names[i][-1]) - int(room_names[j][-1])) == 1: #same xy coordinates, one floor difference
room[j] = 2
weight[(room_names[i], room_names[j], 0)] = "stairway"  #edge name + key
weight[(room_names[i], room_names[j], 1)] = "elevator"
elif room_names[i][-1] == room_names[j][-1] and room_names[i][0] == room_names[j][0] and abs(int(room_names[i][1]) - int(room_names[j][1])) == 1: #same floor, same row, one column difference
room[j] = 1
weight[(room_names[i], room_names[j], 0)] = "west-east hallway"
elif room_names[i][-1] == room_names[j][-1] and room_names[i][1] == room_names[j][1] and abs(int(room_names[i][0]) - int(room_names[j][0])) == 1: #same floor, same column, one row difference
room[j] = 1
weight[(room_names[i], room_names[j], 0)] = "north-south hallway"
else:
room[j] = 0
label[i] = room_names[i]
mx[i] = room

graph = nx.from_numpy_array(mx, parallel_edges=True, create_using=nx.MultiDiGraph, edge_attr=False)
nx.relabel_nodes(graph, label, copy=False)
nx.set_edge_attributes(graph, weight, name="type")

Код: Выделить всё

def flat_weight(G, d, a):
"""returns weight for same floor edge with G and the two endpoints of the edge as input"""
fweight = 0
if G.get_edge_data(d, a, 0)['type'] == "west-east hallway":
fweight = 25
elif G.get_edge_data(d, a, 0)['type'] == "north-south hallway":
fweight = 20
else:
raise ValueError("not on the same floor")
return fweight

def vertical_weight(G, d, a):
"""returns weight for bunch of vertical edges with the same xy coordinates"""
vweight = {}
floors = abs(int(a[-1]) - int(d[-1])) #floors to climb/descend
if d[0:2] == a[0:2] and d[-1] != a[-1]:
vweight["elevator"] = 1.5*np.sqrt(floors)
vweight["stairway"] = (1/2)*floors**2
else:
raise ValueError("xy coordinates not the same")
return vweight`

Я попытался скопировать и вставить существующие функции Дейкстры (в основном те, которые есть в исходном коде NetworkX) и изменить часть, в которой они вычисляют стоимость (начальная строка 74 в _dijkstra_multisource(), та же самая отправная точка в других функциях dijkstra), но мне не удалось выяснить что-то, что дает мне то, что я хочу.
Измененный код в ячейке ниже обрамлен """vvv" "", """^^^""".

Код: Выделить всё

def path_copy(G, sources, pred=None, cutoff=None, target=None):
"""copy of nx._dijkstra_multisource() with modification"""
G_succ = G._adj #dict (nodes) of dict (edges for each node) of dict (edge keys) of dict (weight = type) of G # For speed-up (and works for both directed and undirected graphs)

"""vvv"""
flatw = flat_weight #weight function for flat edge
vertw = vertical_weight #weight function for vertical edge
"""^^^"""
push = heappush #Push item onto heap, maintaining the heap invariant.
pop = heappop #Pop the smallest item off the heap, maintaining the heap invariant.
dist = {} #dictionary of final distances
seen = {} #dict of visited nodes : dist to source
paths = {source:[source] for source in sources}
# fringe is heapq with 3-tuples (distance,c,node)
# use the count c to avoid comparing nodes (may not be able to)
c = count() #Return a count object whose .__next__() method returns consecutive values.
fringe = [] #empty list for heapq
for source in sources:
seen[source] = 0 #distance to source = 0
push(fringe, (0, next(c), source)) #fringe = [(distance = 0, next c, node = source)]
while fringe: #while fringe is not empty (= bool(fringe) == True)
(d, _, v) = pop(fringe) #d

Подробнее здесь: [url]https://stackoverflow.com/questions/78456493/how-to-implement-a-skip-in-neighbor-nodes-in-modified-dijkstras-algorithm[/url]