Здравствуйте. У меня есть карта дорог, представленная, примерно, из 1500 узлов (все пересечения обозначены, висячих или изолированных узлов нет). Она является взвешенным неориентированным графом. Требуется найти все возможные схемы пути из заданного пункта А в пункт В. Не получается написать алгоритм поиска и способ хранения результатов. Пыталась взять за основу какой-нибудь алгоритм из теории графов, не вышло, скорее всего, остается только вариант полного перебора, но как его организовать? Может, кто сталкивался с подобной задачей, подскажите метод или идею решения.
Уважаемые авторы вопросов! Большая просьба сообщить о результатах решения проблемы на этой странице. Иначе, следящие за обсуждением, возможно имеющие аналогичные проблемы, не получают ясного представления об их решении. А авторы ответов не получают обратной связи. Что можно расценивать, как проявление неуважения к отвечающим от автора вопроса.
Думаю легче всего будет работаться если весь граф уложить в матрицу смежности(будут очевидны перемещения между узлами) и выдавать результат в виде списка смежных вершин.
вот пример рекурсивной реализации для небольшого числа вершин (до 32)
забит граф в виде шестиугольника с большим циклом 013652, и вершина 4 соединена с 0,3,5
procedure TForm1.Button1Click(Sender: TObject);
var
Adj: array of array of Byte;
Src, Dest: Integer;
procedure FindRoute(V: Integer; Used: Integer; Route: string);
var
i, W: Integer;
begin
if V = Dest then
Memo1.Lines.Add(Route)
else
for i := 0 to High(Adj[V]) do begin
W := Adj[V, i];
if (Used and (1 shl W)) = 0 then
FindRoute(W, Used or (1 shl W), Route + IntToStr(W) + ' ');
end;
end;
Как я понял, граф ненасыщенный (E << V^2)
Тогда можно использовать представление графа в виде списков смежности, а все пути можно получить, например, так (псевдокод):
VertexUsed: array[N] of Boolean;// инициализируется False
Route: список или строка
procedure FindRoute(V: Vertex)
if V = Destination then
Print(Route)
else
для всех смежных с V вершин (W)
if not VertexUsed[W] then begin
VertexUsed[W] = True
добавить W к Route
FindRoute(W)
VertexUsed[W] = False
исключить W из Route
end
Уважаемый MBo, благодарю вас за ответ, но результат от поиска кратчайшего пути, не есть решение моей задачи. В моем примере, не много замкнутых траекторий, в виду чего, количество маршрутов не стремится к бесконечности, а все-таки является конечным числом.
Суть задачи – предоставить пользователю несколько возможных путей проезда, а он уже, в зависимости от своих, только ему ведомых, критериев, выберет нужный.
Количество всех путей будет неимоверное - экспоненциальная зависимость от размера графа
Так что нужно определить критерии отбора маршрутов - логично, например, искать кратчайшие пути: http://algolist.ru/maths/graphs/shortpath/
Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter. Функция может не работать в некоторых версиях броузеров.
