@havemanyquestions

Как найти оптимальный путь для каждой пары элементов так, чтобы пути соединительных линий не пересекались?

Здравствуйте.
Имеется такой рисунок. Задавая пары: 1-5, 2-9 и т.д, необходимо их соединять линиями. Точки для возможных линий и соединений - квадрат, составленный из NxN элементов, где N - количество соединяемых элементов одной из соединяемых групп с макс. кол-вом элементов. Нужно соединять линии так, чтобы каждая пара была соединена с другой, и не возникало тупиковых ситуаций, как с красными линиями. При этом линии могут проходить или вертикально, или горизонтально, никаких диагоналей.

5afab152c5fa2972685870.png

К какой области знания относится рисование, алгоритм данного рисования, вычисление этого самого оптимального пути для каждой пары точек? Что это за алгоритмы, можно простые примеры для, например, двух групп элементов по 3 с каждой стороны?

Укажите хотя бы, в какую сторону смотреть?

P.S. И, как меня верно поправили, есть еще одно условие, забыл указать, линии не должны накладываться, но пересекаться могут.
P.P.S. Поправка. Решений нет при указанном условии. Добавляем еще одно условие - линии могут пересекаться по диагонали.
  • Вопрос задан
  • 133 просмотра
Решения вопроса 1
Пригласить эксперта
Ответы на вопрос 1
  • @forspamonly2
    задача в вашей формулировке не имеет решений, кроме вырожденных (когда всё сразу совпадает один к одному).

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

    во-вторых, у вас написано: "квадрат", а при одной свободной полосе, в части случаев его не будет хватать по длине. для того, чтобы поменять местами две линии, надо три ячейки в длину: из первой на свободную временную, со второй на первую, и со временной на вторую. так что, в худшем случае (множество линий, которые надо менять местами попарно), это не квадрат, а прямоугольник с соотношением сторон примерно два к трём.
    Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы