LINUX.ORG.RU
Форум — Talks  

[Математикам]Помогите с решением


0

0
Здравствуйте всем!

Позвольте попросить у многоуважаемых участников сообщества помощи. В общем, задача состоит в следующем:

Есть карта автомобильных дорог, скажем, Украины. Вопрос: как найти кратчайший путь, например, из Днепропетровска в Ужгород? Можно, конечно, перебрать все возможные пути и выбрать минимальный из них, но тогда получаются кучи заведомо неверных вариантов... К слову, зачем ехать из Днепра в Ужгород через Донецк, конечно, для бешеной собаки собсно и 7 верст не крюк, и все же, это около шестисот лишних километров? Плюс ко всему, надо еще учесть такой вариант, что на кратчайшом пути, возможно что-то вроде ремонта дороги или движение перекрыто и целесообразнее поехать обходным путем и т.д.
Вот как задать это дополнительное условие (про ремонт дороги и перекрытость движения)?

Игры разума натолкнули на мысль, что кратчайший путь ищется по алгоритму Дейкстры, но что с этим делать дальше, непонятно :(


Спасибо заранее за помощь.



// =^_^=
← Номер страницы и OOv3
[полуЖЖ]Ваше отношение к виртуальной жизни. →
 ← 1 2 3
>Вопрос: как найти кратчайший путь, например, из Днепропетровска в Ужгород?

Рекомендую телепортацию.

anonymous
()
алгоритм A* c весами.
anonymous
()
> Вот как задать это дополнительное условие (про ремонт дороги и перекрытость движения)?

Измерять дорогу не длиной, а временем. Время = длина/(крейсерская скорость) + бонусы (все эти ремонты и т.д.)

anonymous
()
Вроде это обычно решается динамическим программированием на графах. до каждого узла на расстоянии n ребер считаешь кратчайший путь, уже зная кратчайший путь до узлов на расстоянии n-1. Вот. А вообще это кажется NP полная задача, т.е. все известные алгоритмы имеют экспоненциальное время выполнения (от числа узлов). вот.
soomrack ★★★★★
()
используй ГЛОНАС
anonymous
()
Ответ на: комментарий от far_tuna
Тогда точно -- динамическое программрование.
soomrack ★★★★★
()
Ну что тут поделаешь... - только вдоль.
anonymous
()
Ответ на: комментарий от soomrack
> Вроде это обычно решается динамическим программированием на графах. до каждого узла на расстоянии n ребер считаешь кратчайший путь, уже зная кратчайший путь до узлов на расстоянии n-1. Вот. А вообще это кажется NP полная задача, т.е. все известные алгоритмы имеют экспоненциальное время выполнения (от числа узлов). вот.

Очень умно звучит, но 4.2. Алгоритм Дейкстры квадратичен, а алгоритм Флойда-Уоршелла (поиск кратчайших путей между всеми парами вершин) кубический.

anonymous
()
Судя по описанию это задача на графах. Гугл: поиск кратчайшего пути в графе.
smh ★★★
()
Кратчайший путь между двумя точками - прямая. Ответ: проложить новую трассу.
matich ★
()
Ответ на: комментарий от smh
> Судя по описанию это задача на графах. Гугл: поиск кратчайшего пути в графе.

Так это... кратчайший путь ищется достаточно успешно, а как туда приплести про дополнительные условия?

far_tuna ★
() автор топика
Доп. условие -- можно ввести "надежность пути" -- вероятность отказа заданного участка дороги. И вести обсчет уже массива чисел: время до вершины и время между вершинами с учетом вероятности отказа. А дальше брать оптимальный маршрут, например, с гарантированной вероятностью 0.9 (параметр задан).

Сложность сохранится (кубическая, спс анонимусу).

soomrack ★★★★★
()
Ответ на: комментарий от far_tuna
> Так это... кратчайший путь ищется достаточно успешно, а как туда приплести про дополнительные условия?

Похоже можно просто удалить ремонтируемые\перекрытые дороги-рёбра из графа.

smh ★★★
()
Ответ на: комментарий от far_tuna
>> Судя по описанию это задача на графах. Гугл: поиск кратчайшего пути в графе.

> Так это... кратчайший путь ищется достаточно успешно, а как туда приплести про дополнительные условия?

В вес ребра. Дорога с ремонтом имеет бесконечный вес.

gaa ★★
()
Ответ на: комментарий от far_tuna 
Ну да, теперь у кажлого ребра есть два свойства:
1. Время в пути по этому ребру
2. Вероятность его отказа

Обсчитываешь следующий массив:
вероятность, время в пути
вероятность, время в пути
вероятность, время в пути

0.9; 2 часа
0.8; 1 час
0.7; 10 мин.

ЗЫ: для уменьшения объема данным можно считать, что вероятность задана с точностью до 0.01.
soomrack ★★★★★
()
Согласен с предыдущим оратором - функцией на рёбрах графа должно быть не расстояние, а время. А в случае ремонта или ещё какого катаклизма на дороге функция будет просто возвращать +inf =)
kranky ★★★★★
()
Ответ на: комментарий от anonymous
> в каком вузе и на какой специальности такие дипломы ?

Диплом по логистике, кафедра САПР. Что Вас смущает в _таких_ дипломах?

far_tuna ★
() автор топика
Ответ на: комментарий от far_tuna
Нормальный диплом. Ибо дипломник должен уметь адаптировать известные методы к известным задачам.
soomrack ★★★★★
()
Ответ на: комментарий от far_tuna
А вуз какой ?

>_таких_

транспортно вычислительных.

anonymous
()
Ответ на: комментарий от soomrack
Только считать надо будет с конца, и вторым проходом (с начала) определять наиболее благоприятноый ближайший узел, куда ехать.
soomrack ★★★★★
()
Ответ на: комментарий от soomrack
* с учетом информации о закрытых дорогах выходящих из текущего узла.
soomrack ★★★★★
()
Ответ на: комментарий от kranky
> Согласен с предыдущим оратором - функцией на рёбрах графа должно быть не расстояние, а время.

время плохо. Вряд ли чел захочет съезжать с федеральной трассы на грунтовку ради экономии 5 минут. Вес должен включать качество покрытия и т.п.

dilmah ★★★★★
()
Ответ на: комментарий от soomrack
"Ремонт"-это штука такая, например, с 8:15 до 9:45 по этому ребру проехать нельзя, то бишь, пользователь может задать, что сегодня в определенное время на участке будет "ремонт", а прога должна с учетом этого выбрать обходной путь или решить, что выгоднее будет подождать окончания "ремонта"...
far_tuna ★
() автор топика
Ответ на: комментарий от far_tuna
> "Ремонт"-это штука такая, например, с 8:15 до 9:45 по этому ребру проехать нельзя, то бишь, пользователь может задать, что сегодня в определенное время на участке будет "ремонт", а прога должна с учетом этого выбрать обходной путь или решить, что выгоднее будет подождать окончания "ремонта"...

узлы графа нужно размножить, добавив к ним время (скажем с шагом 10 минут). Получится такой большой граф.

dilmah ★★★★★
()
Ответ на: комментарий от far_tuna
>"Ремонт"-это штука такая, например, с 8:15 до 9:45 по этому ребру проехать нельзя, то бишь, пользователь может задать, что сегодня в определенное время на участке будет "ремонт", а прога должна с учетом этого выбрать обходной путь или решить, что выгоднее будет подождать окончания "ремонта"...

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

Время пути по ребру = время проезда по нему + ожидание пока его откроют (исходя из текущего времени). Вот.

ЗЫ: интереснее все-таки считать с надежностью пути.

ЗЗЫ: а где это есть ремонт с соблюденным расписанием?

soomrack ★★★★★
()
Ответ на: комментарий от anonymous
>а почему? Вот и вероятности тут накопали. Можно ещё муравьиные алгоритмы посмотреть.

Генетические алгоритмы больше подходят для огромных объемов данных, где всегда можно найти локально оптимальное решение. Если из локальных оптимальных глобальное субоптимальное не составить, то эффективность сомнительная. Тут объем данных вроде небольшой. Локально оптимальное решение не имеет никакого отношение к глобальному оптимальному, пожтому ген.алгоритмы идут лесом.

soomrack ★★★★★
()
Ответ на: комментарий от soomrack
Ну это сферический такой ремонт, в вакууме.
sin_a ★★★★★
()
Ответ на: комментарий от anonymous
>Тебе не кажется. Это задача коммивояжера.

Уже вспомнили, что нет.

soomrack ★★★★★
()
Ответ на: комментарий от soomrack
>Локально оптимальное решение не имеет никакого отношение к глобальному оптимальному,

>>Ремонт"-это штука такая, например, с 8:15 до 9:45 по этому ребру проехать нельзя, то бишь, пользователь может задать, что сегодня в определенное время на участке будет "ремонт", а прога должна с учетом этого выбрать обходной путь или решить, что выгоднее будет подождать окончания "ремонта"...

anonymous
()
Ответ на: комментарий от anonymous
И че? Я имел ввиду, что градиентные методы тут не работают, а генетические алгоритмы основаны на них (в основной своей массе).
soomrack ★★★★★
()
Блин классическая проблема комивояжера, есть огромная туча всевозможных алгоритмов. От генетических, по стохастические итд. итп.
anonymousI ★
()
Ответ на: комментарий от soomrack
> а, ну это-то вообще фигня. Ничего усложнять не нужно. У тебя просто поменяется функция подсчета времени проезда по ребру (она будет считатся исходя из текущего времени), т.е. для каждого начального времени (не так много, ибо транспорт ходит по расписанию) нужно прогнать алгоритм Дейкстры.

Бинго!! :)

> а где это есть ремонт с соблюденным расписанием?

Это условность, вместо ремонта может быть все, что угодно, неработающий по средам светофор; мент, засевший в кустах, на 35 км ходу, каждодневно с 12-00 до 19-00; пересечение дороги стадом барашков и все в таком духе.

И еще вопрос: куда впихать функцию подсчета времени и где описать расписание для каждного ребра?

/me чувствует, как блондинчатые волосы становятся все светлее и светлее..

far_tuna ★
() автор топика
Ответ на: комментарий от anonymousI
Притом есть сборники проблема-решение, по которым студенты сверяют качество своих имплементаций.
anonymousI ★
()
Ответ на: комментарий от anonymousI
не, не коммивояжёра. Коммивояжёр должен вернуться в исходную точку и посетить все пункты в графе, тут возвращаться не нужно.
anonymous
()
Ответ на: комментарий от anonymous
Такое ощущение, что половина в топике дискретку забыла давно и прочно, другая половина и не знала, и небольшой процент хоть что-то помнящих. Пппц.
redgremlin ★★★★★
()
Ответ на: комментарий от anonymous
Вот так и ошибаются читая по верхам. *ушел посыпать голову пеплом*
anonymousI ★
()
Вы не можете добавлять комментарии в эту тему: топик перемещен в архив.
 ← 1 2 3
← Номер страницы и OOv3
Talks
[полуЖЖ]Ваше отношение к виртуальной жизни. →