LINUX.ORG.RU
ФорумTalks

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


0

0

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

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

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

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


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



// =^_^=

Ещё автор может наебаться в конце, если не учтёт человеческий фактор: к примеру, сколько займёт время пересадки с одного транспорта на другой, перемещения с одной остановки на другую (здесь нужно думаю брать 75% от времени максимально затруднённого действия (перемещения, пересадки со всеми вытекающими).

anonymous
()
Ответ на: комментарий от anonymous

> Ещё автор может наебаться в конце, если не учтёт человеческий фактор: к примеру, сколько займёт время пересадки с одного транспорта на другой, перемещения с одной остановки на другую (здесь нужно думаю брать 75% от времени максимально затруднённого действия (перемещения, пересадки со всеми вытекающими).

Это всё элементарно учитывается без накладных алгоритмов через простую трёхмерную карту.

anonymous
()
Ответ на: комментарий от anonymous

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

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

anonymous
()
Ответ на: комментарий от anonymous

> Это всё элементарно учитывается без накладных алгоритмов через простую трёхмерную карту.

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

anonymous
()
Ответ на: комментарий от anonymous

> Это смотря как интерпретировать тему.

Да по*й как интерпретировать. Ничего нового в дипломе не делается даже формально.

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

Всё это хуита и 101 раз реализовано в лабораторных всех вузов страны. Если это диплом, то только разве что ПТУшный.

> Всё это требует учёта многих практических факторов.

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

> Да, и ещё проблема в такой задаче в большом объёме работ по составлению и обновлению маршрутов транспорта, расписаний, карт.

Гугл мапс + любая база трафика. И вообще это не научная, а инженерная задача. И тем более никакой новизны в этом нет.

anonymous
()
Ответ на: комментарий от anonymous

> трёхмерной карте будут большие оверхеды при движении в двух измерениях (на транспорте)

Каким образом?

> я предлагаю длиной связи

На*й нужны лишние костыли-связи на карте? Или это такая карта для передвижения на велосипедах?

anonymous
()
Ответ на: комментарий от anonymous

Мне бесполезно вам сейчас что-то доказывать, это разрастётся на несколько страниц флейма, и всё равно вы останетесь при своём мнении.

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

anonymous
()
Ответ на: комментарий от anonymous

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

Целую, Я.

anonymous
()
Ответ на: комментарий от anonymous

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

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

anonymous
()
Ответ на: комментарий от anonymous

> больших, умных и понимающих

Прям как в анекдоте: толстых, с завышеным ЧСВ и ФГМ.

anonymous
()

угости дальнобойщика пивом

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.