ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexey Pakhunov                      2:5020/400     29 May 2002  18:47:55
 To : All
 Subject : [the set-covering problem] Вариации на тему...
 -------------------------------------------------------------------------------- 
 

 Hello, All.
 
 Вот такая интересная задача:
 
 Есть прямоугольное поле M*N, заполненное нулями и единицами (прямоугольная
 сетка). Все ячейки, заполненные единицами покрыты множеством
 непересекающихся прямоугольников S1. Координаты и размеры каждого известны.
 
 Hапример:
 
     X1  X2  X3  X4  X5
    +-------+
 Y1 | 1   1 | 0   0   0         Множество S1:
    |       |   +-------+
 Y2 | 1   1 | 0 | 1   1 |    (X1, Y1) - (X2, Y2)
    +-------+   |       |
 Y3   0   0   0 | 1   1 |    (X4, Y2) - (X5, Y3)
                +-------+
 Y4   0   0   0   0   0      (X2, Y5) - (X4, Y5)
        +-----------+
 Y5   0 | 1   1   1 | 0
        +-----------+
 
 Hужно покрыть все оставшееся пространство (заполненное нулями) множеством
 непересекающихся прямоугольников S0 таким обазом, чтобы количество
 прямоугольников было минимальным (близко к минимальному).
 
 Дополнительные условия:
 
 - Прямоугольники из S1 не должны пересекаться с прямоугольниками из S0.
 Вообще не должно быть пересекающихся прямоугольников.
 - Каждая строка должна содержать хотя бы один прямоугольник (из S1 или S0)
 единичной высоты.
 - Каждый столбец должен содержать хотя бы один прямоугольник (из S1 или S0)
 единичной ширины.
 
 Кроме того, в силу особенностей алгоритма расстановки 1 и 0:
 
 - Hикакие две строки, заполненные исключительно 0, не могут соприкасаться.
 - Hикакие два столбца, заполненные исключительно 0, не могут соприкасаться.
 
 Примечание: оптимального решения не требуется. (Вследствие NP-полноты
 задачи). Требуется алгоритм, работающий быстро и дающий близкий к
 оптимальному результат.
 
 Для приведенного выше примера решением задачи может быть следующее множество
 S0:
 
 (X3, Y1) - (X5, Y1)
 (X3, Y2) - (X3, Y2)
 (X1, Y3) - (X1, Y5)
 (X2, Y3) - (X3, Y2)
 (X2, Y4) - (X2, Y4)
 (X3, Y4) - (X3, Y4)
 (X4, Y4) - (X4, Y4)
 (X5, Y4) - (X5, Y5)
 
     X1  X2  X3  X4  X5
 
            +-----------+
 Y1   1   1 | 0   0   0 |
            +---+-------+
 Y2   1   1 | 0 | 1   1
    +---+---+---+
 Y3 | 0 | 0   0 | 1   1
    |   +---+---+---+---+
 Y4 | 0 | 0 | 0 | 0 | 0 |
    |   +---+---+---+   |
 Y5 | 0 | 1   1   1 | 0 |
    +---+           +---+
 With best regards,
   Alexey Pakhunov.
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор