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

>Вопрос: как найти кратчайший путь, например, из Днепропетровска в Ужгород?

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

Интересует другой вариант: использовать теорию графов, реализуемую на делфи?

алгоритм A* c весами.

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

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

Вроде это обычно решается динамическим программированием на графах. до каждого узла на расстоянии n ребер считаешь кратчайший путь, уже зная кратчайший путь до узлов на расстоянии n-1. Вот. А вообще это кажется NP полная задача, т.е. все известные алгоритмы имеют экспоненциальное время выполнения (от числа узлов). вот.

используй ГЛОНАС

ЗЫ: сессия?

Диплом. Причем не мой О_о

Может попробовать генетический алгоритм?

Тогда точно -- динамическое программрование.

Ну что тут поделаешь... - только вдоль.

> Вроде это обычно решается динамическим программированием на графах. до каждого узла на расстоянии n ребер считаешь кратчайший путь, уже зная кратчайший путь до узлов на расстоянии n-1. Вот. А вообще это кажется NP полная задача, т.е. все известные алгоритмы имеют экспоненциальное время выполнения (от числа узлов). вот.

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

да, стормозил. извиняюсь.

http://en.wikipedia.org/wiki/Shortest_path_problem

Домашнее задание?

Судя по описанию это задача на графах. Гугл: поиск кратчайшего пути в графе.

> Может попробовать генетический алгоритм?

Стесняюсь спросить, а что это? ;)

Кратчайший путь между двумя точками - прямая. Ответ: проложить новую трассу.

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

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

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

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

>> Может попробовать генетический алгоритм?

> Стесняюсь спросить, а что это? ;)

в данной задаче -- лажа.

А тогда реально будет вводить новые ремонты на дорогах?

в каком вузе и на какой специальности такие дипломы ?

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

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

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

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

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

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

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

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

ЗЫ: для уменьшения объема данным можно считать, что вероятность задана с точностью до 0.01.

Согласен с предыдущим оратором - функцией на рёбрах графа должно быть не расстояние, а время. А в случае ремонта или ещё какого катаклизма на дороге функция будет просто возвращать +inf =)

> в каком вузе и на какой специальности такие дипломы ?

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

Нормальный диплом. Ибо дипломник должен уметь адаптировать известные методы к известным задачам.

А вуз какой ?

>_таких_

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

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

* с учетом информации о закрытых дорогах выходящих из текущего узла.

> Согласен с предыдущим оратором - функцией на рёбрах графа должно быть не расстояние, а время.

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

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

> ...реализуемую на делфи?

тонкий троллинг?

Жестокая правда

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

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

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

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

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

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

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

а почему? Вот и вероятности тут накопали.
Можно ещё муравьиные алгоритмы посмотреть.

>а почему? Вот и вероятности тут накопали. Можно ещё муравьиные алгоритмы посмотреть.

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

Тебе не кажется. Это задача коммивояжера.

Ну это сферический такой ремонт, в вакууме.

>Тебе не кажется. Это задача коммивояжера.

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

>Локально оптимальное решение не имеет никакого отношение к глобальному оптимальному,

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

И че? Я имел ввиду, что градиентные методы тут не работают, а генетические алгоритмы основаны на них (в основной своей массе).

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

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

Бинго!! :)

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

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

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

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

Притом есть сборники проблема-решение, по которым студенты сверяют качество своих имплементаций.

не, не коммивояжёра. Коммивояжёр должен вернуться в исходную точку и посетить все пункты в графе, тут возвращаться не нужно.

Такое ощущение, что половина в топике дискретку забыла давно и прочно, другая половина и не знала, и небольшой процент хоть что-то помнящих. Пппц.

Вот так и ошибаются читая по верхам. *ушел посыпать голову пеплом*