Добрый день

Не подскажите ли какой-либо общий алгоритм для решения следующей задачи:
Есть прямоугольник размерами ДхШ. Внутри произвольно расположены
М точек. По периметру прямоугольника равномено расположены еще
М точек. Необходимо:
1) Для каждой точки в поле найти точку на периметре таким образом,
чтобы отрезки соединяющие точки не пересекались.
2) Если возможно несколько вариантов, то выбрать тот при котором
длины отрезков наименьшие.

Есть ли какио-либо формальное описание такой задачи?
Кто-нибудь может посоветовать алгоритм или источник, где лучше
всего поискать?

Удачи,
DaD

Здравствуйте, ddolgikh, Вы писали:

...

Очевидно, что задача NP — полная, т.е. глобальный оптимум гарантированно можно найти только полным перебором, т.е. в данном случае сложность — M! Поэтому подобные задачи решаются только приближенно. Один из возможных подходов:
На первом этапе строится некое приближенное решение, которое даже может содержать пересечения (например каждую точку внутри соединить с ближайшей точкой на границе). Затем полученное решение улучшается с использованием алгоритмов локального поиска. Из таких алгоритмов в последнее время очень популярен Tabu search. В инете куча материалов по этому поводу, правда как правило на английском.

Здравствуйте, Bell, Вы писали:

B>можно найти только полным перебором, т.е. в данном случае сложность — M!

Хт, этого хотелось бы избежать...
Кстати, где можно посмотреть, откуда будет "очевидно, что задача NP-полная"?

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

Удачи, DaD

Здравствуйте, DaDy, Вы писали:


DD>Хт, этого хотелось бы избежать...

DD>Кстати, где можно посмотреть, откуда будет "очевидно, что задача NP-полная"?
Вообще-то это мое ИМХО, доказательства для подобной задачи я не видел, но думаю, что это все-таки именно так.

DD>Похоже я немного не точно сформулировал задачу.
DD>Алгоритм может помещать точки на периметре как хочет, главное
DD>чтобы они были размещены равномерно, это меняет дело? (похоже не особо )
По-моему только усложняет...
DD>Ну и бог с ней с оптимальностью по длине, главное первое
DD>приближенное решение давало непересекающиеся отрезки, это возможно?
Можно попробовать так:
1. размещаем точки по периметру.
2. соединяем точку из прямоугольника с ближайшей точкой на периметре
3. если пересечений нет, берем следующую точку из прямоугольника , и идем на шаг 2. Иначе — на шаг4.
4. если еще есть точки на периметре, то помечаем текущую точку и берем следующую из непомеченных, идем на шаг 2. Иначе — шаг 5
5. разрываем предыдущий отрезок, и соединяем точку в прямоугольнике с другой точкой на периметре.


Это в общих чертах...

Здравствуйте, DaDy, Вы писали:

DD>...

DD>Похоже я немного не точно сформулировал задачу.
DD>Алгоритм может помещать точки на периметре как хочет, главное
DD>чтобы они были размещены равномерно, это меняет дело? (похоже не особо )
Попробуем так:

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

2) Начинаем перебирать точки на заданной гране, начиная, например слева (B1, B2, ...)

3) Для каждой поверхностной точки (Bi), перебираем все точки, связанные с заданной гранью (Сj), и еще не имеющие связей. Находим точку с минимальным углом A-Bi-Cj.
Так, например, для ситуации на рисунке, B1, будет связана с C2.
Далее, для слудующей точки на поверхности ...

Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, DaDy, Вы писали:

C>2) Начинаем перебирать точки на заданной гране, начиная, например слева (B1, B2, ...)

Браво!!!
Сейчас так и сделано В связи с этим вопрос: такая задача описана
где-нибудь и это известное решение?

Проблемы начинаются на пересечениях граней, например рассмотрим такой
простейший пример:


Очевидно, что алгоритм проходя по нижней грани найдет точку С1, т.к.
угол А-B1-C1 < A-B1-C2, при этом при проходе по боковой грани
алгоритм найдет точку С2. В результате найденные отрезки B1-C1 и D1-C2
пересекаются

Вижу два пути решения:
1) После построения решения все же проверять отрезки каждый с
каждым на сопрягающихся гранях (оптимизация — проверять только
для углов > 90)

2) Найти другой алгоритм

Какие будут мысли?

Удачи,
DaD

Здравствуйте, DaDy, Вы писали:

DD>Здравствуйте, Chorkov, Вы писали:

C>>Здравствуйте, DaDy, Вы писали:

C>>2) Начинаем перебирать точки на заданной гране, начиная, например слева (B1, B2, ...)

DD>Браво!!!
DD>Сейчас так и сделано В связи с этим вопрос: такая задача описана
DD>где-нибудь и это известное решение?

Не помню, просто первое первое, что пришло в голову. ...

DD>Проблемы начинаются на пересечениях граней, например рассмотрим такой
DD>простейший пример:
DD>

DD>Очевидно, что алгоритм проходя по нижней грани найдет точку С1, т.к.
DD>угол А-B1-C1 < A-B1-C2, при этом при проходе по боковой грани
DD>алгоритм найдет точку С2. В результате найденные отрезки B1-C1 и D1-C2
DD>пересекаются

Такая проблемма не возникнет, если сразу правильно распределить точки между гранями (согласно правилам из пункта (1) в предыдущем моем сообщении).
Например,при использовании идеологии "Связываение с ближайшей гранью", точка С1, окажется связана с вертикальной гранью, и не будет входить в перечисление свободных точек, при поиске партнера для В1, из вашего примера.
"Связываение с ближайшей гранью", однако, не гарантирует, что к каждой грани будет присоединено ровно столько точек, сколько на ней краевых точек.

Другой пример распределения точек между гранями:

Из вершин прамоугольника ABCD, проводим бессиктрисы.
Пусть они пересикаются в точках X и Y.
Будем связывать все точки из AXYD — с верхней гранью, BXYC — с нижниней, а треугольники AXB, CYD с боковыми гранями.
Очевидно, что ни один отрезок соединающий точку из BXYC с точкой на BC, не пересекает отрезок из CYD-CD.смсв
Теперь будем перемещать точки X и Y пока с каждой из граней не будет связано должное число точек.
Если задача с двумя точками не решается ( слишком неприятное распрадаление попалось ) можно добавить еще излом в середине отрезка XY.

Здравствуйте, Chorkov, Вы писали:

C>Если задача с двумя точками не решается ( слишком неприятное распрадаление попалось ) можно добавить еще излом в середине отрезка XY.

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

В остальном идея понятна, спасибо.

Удачи,
DaD

Здравствуйте, ddolgikh, Вы писали:

D>Не подскажите ли какой-либо общий алгоритм для решения следующей задачи:
D>Есть прямоугольник размерами ДхШ. Внутри произвольно расположены
D>М точек. По периметру прямоугольника равномено расположены еще
D>М точек. Необходимо:
D>1) Для каждой точки в поле найти точку на периметре таким образом,
D>чтобы отрезки соединяющие точки не пересекались.
D>2) Если возможно несколько вариантов, то выбрать тот при котором
D>длины отрезков наименьшие.

Есть алгоритм для несколько упрощенного варианта этой задачи. Упрощение состоит в том, что накладывается ограничение на множество точек, а именно,что никакие 3 точки не должны лежать на одной прямой. А также не идет речь о минимизации общих длин.
Может быть можно что-нибудь придумать на его основе.

Алгоритм строится на основе метода "разделяй и властвуй".
1. "Разделяй" — разобъем задачу на две задачи мешьшей размерности:
1.1. Возьмем произвольную точку на периметре D (лучше угловую) и отсортируем по углу относительно нее все остальные точки (на периметре и внутри)
1.2. Последовательно будем рассматривать отрезки (D,Pi) считая сколько точек (первого(на периметре) Cd и второго типа Ci) мы уже просмотрели.
1.3. Если в некоторый момент Pi — точка второго типа и Cd == Ci, то мы нашли прямую которая разбивает все множество точек на две независимые подзадачи. Поскольку с обоих сторон от этой прямой одинаковое количество точек разных типов.
2. "Властвуй" — записываем найденную прямую в решение и решенаем две оставшиеся подзадачи меньшей размерности.
Почему таким образом можно разбить задачу на две подзадачи и что это всегда возможно, доказывается от противного с учетом ограничения на 3 точки.
Сложность алгоритма O(n^2 log(n)).

Что касается книжки, то данная задачка приводится в виде упражнения (правда без решения в главе по геометрии в книге "Алгоритмы построение и анализ" Т. Кормен,Ч. Лейзерсон, Р.Ривест.- большая такая толстая книжка формата A4 сейчас проддается во многих магазинах,

Извините не подписал предыдущее сообщение.
Виктор.