Нет - ну почему!
Думать всегда надо и там то же.
Просто для некоторых задач часто можно вообще не считать.
Или свести сам расчёт к минимуму.
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
-
- Сообщений: 760
- Зарегистрирован: 07 фев 2015, 21:00
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
Последний раз редактировалось individ.an 27 ноя 2019, 19:25, всего редактировалось 1 раз.
Причина: test
Причина: test
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
Ну алгоритмы для устного счета совсем другие - это верно. Там как мне кажется эвристики важны. Они хоть не идеальны но решают массу проблем
Пример - когда в прошлом веке писали шахматную программу для игры окончаний (заведомо выигрывающих), были "по тупому" просчитаны таблицы позиция - следующий оптимальный ход (для защиты - ход максимально отодвигающий проигрыш). И вот программа которая должна проиграть но сарается подольше потрепыхаться дается на растерзание гроссмейстерам, которые легко выигрывают в таких ситуациях. А альше странно - оказалось что гроссмейстеры играют по эвристикам - зажимают противника по определенным схемам и когда ход программы ломает схему, ломает стратегию, им приходится начинать сначала - и они не могут выиграть! Такой вот пердимонокль) Это я к чему - что гроссмейстеры играли по эвристикам))
Пример - когда в прошлом веке писали шахматную программу для игры окончаний (заведомо выигрывающих), были "по тупому" просчитаны таблицы позиция - следующий оптимальный ход (для защиты - ход максимально отодвигающий проигрыш). И вот программа которая должна проиграть но сарается подольше потрепыхаться дается на растерзание гроссмейстерам, которые легко выигрывают в таких ситуациях. А альше странно - оказалось что гроссмейстеры играют по эвристикам - зажимают противника по определенным схемам и когда ход программы ломает схему, ломает стратегию, им приходится начинать сначала - и они не могут выиграть! Такой вот пердимонокль) Это я к чему - что гроссмейстеры играли по эвристикам))
Последний раз редактировалось folk 27 ноя 2019, 19:25, всего редактировалось 1 раз.
Причина: test
Причина: test
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
Кхм... Не вижу постановки задачи. О каком графе идёт речь? Ориентированном или неориентированном? Веса неотрицательные или любые?
Последний раз редактировалось Swetlana 27 ноя 2019, 19:25, всего редактировалось 1 раз.
Причина: test
Причина: test
-
- Сообщений: 760
- Зарегистрирован: 07 фев 2015, 21:00
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
Swetlana писал(а):Source of the post Кхм... Не вижу постановки задачи. О каком графе идёт речь? Ориентированном или неориентированном? Веса неотрицательные или любые?
Действительно не понятно? И зачем такие дополнительные условия?
Если задача решена в общем виде, то какая разница? Не всё равно как он выглядит?
Последний раз редактировалось individ.an 27 ноя 2019, 19:25, всего редактировалось 1 раз.
Причина: test
Причина: test
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
Действительно только одно. Пока нет математической постановки задачи, нет смысла говорить об алгоритме.
В постановке самого общего вида речь идёт о взвешенном орграфе с произвольными весами, но без контуров отрицательного веса. Для этого случая алгоритм Форда-Беллмана (вектор расстояний от источника до всех вершин графа, выч. сложность O(nm)), алгоритм Флойда (матрица расстояний между всеми парами вершин, выч. сложность ), алгоритм Йена (первые k кратчайших путей между парой фиксированных вершин, выч. сложность ).
Если на том же графе веса неотрицательные, то алгоритм Дейкстры (вектор расстояний за ), алгоритм Йена для первых k кратчайших путей за
Если орграф бесконтурный, то после правильной нумерации вектор расстояний за O(m).
Если граф неориентированный, то любое ребро отрицательного веса при расщеплении на пару противоположно направленных дуг образует контур отрицательного веса, к такому графу Флойд и Форд-Беллман уже не применимы. Если под кратчайшим путём понимается путь, у которого все вершины различны, то кратчайшие пути на таком графе находятся за экспоненциальное время.
Если граф неориентированный с неотрицательными весами, то направление не имеет значения, всё тот же вектор расстояний, который можно найти алгоритмом Дейкстры.
Если ориентированный без контуров отр. веса - тогда Флойд.
Если неориентированный с отрицат. весами - алгоритм с возвратом (бэктрекинг).
В постановке самого общего вида речь идёт о взвешенном орграфе с произвольными весами, но без контуров отрицательного веса. Для этого случая алгоритм Форда-Беллмана (вектор расстояний от источника до всех вершин графа, выч. сложность O(nm)), алгоритм Флойда (матрица расстояний между всеми парами вершин, выч. сложность ), алгоритм Йена (первые k кратчайших путей между парой фиксированных вершин, выч. сложность ).
Если на том же графе веса неотрицательные, то алгоритм Дейкстры (вектор расстояний за ), алгоритм Йена для первых k кратчайших путей за
Если орграф бесконтурный, то после правильной нумерации вектор расстояний за O(m).
Если граф неориентированный, то любое ребро отрицательного веса при расщеплении на пару противоположно направленных дуг образует контур отрицательного веса, к такому графу Флойд и Форд-Беллман уже не применимы. Если под кратчайшим путём понимается путь, у которого все вершины различны, то кратчайшие пути на таком графе находятся за экспоненциальное время.
Если граф неориентированный с неотрицательными весами, то направление не имеет значения, всё тот же вектор расстояний, который можно найти алгоритмом Дейкстры.
Если ориентированный без контуров отр. веса - тогда Флойд.
Если неориентированный с отрицат. весами - алгоритм с возвратом (бэктрекинг).
Последний раз редактировалось Swetlana 27 ноя 2019, 19:25, всего редактировалось 1 раз.
Причина: test
Причина: test
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
Ответ на сабжевый вопрос.
Универсальный алгоритм есть, называется алгоритм с возвратом, в худшем случае будет работать за факториальное время.
Универсальный алгоритм есть, называется алгоритм с возвратом, в худшем случае будет работать за факториальное время.
Последний раз редактировалось Swetlana 27 ноя 2019, 19:25, всего редактировалось 1 раз.
Причина: test
Причина: test
-
- Сообщений: 760
- Зарегистрирован: 07 фев 2015, 21:00
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
Swetlana писал(а):Source of the post Действительно только одно. Пока нет математической постановки задачи, нет смысла говорить об алгоритме.
В постановке самого общего вида речь идёт о взвешенном орграфе с произвольными весами, но без контуров отрицательного веса. Для этого случая алгоритм Форда-Беллмана (вектор расстояний от источника до всех вершин графа, выч. сложность O(nm)), алгоритм Флойда (матрица расстояний между всеми парами вершин, выч. сложность ), алгоритм Йена (первые k кратчайших путей между парой фиксированных вершин, выч. сложность ).
Если на том же графе веса неотрицательные, то алгоритм Дейкстры (вектор расстояний за ), алгоритм Йена для первых k кратчайших путей за
Если орграф бесконтурный, то после правильной нумерации вектор расстояний за O(m).
Если граф неориентированный, то любое ребро отрицательного веса при расщеплении на пару противоположно направленных дуг образует контур отрицательного веса, к такому графу Флойд и Форд-Беллман уже не применимы. Если под кратчайшим путём понимается путь, у которого все вершины различны, то кратчайшие пути на таком графе находятся за экспоненциальное время.
Если граф неориентированный с неотрицательными весами, то направление не имеет значения, всё тот же вектор расстояний, который можно найти алгоритмом Дейкстры.
Если ориентированный без контуров отр. веса - тогда Флойд.
Если неориентированный с отрицат. весами - алгоритм с возвратом (бэктрекинг).
С ума сойти! Теперь осталось придумать алгоритм - как это всё объяснить разносчику пиццы или почтальёну.
Который умеет только считать и то плохо.
Я вспомнил один анекдот. В поезде едит математик и разговаривает с одним пассажиром.
Проезжают около стада коров. И математик говорит, что там 374 головы.
Пассажир удивляется и спрашивает. Как ты сумел посчитать?
А он говорит. Это же элементарно. Надо посчитать все копыта и разделить на 4.
Так и тут. Минимальное расстояние между двумя точками - это прямая их соединяющая.
Поэтому стандартная процедура расчёта сводится в построении всех вершин в одну прямую линию. Для этого и нужен не тупой перебор, а фантазия чтоб разглядеть метод выстраивающий все точки в одну линию.
Кстати похожая ситуация была с одной задачкой. Принцессы и Чудовища.
http://www.mathforum.ru/forum/read/1/70729/page/1/http://www.mathforum.ru/forum/read/1/70729/page/1/
Если Чудище движеться абсолютно случайно, то решение элементарно. Используя понятие геометрической вероятности.
Зато сколько бреда опубликовали. Ужас просто.
Кстати такие методы у буржуинов почему то называются - применение грубой силы в математике.
Мне кажеться хорошое определение.
Последний раз редактировалось individ.an 27 ноя 2019, 19:25, всего редактировалось 1 раз.
Причина: test
Причина: test
Подскажите есть ли универсальный алгоритм для поиска нескольких кратчайших путей на графе
Методом "грубой силы" силы называют все переборные экспоненциальные алгоритмы.
Не засоряйте офтопом тематический раздел.
Не засоряйте офтопом тематический раздел.
Последний раз редактировалось Swetlana 27 ноя 2019, 19:25, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 1 гость