Задача на минимальное остовное дерево
Доброго времени суток!
Не могу реализовать задачу на Borland Turbo C++.
Условие:
"Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут, который позволил бы посетить их все по одному разу. Построить графическое изображение маршрута."
Буду рад, если мне помогут с реализацией алгоритма.
Спасибо!
Не могу реализовать задачу на Borland Turbo C++.
Условие:
"Дан набор координат точек. Начиная с первой, проложить кратчайший маршрут, который позволил бы посетить их все по одному разу. Построить графическое изображение маршрута."
Буду рад, если мне помогут с реализацией алгоритма.
Спасибо!
Уточни. Тебе надо пройти без повторений? Или маршрут, который просто свяжет все точки?
Все точки по одному разу - без повторений.
Фактически, речь идёт о минимальном остовном дереве.
Изначально планируется использовать алгоритм Прима.
Но подойдёт любой с подробным комментированием кода (для того, чтобы разобраться)
Фактически, речь идёт о минимальном остовном дереве.
Изначально планируется использовать алгоритм Прима.
Но подойдёт любой с подробным комментированием кода (для того, чтобы разобраться)
Цитата: IT-Shark
Изначально планируется использовать алгоритм Прима.
Тебе надо задача коммивояжера, а не алгоритм Прима:). Алгоритм Прима находит каркас минимального веса, но его далеко не всегда можно росчерком пройти.
Согласен!
По моим сведениям, для решения этой задачи можно применить 2 метода:
Метод ветвей и границ и метод генетических алгоритмов.
Остаётся вопрос: где взять наглядные примеры для реализации этих алгоритмов?
По моим сведениям, для решения этой задачи можно применить 2 метода:
Метод ветвей и границ и метод генетических алгоритмов.
Остаётся вопрос: где взять наглядные примеры для реализации этих алгоритмов?
Цитата: IT-Shark
2 метода:
Метод ветвей и границ
http://www.basegroup.ru/genetic/math.htm
Цитата: IT-Shark
и метод генетических алгоритмов.