5
Prowadzę bibliotekę odnajdywania ścieżek. QuickGraph, biblioteka otwartych wykresów, pasuje do wszystkich moich wymagań, ale spotkałem się z jednym problemem. Potrzebuję algorytmów o najkrótszej ścieżce, aby pominąć krawędzie, które są nie do przebycia przez bieżący środek poruszający. Co chcę jest coś takiego:QuickGraph - Jak zrobić A *, aby pominąć określone krawędzie?
Func<SEquatableEdge<VectorD3>, double> cityDistances = delegate(SEquatableEdge<VectorD3> edge)
{
if(edge.IsPassableBy(agent))
return edgeWeight; // Edge is passable, return its weight
else
return -1; // Edge is impassable, return -1, which means, that path finder should skip it
};
Func<VectorD3, double> heuristic = ...;
TryFunc<VectorD3, IEnumerable<SEquatableEdge<VectorD3>>> tryGetPath = graph2.ShortestPathsAStar(cityDistances, heuristic, sourceCity);
mogę sobie wyobrazić rozwiązania tego problemu poprzez tworzenie kopii wykresu i usuwanie bezprzepływowej brzegi, ale to niepotrzebne marnotrawstwo zasobów komputera. Czy mógłby mi pan powiedzieć, jak rozwiązać ten problem? Czy też nie ma rozwiązania i powinienem zaktualizować źródło?
Szybkim zhackowaniem byłoby sprawienie, że nieprzejezdne krawędzie mają wagę większą niż całkowita waga rzeczywistej najkrótszej ścieżki. Algorytm A * zawsze przesunie ścieżki zawierające "nieprzekraczalne" krawędzie do końca kolejki priorytetów i znajdzie rzeczywistą najkrótszą ścieżkę. Wadą tego podejścia jest to, że * jeśli każda ścieżka do celu przemierza "niecierpliwą" krawędź, wówczas algorytm zhakowany wybierze ścieżkę, zamiast wykonać właściwą rzecz i zawodzi *. –
@EricLippert Obejście tego obejścia może polegać na sprawdzeniu długości ścieżki wynikowej, a jeśli jest większa niż "nieprzekraczalna" waga krawędzi, można oczekiwać, że nie znajdzie ona ścieżki. – Luaan
Jeśli chcesz określić niestandardową metodę pobierania odległości metodą, czy rzeczy takie jak 'DelegateIncidenceGraph' nie są przeznaczone do robienia tego, czego potrzebujesz? – Superbest