На практике столкнулся с такой проблемой: есть сверлильный станок для него существуе задание просверлить N дырок и вернутся в исходную позицию. Координаты дырок известны, нужно минимизировать пройденный путь.
ЗЫ Мне посоветовали читать книжки по теории графов

Если на плоскости, то это типичная задача коммивояжера.
Оптимизировать можно, отсекая лишние ветви, если уже на i-том шаге путь станка больше какого-то полученного. А вообще посмотри метод Литтла. Вроде как он позволяет решать задачу для N (кол-ва городов) в районе 30-50...

Плиз дайте ссылку.

http://alglib.manual.ru/

Там только блок-схема была в прошлый раз.... но на безрыбье....

Можно использовать генетический алгоритм. Поищи "Konstantin Boukreev" , он написал программу на эту тему и выложил исходник. Правда генетические алгоритмы довольно медленные.

http://www.codeproject.com/cpp/tspapp.asp
Буду разбириться

Алгоритм решения задачи комивояжера: (алгоритм жадный, так что он может давать оптимальное решение, а может и не давать, но не жадного алгоритма нет т.к. задача NP-полна)
1)Начинаем строить цикл, включив в него ребро наименьшего веса;
2)Среди рёбер, инцедентных концам нашего ребра, находится ребро наименьшего веса(весом будет расстояние между дырками) и тоже включается в цикл;
3)Если построили цепь, то просматриваем рёбра, инцедентные концам цепи, и не образующие цикл с уже включёнными рёбрами, выбираем наименьшее и включаем;
4)Пункт 3 повторяем, пока не закончатся вершины, а потом соединяем последнюю и первую вершины.
Вот и весь алгоритм. Его удобнее всего реализовать методом расстановки меток.

А скажите, задача коммивояжёра определена для полного графа, или для любого?

Hello, ALL !

Если путь замкнутый, то видимо для любого.

В случае с печ-ми платми, прирост производит-ти станка при замене пути,
может достичь ~30 % (где вычитал не помню, давно это было)
Реальный экономический эффект, без "большого" напряга :-)
Когда-то я пробовал решать эту задачу по алгоритму, схожему с предложенным
Golod-ом, но с некоторым отличием. Внедрить, увы не удалось, т к на тот момент
все производства "дохли" ... :-( Попробуйте, может у вас что-то получится.

Итак, алгоритм:

1) в составленной матрице из _расстояний_ между точками выбираем самую
"дальнюю" точку (можно по макс расст или по сумме всех расст. Я брал 1-й вар )
2) вкл в маршрут _две_ ближайшие точки
3) добавить в маршрут точку с наименьшей ценой, т е включение которой даёт
_наименьшее_ приращение длинны маршрута. Включение этой точки
производится перебором включением во все рёбра уже имеющегося маршрута.
Есс-но выбирается вставка в то ребро, где приращение маршрута наименьше.
4) ... и так далее, пока не будут вставлены в маршрут все точки.

Была и вторая часть, оптимизатор, но сейчас точно я его не помню :-(
Если найду, кину. Эх, давно это было ... :-(

Удачи !

кстати, а сколько отверстий? (приблизительно)

Цитата(maxim1000 @ 13.5.2004, 11:37)

кстати, а сколько отверстий? (приблизительно)

~100 в худшем случае
p.s. уже потихоньку врубаюсь в книжку Кристофидеса "Графы.
Алгоритмический подход"

Это сообщение отредактировал(а) Graf Zeppelin - 14.5.2004, 11:25

В догонку

Как вариант:
п 2 можно изменить на включение 2-х или 3-х самых дальних точек,
что-бы охватить сразу _весь_ периметр печатной платы.
Этот вариант у меня тоже был. Экспериментируйте...

Удачи !

Цитата(Crot @ 13.5.2004, 05:59)

А скажите, задача коммивояжёра определена для полного графа, или для любого?

Решение есть если граф Гамильтонов, задача определения являеся ли граф Гамильтоновым NP полная, но полный граф всегда Гамильтонов.

в догонку могу посоветовать книгу Мину, тоже по графам.

http://algolist.manual.ru

Вобщем там есть достаточно простые методы. Хотя там нет методов ветвей и границ.