http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm
Я использую алгоритм ближайшего соседа для решения задачи коммивояжера. Это очень быстро, но не точно. Я где-то читал о двух улучшениях, которые я мог бы сделать. Первый - вместо того, чтобы начинать с одной случайной точки, запустить алгоритм ближайшего соседа, начиная с каждого узла. (Так, если есть N узлов, ближайший сосед запускается N раз) Затем сравните и выберите маршрут с наименьшим общим расстоянием. Это будет намного точнее. Но это слишком медленно.
Другой метод - вместо случайного выбора начального узла выберите специальный. Затем по-прежнему запускайте ближайшего соседа только один раз, чтобы получить результат. Это будет не так точно, как описанный выше метод, но определенно намного быстрее, поскольку алгоритм запускается только один раз, как и раньше. Но, к сожалению, я не мог вспомнить, где я читал эту статью и критерии выбора этого начального узла.
Я предполагаю, что я должен получить общее расстояние между каждым узлом и другими узлами, тогда узел, который имеет наибольшее значение, должен быть выбран в качестве начального узла. (По моим словам, это выбор узла, который «наиболее удален» от графа, при этом избегая выбора узла, который находится рядом с центром графа). Я думаю, что таким образом полученный мной маршрут должен быть достаточно близок к оптимальному кратчайшему маршруту.
Я правильно думаю?
Изменить: я имею дело с метрическим TSP с евклидовым расстоянием.
