Вот есть у меня матрица весов. Стартовая позиция - нижний

Question

Вот есть у меня матрица весов. Стартовая позиция - нижний

левый угол; конец - верхний правый. Нужно найти кратчайший маршрут. Не проблема! Из конца запускаем волну. Но, если маршрутов несколько - вывести их все
Вот с этим затык
Пробовал сначала сделать рекурсию. Нашли развилку? Ставим затычку в право идём вверх, а потом затычку сверху и идеи вправо. При максимальном числе маршрутов (когда все веса одинаковые) ответ получаю только через 63 секунды.
Никуда не годится. Переделал на бинарное дерево. Развилка? Создаём потомков и идем дальше. Получил 23 секунды.
Вопрос: можно ли ещё как-то получить маршрут? Или пересмотреть дерево и как-то его оптимизировать? Дерево возвращает вектор строк в качестве ответа. Ответ: записи вида G(i,j) от начала до конца

#c #embedded #programming #russian

0

16.04.2021

8 ответов

11 просмотров

Constantine Drozdov

к черту подробности, как считается вес маршрута и куда можно ходить

0

16.04.2021

Иоанн Гольден Автор вопроса

Constantine Drozdov
к черту подробности, как считается вес маршрута и ...

Вверх или вправо из начальной точки. Нужна ещё одна матрица, она же и будет матрицей пути. Инициализирую ее максимумом Формирую записи матрицы пути следующим образом: начинаю идти с конца по всей матрице, если придти сверху ближе чем справа, то записываю значение матрицы пути + матрицы весов. Если сверху ближе - аналогично

0

16.04.2021

Иоанн Гольден Автор вопроса

Constantine Drozdov
к черту подробности, как считается вес маршрута и ...

Просто и быстро Но, возможно, эта простота себя не оправдывает

0

16.04.2021

Иоанн Гольден Автор вопроса

std::slavik
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D...

Пути сложновато получить будет

0

16.04.2021

std::slavik

Иоанн Гольден
Пути сложновато получить будет

каким алгоритмом?

0

16.04.2021

Constantine Drozdov

Иоанн Гольден
Вверх или вправо из начальной точки. Нужна ещё одн...

Если ходить только вверх или вправо, то (1) зачем Форд-Беллман если граф без циклов и кратчайшие пути считаются проходом по графу против направления пути (2) после поиска длины кратчайшего пути от всех вершин до финиша все маршруты до финиша выводит простейшая рекурсия по всем маршрутам с отсечением "сколько идти до финиша", которое считается в параметре (3) пункт (2) работает за вывод, так что проблема в любом случае дальше может быть только в выводе

0

16.04.2021

Иоанн Гольден Автор вопроса

std::slavik
каким алгоритмом?

Сильно урезанный поиск в ширину

0

16.04.2021

std::slavik · Accepted Answer

std::slavik

https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BA%D1%80%D0%B0%D1%82%D1%87%D0%B0%D0%B9%D1%88%D0%B5%D0%BC_%D0%BF%D1%83%D1%82%D0%B8

0

16.04.2021

170 похожих чатов

Вот есть у меня матрица весов. Стартовая позиция - нижний

8 ответов

Похожие вопросы