Задача Штейнера , алгоритм или исходник

Требуется решить задачу Штейнера: в плоской стране есть N городов, которые надо соединить дорогами так, чтобы образовалась связанная сеть. Естественно, суммарная длина дорог должна быть минимальной. В любом месте страны можно строить сколько угодно развилок (т.е. дороги могут разветвляться в чистом поле, в отличии от задачи Прима-Круксала о минимальном стягивающем дереве).

Решение для трех точек понятно: если один из углов треугольника больше 120 градусов, то две стороны треугольника образуют сеть. Если все углы меньше 120, то в треугольнике ABC ещим точку P такую, что углы APB, BPC, CPA равны 120 градусов (это сделать несложно).

А как решить задачу для N > 3? Точно она не решается, хотя бы приближение какое-нибуть бы найти... Помогите алгоритмом, как определить где надо построить развилки (потом соединить по SST алгоритмом Прима).

Может у кого-нибуть есть исходник, буду признателен....

Насчет связного и понятного алгоритма это тяжело, но есть некоторые соображения:

Строим матрицу N*N в которой записываем расстояние между каждым из городов,
Ищем минимальное, (исключая нулевые значения которые стоят по диагонали матрицы ),
соединяем точки, для которых расстояние минимально,

ВАЖНО!: теперь рассматриваем соединенные точки как ЕДИНЫЙ ОБЪЕКТ и ищем уже кратчайшее расстояние от каждой точки до него,
получаем старую матрицу в которой две строки и два столбца заменились соответственно на строку и столбец расстояний от нового объекта, до каждой из точек.

Замечание : ясно что кратчайшее расстояние от точки до полученного выше отрезка будет либо по перпендикуляру, либо по наклонной.

Опять выбираем кратчайшее расстояние из новой матрицы (N-1)*(N-1) и строим его.

Еще раз напомню : соединенные точки рассматриваем как единый объект.

И Т.Д. пока все точки не быдут соединены.

Нужно реализовать и посмотреть, будет ли решение оптимальным.
Потом если решение не оптимально можно попробовать вывести правила оптимизации полученного объекта.

Эт пока все что надумал Пиши!

Ну, это делается по SST алгоритмом Прима. Понятно как.

Что есть единый объект и от каких точек мы ищем расстояние до объекта? Можно подробнее.

Те размышления, которые я видел, сводились к тому, что надо как-то строить локальные компоненты связанности (т.е. для трех точек мы ищем так называемую "точку Штейнера", для которой суммарное расстояние от вершин треугольника до этой точки минимальное). Эти компоненты связанности прибавляются к искомым вершинам. Дальше продолжаем строить эти компоненты, пока вся сеть не будет связанной.
Только:
1) как лучше выбрать три вершины, для которых будем строить локальную компоненту связанности
2) для треугольника как найти эту "точку Штейнера"? (мат. формулы)

В качестве первых двух точек, от которых плясать, можно выбрать два города, лежащих в соседних вершинах выпуклой оболочки, охватывающей все множество городов. Если етот выбор сделать несколько раз, с разными парами городов, лучшее из найденных решений будет близко к оптимальному...

Разумеется, можно построить пример системы городов, где ни одно из найденных таким образом решений не будет оптимальным.

Вообще, чтобы решить ету задачу необходим (усеченный) перебор, т.е., метод ветвей и границ (долго, но с гарантией), или стохастический алгоритм, например, генетический (быстро но не гарантированно).

Сообщение отредактировано: Visitor - 07.12.03, 22:56

Я вообще не претендую на то, что мой алгоритм может оказаться верным.
Просто меня заинтересовала задача, ходил и думал как это сделать, то что пришло в голову решил написать здесь, вдруг пригодится.
Именно поэтому таких умных слов как

и т.д. могу и не знать.

Единым объектом я для удобства назвал любые соединенные точки и их соединенния.

т.е. вначале на 1 шаге объектами являются отдельные точки.
после того как мы соединили первые две точки (те между которыми расстояние минимально)
объектами являются отдельные(не соединенные) точки и единым объектом две соединенные точки, т.е. из геометрии это отрезок.
далее ищем расстояния между несоединенными точками( они уже были получены на 1 шаге)

и кратчайшее расстояние от несоединенных точек до полученного отрезка.

На более высоких шагах едиными объектами быдут являться уже не отрезки а геом фигуры составленные из отрезков и кратчайшее расстояние уже нужно будет искать до любой точки принадлежащей этой фигуре.

т.е. идея в чем:
у тебя есть условие, что можно ставить неограниченное число развилок в любом месте, но не понятно как найти эти места, при реализации данного алгоритма:

например кратчайшее расстояние от отрезка, до "свободной" точки:
это либо перпендикуляр, если возможно его построить к отрезку из данной точки, либо, если невозможно построить перпендикуляр, то кратчайшее расстояние это линия к одному из концов отрезка.

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

если еще чтото я намутил спроси конкретно, и я попытаюсь поэтапно отвечать на твои вопросы.

Цитата tserega @ 30.11.03, 14:39

А как решить задачу для N > 3? Точно она не решается, хотя бы приближение какое-нибуть бы найти... Помогите алгоритмом, как определить где надо построить развилки (потом соединить по SST алгоритмом Прима).

Назовём структуру искомой сети топологией. Т.е. топология искомой сети - это граф, представляющий из себя дерево, вершинами которого служат исходные точки, которые нужно соединить, и промежуточные точки ветвления (т.н. точки Штейнера, или точки Торричелли). Исходные точки являются листьями этого дерева - их степень равна 1. А внутренние вершины дерева - точки Штейнера, имеют степень 3, т.е. каждая точка Штейнера соединена тремя рёбрами со смежными вершинами.

Предположим, что топология искомой сети известна. Чтобы найти саму оптимальную сеть, нужно найти соответствующее данной топологии оптимальное положение точек Штейнера на плоскости. Эта частная задача (поиск оптимального расположения точек Штейнера при заданной топологии) имеет простое красивое элегантное геометрическое решение, описанное в литературе.

Замечание. При некоторых расположениях исходных точек возможно совмещение точек Штейнера как между собой, так и с исходными точками.

Т.о., задачу Штейнера (точно или приближённо) можно решать, организовав каким-либо образом перебор топологий. Некоторые алгоритмы на эту тему тоже описаны в литературе...

Цитата Swetlana @ 21.11.10, 20:04

Graph, у нас не принято поднимать старые темы.

Сорри, протупил. Сначала ответил, потом посмотрел на дату исходного поста... Надеюсь, у спрашивавших когда-то студентов всё удачно сложилось с задачей Штейнера

Цитата Graph @ 22.11.10, 16:14

Сорри, протупил.

Never mind и бобро пожаловать

Прошу прощение за офтоп
А если алгоритм не решен? А если кто-нибудь будет искать? А если у кого-то есть идеи?

Цитата Black_Dragon @ 27.11.10, 06:42

Решение NP-трудных геометрических задач оптимизации - большой и довольно хорошо исследованный раздел.
Если в NP-трудной задаче оптимизации есть эвклидова метрика - это подарок, значит, для этой задачи есть питасы (полиномиальные апроксимационные схемы).
Если кто-то этим серьёзно занимается, пусть заведёт в этом разделе соответствующую тему и ведёт там тематический блог. С огромным удовольствием поучусь у специалиста. А пока выкладываю некий обзор способов решения наиболее известных "геометрических" задач, в том числе и дерева Штейнера.

Arora
Approximation schemes for NP-hard geometric optimization problems: A survey
Прикреплённый файлTSP_arorageo.pdf (350.33 Кбайт, скачиваний: 3480)