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

>ибо транспорт ходит по расписанию

хм.. это автомобили ездят по расписанию? Как хотят так и ездют. Если бы на автобусах ехали с пересадками на остановках, чтобы побыстрее (или min денег), тогда да.

Владимир Рыбинкин съел твой моск

Корона не жмет? Посмотрю я на тебя, что будешь через 5 лет помнить.

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

Причем тут какой-то господин Рыбинкин?

ЗЫ: последний раз запускал дельфи 10 лет назад.

Я то как раз вспоминаю, когда ответы вижу, что когда-то знал, почему и обратил внимание. :)

Ты вот скажи-ка давно у тебя был курс сего предмета?

P.S. Ах да, как раз пять лет и прошло ...

> Кажется, проще всего все время апдейтить длины ребер. Делаешь наследника класса "узел", там все прописываешь. Но код алгоритма похоже подправить все-таки придется...

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

Какая сложность алгоритма?

Ну молодец, большинство за 5 лет даже базовых формул не помнят. Я вот сдал в свое время на 4.5 из 5 дифуры. Сходу ни одного уравнения или системы не решу. Но вспомнить конечно быстрее чем заново обучаться.

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

нет, если автобус вышел из пункта А в 10:00, то в пункт Б он может прийти и в 11:07

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

1) А что делаешь-то?

2) Ты уже переселилась в Украину? :)

> А что делаешь-то?

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

> Ты уже переселилась в Украину? :)

Пока нет, как Вы можете наблюдать, я не могу туда доехать, пока не просчитаю дорогу ;)

Что ты забыла на Украине?!

> Какая сложность алгоритма?

в первых постах назвали A-star алгоритм -- не более чем квадратичен по числу узлов

> Что ты забыла на Украине?!

Да в принципе ничего из того, что держит меня здесь, просто тамошние люди мне очень нравятся ;)

оставайся с нами, приезжай в Питер. Тут тоже люди неплохие и с Украиы тоже есть.

PS: могу даже с работой попробовать подсобить.

> оставайся с нами, приезжай в Питер. Тут тоже люди неплохие и с Украиы тоже есть.

Забавный такой, как будто я в на другую сторону Экватора собралась, Украина она ж близко совсем. И потом, куда я от вас денусь, с неимоверной тягой к городу на Неве, с бесконечной любовью к красным кирпичным стенам города по умолчанию, с родными корнями из Брянских лесов и Смоленских озер :)

Грр. а там газа нету. фыф!

Ой да ладно, все там есть ;)

> Грр. а там газа нету. фыф!

баблопровода вообще нигде кроме дефолтного города нет

Нету, я там был. Его внутри страны продают на 100$ дороже, чем покупают у нас. Плохо там. Туда хорошо ездить отдыхать и все.

А на больше и не надо, я ж скучать по белокаменной начну :)

>баблопровода вообще нигде кроме дефолтного города нет

Угу. но видел бы ты что творится с энергетикой на постсоветском пространстве... Все продано и вообще не поддерживается, опоры лэп ржавые как дачные бочки, трубопроводы гнилые...

> А на больше и не надо, я ж скучать по белокаменной начну :)

А я к Москве равнодушен. :(

> видел бы ты что творится с энергетикой на постсоветском пространстве... Все продано и вообще не поддерживается, опоры лэп ржавые как дачные бочки, трубопроводы гнилые...

у меня родина в крыму -- там уже много лет норма -- горячая вода только по воскресеньям. При том что Черноморнефтегаз добывает газ, там чьи-то важные дети руководят.

>Ой да ладно, все там есть ;)

Пираццкое ... Не Ъ.

> у меня родина в крыму -- там уже много лет норма -- горячая вода только по воскресеньям. При том что Черноморнефтегаз добывает газ, там чьи-то важные дети руководят.

значит знаешь не по наслышке... грустно.

теория графов плюс поиск в ширину или простейшая эвристика. Я бы делал на лиспе или, в крайнем случае, на питоне.

собственно это одна из простейших задачек по ИИ.

Use GPS, mum.

Не оффтопь, пожалуйста.

сумрак прав,

динамическое программирование, однозначно.

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

Афигеть. Люди стесняються гугла.. ППЦ.

Подходить к задаче только с одной точки зрения на теорию графов - былинный отказ.

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

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

Ещё могу подсказать в какую сторону думать:

Наикратчайший путь между двумя узлами - отрезок на прямой, проложенный через два эти узла.

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

Можно делать красивее, запускать два таких потока, один из точки отправления, другой - из точки назначения, а можно вообще просчёт каждого нового узла в отдельном, ну это зависит от количества и качества дорог.

Уважаимый анонимус, спасибо за участие в судьбе многострадального диплома :) Графы тут присутствуют по умолчанию, ибо заведующий кафедры захотел чтобы так :) и больше интересует практический вопрос впихивания "расписания" в программу :)

Уважаимый анонимус, спасибо за участие в судьбе многострадального диплома :) Графы тут присутствуют по умолчанию, ибо заведующий кафедры захотел чтобы так :) и больше интересует практический вопрос впихивания "расписания" в программу :)

А что расписание?

Есть база данных расписаний движения транспорта (время прибытия и отправки на остановку). Если есть точное расписание и маршрут движения, несложно определить время появления транспорта в определённой точке пути. Далее, можно посчитать среднюю скорость движения между двумя узлами. Возможно ещё ввести дополнительные узлы, как остановки транспорта (к примеру, чтобы пересесть на более скоростной транспорт, на который было невозможно сесть на предидущем узле). Далее, имея среднее время движения транспорта между двумя узлами мы можем провести линию связи между ними.

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

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

Транспорт только один, пересаживаться никуда не надо (возить не человеков собираемся ))) А в какую часть проги запихивать это расписание?

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

не нужно изобретать велосипед. алгоритм A-star специально разработан для этого -- в нем геометрические соображения закладываются в эвристику.

Дак то же функция оценки пути для алгоритма A* :)

> Транспорт только один, пересаживаться никуда не надо (возить не человеков собираемся ))) А в какую часть проги запихивать это расписание?

В прогу записывать не расписание, а его обработку (на этапе построения графа). Расписание пихать в базу данных.

угу, а как тогда обращаться к этой базе?

Да и вообще, A* (в оригинальном понимании) хорошо служит для нахождения пути в двумерном грубокординированном пространстве (разделённом на клетки), на которе конечно можно наложить граф, но это извратно. Я думаю легче нагорбить свой алгоритм.

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

> угу, а как тогда обращаться к этой базе?

Зависит от реализации самой базы данных, наличия системы управления базой данных, реализации языка, наличия библиотек. Если религия запрещает пользоваться сторонней СУБД, то можно реализовать свою хоть на текстовых файлах.

Не очень понятны условия задачи.

http://www.google.ru/search?q=site:www.intuit.ru+поиск+пути

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

Поиск пути по карте - моя лаба по робототехнике.

В интернете исходников для мелких статических карт на делфи навалом.

Соответственно если >движение перекрыто<, надо просто отметить конкретное место перекрытия на карте как непроходимое.

p.s. В целом на диплом это не тянет. Максимум - слабенькая курсовая.

//Анонимный Анонимус