Народ, подскажите, может кто сталкивался со следующей задачей. Есть некоторое, не очень большое (100-300), количество случайных отрезков на плоскости. Необходимо найти КРАТЧАЙШИЙ путь, проходящий через ВСЕ конечные точки отрезков и по САМИМ отрезкам. Может я не очень понятно написал, в атаче картинка с объяснением. Помогите плис
Это задача не о комие ваежоре. А на поиск кротчайшего пути. Посмотри Алгоритм Флойда. Правдо он порядка N^3.
Тебе придется добавить отсечение. И после прохода алгоритма выбрать наименьшую длину из всех получившихся.
Bohdan200 Не похоже, чтобы для этой задачи существовал полиномиальный алгоритм. Есть стандартный алгоритм ветвей и границ для задачи коммивояджера. Он частенько решает задачи до 100 вершин. Главная идея алгоритма - выбрать наилучшее ребро и рассмотреть 2 случая - ребро входит в путь и не входит. Первым рассматривается случай когда ребро в путь входит. Выбор наилучшего ребра происходит следующим образом. Будем считать, что мы ищем не путь, а цикл. (задача для пути сводится к задаче для цикла, если перебрать все возможности для концов) Составим матрицу расстояний между точками. В каждой строчке найдем минимум. Вычтем из всех расстояний этот минимум и прибавим его к текущему ответу. Потом тоже самое сделаем для всех столбцов. Для каждого нуля в матрице посчитаем 2 по величине число в строке и столбце. Сумма этих чисел - "штраф" за не взятие этого ребра. Соотвественно наилучшим является ребро с наибольшим штрафом. Если в процессе перебора текущий ответ превзойдет оптимальный - перебор заканчиваем. Алгоритм сложный, меньше чем за день его не напишешь.
Обратите внимание, что это не совсем задача на графе. Ведь рассматриваются случайно брошенные на плоскость отрезки. Это можно свести к графу, если только соединить концы каждого отрезка с концами всех остальных и уже на получившемся графе решать задачу нахождения кратчайшего пути.
Если не ошибаюсь, то эту задачу можно свести к классической TSP (Traveling Salesman Problem), если для всех точек, соединенных отрезком, взять в качестве расстояния большие отрицательные значения (что-нибудь вроде -10^12 например). Если же точки не соединены отрезком, брать обычное расстояние. Тогда можно применить любой стандартный алгоритм для TSP (cutting-plane method наверное справится), и итоговый путь будет обязательно содержать все отрезки, т.к. иначе не будет минимальным.
Уже неделю парюсь над проблемой. По всей видимости найти решение БЫСТРО не получится, надо искать альтэрнативу - какой-то метод, с достаточно близким к идеалу результатом так как мне абсолютно точного решения не надо.
В идеале начальная точка - любая. На практике наверно сделаю начальной точкой геом. центр картинки, а обход - перебор всех непройденых точек и выбор ближайшей. Немного не то, но наверно покатит
в общем, я попробовал, но видать мозги подсохли - быстро не получилось, на долго - времени нет попробуй перебором в виде поиска в глубину: построй два списка: сначала берешь первый отрезок (в списке отрезков) за конец А и все концы В (начиная с него) соединяй с концом А следующего, посчитай длину - это будет наилучший вариант. затем строй следующий, меняя маршрут с конца списка - если длина получится меньше чем у первого - значит этот становится наилучшим, продолжай поиск в первом, и т.д. самое сложное здесь - алгоритм выбора следующего конца, так, чтобы не пропускать точки, и исключать те, которые уже есть в списке текущего маршрута... вот-с
Попробуй использовать генетические алгоритмы для этой задачи, оптимального решения не получишь, но получиши близкое к нему за небольшое время.
