Блог

Существует набор сегментов {(a_i,b_i) with i = 1, ..., n} , 0 <= a_i < b_i <= 1 которые должны быть расположены в N строках [0,1] без перекрытия.

Например, если набор может состоять из {(0.35,0.41), (0.40,0.43), (0.47,0.88)} и N >= 2 , можно упорядочить сегменты без перекрытий. N = 1 Это невозможно, потому что первый и второй сегменты перекрываются.

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

Что, если некоторые из сегментов имеют ограничения на строку, на которой они должны быть размещены? Например, сегмент (a_2,b_2) может быть размещен только на 3-й строке, и его записывают как (a_2,b_2;3) .

Одна из возможных ситуаций заключается в следующем: {(0.45,0.56;-), (0.48,0.67;-), (0.66,0.70;2), (0.68,0.71;-)} и N = 2 . Если поместить первый сегмент в первую строку, второй сегмент должен находиться на второй строке, а третий сегмент не может выполнить ограничение. Напротив, если первый сегмент помещен во вторую строку, второй сегмент идет в первой строке, третий — во второй строке, выполняющей ограничение, и последний — в первой строке.

Что я пробовал

1. Попробуйте каждую комбинацию, которая удовлетворяет ограничениям. В последнем примере {1,2}x{1,2}x{2}x{1,2} после первого без какого-либо перекрытия программа возвращает комбинацию, которая является решением проблемы. Конечно, это работает, конечно, это медленно.

2. Нарисуйте линию [0,1] , отмеченную точками, которые являются границами хотя бы одного сегмента. Создайте список I интервалов, состоящий из двух последовательных точек. Для каждого элемента I возьмите список S сегментов, который его покрывает. Для каждого подмножества S' S постройте набор A' , равный объединению номеров строк, в которых они разрешены. Например, для S' = {(0.5,0.6;1,2), (0.4,0.7;2)} , A' = {1, 2} . Если мощность A' меньше мощности S' , решения нет. К сожалению, обратное не всегда верно.

3. Сканируйте каждый интервал в точке 2. и удаляйте линии, на которых сегмент не может быть размещен, в соответствии с ограничениями на другие сегменты. Например, если сегмент ограничен в строке 2, это невозможно для любого другого сегмента, который имеет с ним пересечение. Продолжайте просматривать список интервалов, пока сокращения не станут невозможными. Затем используйте базовый алгоритм в 1. с этим подмножеством возможных комбинаций.

4. Нарисуйте квадратную матрицу A размера n ( n быть количеством сегментов). a_ij равно 1 , если они перекрываются, 0 если нет. Разрешены только определенные операции с матрицей в зависимости от того, имеют ли сегменты ограничения или нет (если две строки меняются местами, необходимо поменять местами одни и те же столбцы, сегменты с ограничениями нельзя произвольно менять местами). Если можно получить матрицу, содержащую несколько диагональных блоков <= N , которые являются единичной матрицей, решение есть. Не уверен, что это жизнеспособный вариант, и если это имеет смысл.

5. Рассмотрим I , S , S' и A' , как определено в 2. . Если мощность A' меньше мощности S' , прервать (решения нет). Если мощность A' равна мощности S' , удалите номера строк A' из сегментов, которые пересекают каждый элемент S' .

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

   Например, N = 3 , S = {(0.5,0.6;1,2), (0.4,0.7;2), (0.5,0.6;1,2,3)} . Одним из подмножеств является S' = {(0.5,0.6;1,2), (0.4,0.7;2)} то, для которого имеется A' = {1,2} . Мощность S' равна мощности A' , поэтому нужно удалить {1,2} из строк, разрешенных для каждого сегмента, которого нет S' . Получается S = {(0.5,0.6;1,2), (0.4,0.7;2), (0.5,0.6;3)} . Делая то же самое с S' = {(0.4,0.7;2)} , 2 удаляется из первого сегмента и получается S = {(0.5,0.6;1), (0.4,0.7;2), (0.5,0.6;3)} , что является (единственным возможным) решением.

   Контрпример: для N = 2 и {(0.5,0.6;-), (0.55,0.7;-), (0.65,0.8;-)} не каждая комбинация из {1,2}x{1,2}x{1,2} является решением. Причина связана с симметрией (истинных) решений. Если после каждого полного запуска алгоритма один из сегментов фиксируется на одной из его разрешенных строк (тем самым нарушая симметрию) и перезапускает алгоритм, получается решение для этого предлагаемого набора.

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

6. Если 5. верно, можно ли вычислить решение для n сегментов из решения для n-1 сегментов?

Замечания (из комментариев и от меня)

Ограничения, требующие, чтобы некоторые сегменты располагались на определенных строках, могут быть немного ослаблены, поскольку после завершения решения вы можете полностью изменить нумерацию строк, не меняя, перекрываются ли сегменты в одной строке или нет. Так, например, если предполагается, что два сегмента должны быть в строке 5, все это на самом деле означает, что они должны быть в одной строке; и если один сегмент должен быть в строке 3, а другой в строке 7, все это на самом деле означает, что они должны быть в разныхстроки.

Если какая-либо точка x не покрыта каким-либо сегментом, задачу можно разделить на 2 задачи, имеющие строки [0,x] и [x,1] длину, и два набора отдельных сегментов. Поэтому нужно предположить, что каждая точка в [0,1] покрыта хотя бы одним сегментом.

Я думаю, что эту проблему можно перевести на раскраску вершин:

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

Вариацию с ограничениями можно описать как раскраску списка.