| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритмы задач кратчайшего пути |
| Автор: wind1 21.10.2009, 12:26 |
| Подскажите, пожалуйста, по каким алгоритмам можно решать следующие задачи: 1) Жук-долгоносик движется по лабиринту ходов внутри дерева к самке. Нужно найти кратчайший путь из возможных путей. 2) Дано множество городов, которые соединяют трассы определенной длины. Нужно найти кратчайший путь из города А в город Б. 3) Есть квартира, которая состоит из нескольких комнат, поделенных на квадраты. Есть пылесос, который должен убрать все комнаты. Нужно обойти все квадраты за меньшее количество времени – пройти все квадраты только по одному разу. Очень нужны хотябы названия алгоритмов, по которым решаются хотябы подобные задачи. |
| Автор: azesmcar 21.10.2009, 12:30 |
| http://ru.wikipedia.org/wiki/%D0%92%D0%BE%D0%BB%D0%BD%D0%BE%D0%B2%D0%BE%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC |
| Автор: ДобренькийПапаша 21.10.2009, 14:12 |
| см. Теория графов. Решение задачи коммивояжора посмотрите. Точно скажу вечером. |
| Автор: ДобренькийПапаша 21.10.2009, 18:06 |
| Для общего случая нахождения кратчайшего пути можно использовать алгоритм Беллмана-Форда. Также можно использовать алгоритм Дейкстры, но он работает, если нет рёбер отрицательного веса. 3-я задача, является задачей линейного программирования (вроде бы). Её можно решить составив систему неравенств с заданными ограничениями, и решить симплексным методом. Кажется так, если я не напутал))) |
| Автор: wind1 21.10.2009, 19:59 |
| Спасибо большое. Так, значит: 1. Волновой алгоритм; 2. Алгоритм Беллмана-Форда, алгоритм Дейкстры. 3. Линейное программирование (?) Третья задача, кажется, похожа на задачу о ходе коня, которая, думаю, не решается линейным программированием.. |
| Автор: ДобренькийПапаша 21.10.2009, 20:21 |
| А да, извиняюсь, я не вчитался в третью задачу. Да, это аналог задаче о коне, Вы правы. Решается элементарно, алгоритм можно самому составить в зависимости от правил передвижения пылесоса и карты квартиры. |
| Автор: esperanto 10.11.2009, 13:01 | ||
Во всех ваших задачах лабиринты, комнаты, города - известны заранее. Или же это случайные неизвестные параметры? |