Да, я в диссере занимаюсь приближенным решением задачи коммивояжера.
УПД.Немного хочу поболтать о том, где это может пригодиться и может чуть-чуть рассказать, чем я занимаюсь. Мне почему-то захотелось написать так, чтобы поняли люди ни разу не сталкивающиеся с программированием и дискретной математикой. Но на самом деле я себя все равно чувствую полным профаном в этом, поэтому буду рада, если читатели из it-области меня поправят, если что-то не так.
мда, в итоге все равно накручено получилось, не мое это - писать научно-популярно...да и научно тоже Да и вообще писать читать дальшеНадо конечно рассказать в чем состоит суть задачи коммивояжера, потому что наверняка в жизни вы ее решаете частенько, не подозревая об этом. Например, мне сегодня нужно будет съездить на четыре разных станции метро по делам и вернуться. Вот было бы здорово, если можно было бы их забить в приложение Яндекс.Метро и оно бы рассчитало наименьший путь моего сегодняшнего путешествия по Москве и, естественно, в каждый пункт назначения мне нужно попасть один раз (в математике это называется гамильтоновым циклом). А так, мне придется попарно забивать станции и самой прикидывать как будет менее затратно по времени.
Метро не самый корректный пример, но именно карта метро отлично иллюстрирует, что такое граф. Если мы еще подпишем между станциями время в пути (или расстояние между станциями), то такую схему метро можно назвать взвешенным графом. Так почему же пример не очень корректен? Потому что метро не является полным графом. Да, еще одна характеристика, потерпите, - теория графов действительно большой раздел дискретной математики, то есть раздел математики с конечными "прерывными" структурами данных. Но вернемся к полному графу. В таком графе любые две вершины (так называются наши "станции" в графе) соединены ребром - то есть путем между нашими "станциями". Метро не является полным графом, на первый взгляд, хотя бы потому что не соединены между собой конечные станции прямым путем. Заметьте, я написала, что пример не самый корректный, так как он не является полным графом на первый взгляд. На второй же взгляд, пример метро можно сделать корректным (если ввести еще парочку определений из теории графов) и внедрить в Яндекс.Метро решение задачи коммивояжера.
Ну ладно, забудем о метро и его картах и вспомним, где еще не хватает решения задачи, но не только в мегаполисах с метро? Конечно, просто в обычных дорожных картах. Например, решение этой задачи в реальном времени в навигации с учетом пробок - для водителей грузовиков, которые развозят продукты по магазинам. Опять же, водителю нужно заехать всего лишь по разу в каждый магазин. Думаю, расчет оптимального времени с учетом нескольких факторов был бы крайне полезен. Не знаю, возможно, все же этот функционал где-то встроен (может не с помощью задачи коммивояжера)? Пожалуйста, покажите, мне интересно посмотреть.
Почему же нельзя решать задачу коммивояжера "в лоб"? То есть, вычислить все возможные маршруты и выбрать минимальный? Давайте возьмем классическую постановку задачи коммивояжера. У нас есть 15 городов, который все соединены дорогами между друг другом и бедному коммивояжеру хочется побыстрей расправится со своей работой. Но он глуп и поэтому решил рассчитать свой путь "в лоб". И кажется, он опоздал на все возможные поезда, постарел и умер, пока считал, потому что вариантов его пути насчитывалось аж 43 миллиарда, а если бы городов было 18, то всевозможных путей через них насчитывалось 177 триллионов! И процитирую википедию: "Если бы существовало устройство, находящее решение для 30 городов за час, то для двух дополнительных городов требуется в тысячу раз больше времени; то есть, более чем 40 суток."
Думаю, после этого не нужно говорить, зачем нужно решать эту задачу другими способами... Но об этом может в другой раз, так как текста оказалось очень много. А я еще не затронула, так называемую, NP-полноту и следовательно, почему не все так просто с этой, казалось бы на первой взгляд, простой задачей. Да и продолжить рассказывать про теорию графов и задачу коммивояжера в контексте метро тоже можно растянуть еще на парочку абзацев. Короче, даже если это никто не прочитает, мне было полезно так покопаться в этом, сама себе в итоге задала парочку интересных вопросов. Пойду над ними думать.