Moscow Power Engineering Institute: Mathcad Calculation Server

Решение задачи коммивояжера методом ближайшего соседа

(nva - nearest vertex add).

Координаты городов (n вершин евклидового графа) задаются пользователем либо случайно в интервале от 0 до 100. Укажите

также номер первого города (ib), нажмите на кнопку Recalculate и

получите ответ в виде маршрута на графике и длины пути S.

С какой точки

Пунктир - путь от последнего к первому городу

Маршрут не оптимальный (не самый короткий) и сильно зависит от выбора первого города.

Фактически не решена задача коммивояжера, а найдена одна гамильтонова цепь графа.

Следующий возможный шаг оптимизации - "развязывание петель" (ликвидация перекрестий).

Другое решение - перебор всех городов (вершин графа) в качестве начала маршрута и выбор

	This web page is running on a Mathcad Calculation Server, and was authored with Mathcad software.
	This web page can use the WaterSteamPro functions.
	You can also visit our products site at http://www.trie.ru.