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