Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе

individ.an · Сообщение **individ.an** » 28 июн 2015, 11:59

Нет - ну почему!
Думать всегда надо и там то же.
Просто для некоторых задач часто можно вообще не считать.
Или свести сам расчёт к минимуму.

folk · Сообщение **folk** » 28 июн 2015, 12:30

Ну алгоритмы для устного счета совсем другие - это верно. Там как мне кажется эвристики важны. Они хоть не идеальны но решают массу проблем
Пример - когда в прошлом веке писали шахматную программу для игры окончаний (заведомо выигрывающих), были "по тупому" просчитаны таблицы позиция - следующий оптимальный ход (для защиты - ход максимально отодвигающий проигрыш). И вот программа которая должна проиграть но сарается подольше потрепыхаться дается на растерзание гроссмейстерам, которые легко выигрывают в таких ситуациях. А альше странно - оказалось что гроссмейстеры играют по эвристикам - зажимают противника по определенным схемам и когда ход программы ломает схему, ломает стратегию, им приходится начинать сначала - и они не могут выиграть! Такой вот пердимонокль) Это я к чему - что гроссмейстеры играли по эвристикам))

Swetlana · Сообщение **Swetlana** » 26 сен 2015, 18:08

Кхм... Не вижу постановки задачи. О каком графе идёт речь? Ориентированном или неориентированном? Веса неотрицательные или любые?

individ.an · Сообщение **individ.an** » 26 сен 2015, 18:17

Swetlana писал(а):Source of the post Кхм... Не вижу постановки задачи. О каком графе идёт речь? Ориентированном или неориентированном? Веса неотрицательные или любые?

Действительно не понятно? И зачем такие дополнительные условия?
Если задача решена в общем виде, то какая разница? Не всё равно как он выглядит?

Swetlana · Сообщение **Swetlana** » 26 сен 2015, 18:52

Действительно только одно. Пока нет математической постановки задачи, нет смысла говорить об алгоритме.

В постановке самого общего вида речь идёт о взвешенном орграфе с произвольными весами, но без контуров отрицательного веса. Для этого случая алгоритм Форда-Беллмана (вектор расстояний от источника до всех вершин графа, выч. сложность O(nm)), алгоритм Флойда (матрица расстояний между всеми парами вершин, выч. сложность $O(n^{3})$ ), алгоритм Йена (первые k кратчайших путей между парой фиксированных вершин, выч. сложность $O(kn^{4})$ ).
Если на том же графе веса неотрицательные, то алгоритм Дейкстры (вектор расстояний за $O(n^{2})$ ), алгоритм Йена для первых k кратчайших путей за $O(kn^{3})$
Если орграф бесконтурный, то после правильной нумерации вектор расстояний за O(m).
Если граф неориентированный, то любое ребро отрицательного веса при расщеплении на пару противоположно направленных дуг образует контур отрицательного веса, к такому графу Флойд и Форд-Беллман уже не применимы. Если под кратчайшим путём понимается путь, у которого все вершины различны, то кратчайшие пути на таком графе находятся за экспоненциальное время.

Если граф неориентированный с неотрицательными весами, то направление не имеет значения, всё тот же вектор расстояний, который можно найти алгоритмом Дейкстры.
Если ориентированный без контуров отр. веса - тогда Флойд.
Если неориентированный с отрицат. весами - алгоритм с возвратом (бэктрекинг).

Swetlana · Сообщение **Swetlana** » 26 сен 2015, 19:25

Ответ на сабжевый вопрос.
Универсальный алгоритм есть, называется алгоритм с возвратом, в худшем случае будет работать за факториальное время.

individ.an · Сообщение **individ.an** » 27 сен 2015, 05:05

Swetlana писал(а):Source of the post Действительно только одно. Пока нет математической постановки задачи, нет смысла говорить об алгоритме.

В постановке самого общего вида речь идёт о взвешенном орграфе с произвольными весами, но без контуров отрицательного веса. Для этого случая алгоритм Форда-Беллмана (вектор расстояний от источника до всех вершин графа, выч. сложность O(nm)), алгоритм Флойда (матрица расстояний между всеми парами вершин, выч. сложность $O(n^{3})$ ), алгоритм Йена (первые k кратчайших путей между парой фиксированных вершин, выч. сложность $O(kn^{4})$ ).
Если на том же графе веса неотрицательные, то алгоритм Дейкстры (вектор расстояний за $O(n^{2})$ ), алгоритм Йена для первых k кратчайших путей за $O(kn^{3})$
Если орграф бесконтурный, то после правильной нумерации вектор расстояний за O(m).
Если граф неориентированный, то любое ребро отрицательного веса при расщеплении на пару противоположно направленных дуг образует контур отрицательного веса, к такому графу Флойд и Форд-Беллман уже не применимы. Если под кратчайшим путём понимается путь, у которого все вершины различны, то кратчайшие пути на таком графе находятся за экспоненциальное время.

Если граф неориентированный с неотрицательными весами, то направление не имеет значения, всё тот же вектор расстояний, который можно найти алгоритмом Дейкстры.
Если ориентированный без контуров отр. веса - тогда Флойд.
Если неориентированный с отрицат. весами - алгоритм с возвратом (бэктрекинг).

С ума сойти! Теперь осталось придумать алгоритм - как это всё объяснить разносчику пиццы или почтальёну.
Который умеет только считать и то плохо.
Я вспомнил один анекдот. В поезде едит математик и разговаривает с одним пассажиром.
Проезжают около стада коров. И математик говорит, что там 374 головы.
Пассажир удивляется и спрашивает. Как ты сумел посчитать?
А он говорит. Это же элементарно. Надо посчитать все копыта и разделить на 4.
Так и тут. Минимальное расстояние между двумя точками - это прямая их соединяющая.
Поэтому стандартная процедура расчёта сводится в построении всех вершин в одну прямую линию. Для этого и нужен не тупой перебор, а фантазия чтоб разглядеть метод выстраивающий все точки в одну линию.

Кстати похожая ситуация была с одной задачкой. Принцессы и Чудовища.
http://www.mathforum.ru/forum/read/1/70729/page/1/http://www.mathforum.ru/forum/read/1/70729/page/1/
Если Чудище движеться абсолютно случайно, то решение элементарно. Используя понятие геометрической вероятности.
Зато сколько бреда опубликовали. Ужас просто.

Кстати такие методы у буржуинов почему то называются - применение грубой силы в математике.
Мне кажеться хорошое определение.

Swetlana · Сообщение **Swetlana** » 27 сен 2015, 07:46

Методом "грубой силы" силы называют все переборные экспоненциальные алгоритмы.
Не засоряйте офтопом тематический раздел.

yourdomain.com