Комментарии 15
А построенный маршрут в каком-либо виде можно увидеть? Было бы неплохо, если бы в «Получившийся результат» была ещё и соответствующая картинка.
P.S. А выигрывает как обычно человек с большим количеством родственников\знакомых в разных частях города, которые согласятся сделать небольшой крюк к нужному месту.
P.S. А выигрывает как обычно человек с большим количеством родственников\знакомых в разных частях города, которые согласятся сделать небольшой крюк к нужному месту.
Итоговый маршрут вот такой на Яндекс.Картах. Ссылка из гитхаб.кода, но картинку добавлю, отличная идея
-
Всё верно, Гамильтонов путь на графе я не нашёл, а искал незамкнутую цепь, содержащую все точки. А также я был дважды в одной точке (случайно). Тем не менее задаче поиска кратчайшего маршрута между всеми точками без возврата домой свойственны все те же свойства, что и «классической» задаче коммивояжёра.
Если вернуться к задаче, то я попробовал несколько вариантов решения и пермутаций точек, и финальная оказалась очень близка к дому, хотя это и не было важно: хотелось минимизировать именно время от первой до последней. Время возвращения от последней точки до дома меня вообще не интересовало, в воскресенье вечером возвращаться из Зеленограда в Москву совсем несложно.
А место моего дома я убрал из анализа из соображений приватности. :-)
Если вернуться к задаче, то я попробовал несколько вариантов решения и пермутаций точек, и финальная оказалась очень близка к дому, хотя это и не было важно: хотелось минимизировать именно время от первой до последней. Время возвращения от последней точки до дома меня вообще не интересовало, в воскресенье вечером возвращаться из Зеленограда в Москву совсем несложно.
А место моего дома я убрал из анализа из соображений приватности. :-)
А если добавить второй параметр — стоимость поездки, как изменится маршрут?
Учитывая, что конкурс школьный и если его будет делать один человек, а не скооперируются несколько (это уже отдельная задача — сколько людей оптимально потребуется для снижения временных и денежных затрат. Хотя тут ответ ясен — 35.), и у него не будет личного транспорта.
Учитывая, что конкурс школьный и если его будет делать один человек, а не скооперируются несколько (это уже отдельная задача — сколько людей оптимально потребуется для снижения временных и денежных затрат. Хотя тут ответ ясен — 35.), и у него не будет личного транспорта.
Слушайте, а отличная идея кстати! Но ответ и вправду будет 35, я думаю. На всякий случай уточню, что я прокладывал маршрут с возможностью ехать по платной дороге, но алгоритм предпочел бесплатные.
Ответ 35 будет, только если найти людей, живущих в пешей доступности от билбордов. Но это сферическая ситуация получается, в реальной жизни несколько сложнее и тут уже теорию вероятностей со статистикой применять надо, наверное.
Ну а под стоимостью я понимал расходы на бензин\общественный транспорт.
Ну а под стоимостью я понимал расходы на бензин\общественный транспорт.
А, ну тогда мой ответ вас не удовлетворит. Затраты на бензин в городе пропорциональны не километражу, а времени (потому что обороты двигателя стабильны), поэтому минимизация времени это и есть минимизация трат на бензин. А в случае общественного транспорта в Москве есть дневной безлимит, который точно всех победит.
Я думал что речь про найм специальных сотрудников, но это уже совсем другая история
Я думал что речь про найм специальных сотрудников, но это уже совсем другая история
Весьма полезно, вариантов использования сразу несколько родилось в голове:
Если добавить в параметры временные рамки, в которые нужно посетить определенную точку получится отличная программа для курьеров\доставщиков цветов или еды. А если встретятся конфликты в расписании, то нужно добавлять курьеров до тех пор, пока все не справятся за минимальное время.
Еще можно забивать туда достопримечательности в чужом городе и за день успевать просмотреть больше, чем многие за неделю.
Если добавить в параметры временные рамки, в которые нужно посетить определенную точку получится отличная программа для курьеров\доставщиков цветов или еды. А если встретятся конфликты в расписании, то нужно добавлять курьеров до тех пор, пока все не справятся за минимальное время.
Еще можно забивать туда достопримечательности в чужом городе и за день успевать просмотреть больше, чем многие за неделю.
А если вернуться к исходной задаче? Сделать максимальное количество фотографий за ограниченное время (предположим те же 3 часа).
Потому как убрав даже 5-6 точек на выбросах текущего маршрута уже можно сократить время почти на 2,5 часа. Возможно с этой точки зрения есть и более оптимальный путь.
Потому как убрав даже 5-6 точек на выбросах текущего маршрута уже можно сократить время почти на 2,5 часа. Возможно с этой точки зрения есть и более оптимальный путь.
Ну тут, мне кажется, нужно вводить предпочтения на множестве времени-количества билбордов. У меня предпочтения были значительно повернуты в сторону количества точек, ограничение по времени было лишь в один выходной день.
И да, вы правы, что в случае усталости меня или моих спутников у нас был вариант «не ехать в зеленоград, выиграем 1,5 часа». Но мы доехали.
И да, вы правы, что в случае усталости меня или моих спутников у нас был вариант «не ехать в зеленоград, выиграем 1,5 часа». Но мы доехали.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как быстрее всего сфоткать 35 билбордов в Москве