Коммивояжер осуществляет поездки по населенным пунктам.Потом я совершенно случайно прочёл в IT Happens историю, в которой была уже приведённая выше ссылка на википедию - оказалось, что задачке много-много лет, а алгоритмы решения к ней придумывают ещё с 1930 года.
Населенные пункты и порядок их посещения задаются массивом.
Каждый элемент массива содержит описание одного населенного пункта и включает
- Название
- Широта
- Долгота
- Признак начального, промежуточного и конечного пункта
Значение индекса массива соответствует порядковому номеру посещения населенного пункта.
Необходимо выполнить прогоны модели и оценить общую протяженность и время обхода маршрута на двух наборах населенных пунктов.
Число пунктов должно быть не менее 10, расстояния между пунктами 50-100 км.
В каждом наборе необходимо определить и оценить на модели не менее трех вариантов маршрута посещения населенных пунктов.
Скорость перемещения выбирается равной 200.0.
Величина времени моделирования выбирается исходя из требования обеспечения обхода всех пунктов маршрута.
Модель должна обеспечивать автоматическое получение длины пройденного расстояния и затраченного времени.
Алгоритмов существует масса, мне подошёл бы любой, и я стал искать решение на c++ - и был немного удивлён. Половина сайтов предлагала решение за деньги, притом немалые, другая половина - форумы - если и предоставляла решение, то на б-гомерзком pascal'е или delphi.
В итоге я совершенно случайно наткнулся на гугловый поиск по коду, который привёл меня к десяткам решений задачи коммивояжёра на любимом мною c++ (поиск без выбора языка даёт около тысячи результатов - думаю, любой найдёт реализацию на нужном ему языке).
Надеюсь, мой опыт кому-нибудь поможет сделать лабу\курсовую в ночь перед сдачей.
