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

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

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

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

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

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

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

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

если еще чтото я намутил спроси конкретно, и я попытаюсь поэтапно отвечать на твои вопросы.
]]> AntSecam Алгоритмы https://forum.sources.ru/index.php?showtopic=39346&view=findpost&p=259310 Sun, 07 Dec 2003 22:55:38 +0000 https://forum.sources.ru/index.php?showtopic=39346&view=findpost&p=259310
Разумеется, можно построить пример системы городов, где ни одно из найденных таким образом решений не будет оптимальным.

Вообще, чтобы решить ету задачу необходим (усеченный) перебор, т.е., метод ветвей и границ (долго, но с гарантией), или стохастический алгоритм, например, генетический (быстро но не гарантированно). ]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=39346&view=findpost&p=258013 Fri, 05 Dec 2003 09:14:39 +0000 https://forum.sources.ru/index.php?showtopic=39346&view=findpost&p=258013

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

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

Те размышления, которые я видел, сводились к тому, что надо как-то строить локальные компоненты связанности (т.е. для трех точек мы ищем так называемую "точку Штейнера", для которой суммарное расстояние от вершин треугольника до этой точки минимальное). Эти компоненты связанности прибавляются к искомым вершинам. Дальше продолжаем строить эти компоненты, пока вся сеть не будет связанной.
Только:
1) как лучше выбрать три вершины, для которых будем строить локальную компоненту связанности
2) для треугольника как найти эту "точку Штейнера"? (мат. формулы) ]]> tserega Алгоритмы https://forum.sources.ru/index.php?showtopic=39346&view=findpost&p=257975 Fri, 05 Dec 2003 08:28:33 +0000 https://forum.sources.ru/index.php?showtopic=39346&view=findpost&p=257975
Строим матрицу N*N в которой записываем расстояние между каждым из городов,
Ищем минимальное, (исключая нулевые значения которые стоят по диагонали матрицы ),
соединяем точки, для которых расстояние минимально,

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

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

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

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

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

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

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

]]> AntSecam Алгоритмы https://forum.sources.ru/index.php?showtopic=39346&view=findpost&p=254950 Sun, 30 Nov 2003 14:39:30 +0000 https://forum.sources.ru/index.php?showtopic=39346&view=findpost&p=254950 задачу Штейнера: в плоской стране есть N городов, которые надо соединить дорогами так, чтобы образовалась связанная сеть. Естественно, суммарная длина дорог должна быть минимальной. В любом месте страны можно строить сколько угодно развилок (т.е. дороги могут разветвляться в чистом поле, в отличии от задачи Прима-Круксала о минимальном стягивающем дереве).

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

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

Может у кого-нибуть есть исходник, буду признателен.... ]]> tserega Алгоритмы