Матрица поиска для всех прямоугольников заданных размеров (выберите блоки мест)

Question

All

Я пытался понять, как выбрать, скажем, 15 билетов в одном блоке мест.

РЕДАКТИРОВАТЬ : проблема в том, как найти все прямоугольники заданных размеров (например, 3x5) свободных мест?

Ниже моя таблица, и запрос выбирает 4 последовательных места (или 15 или что-то еще), что хорошо ...

Но я хочу выбрать, скажем, 15 мест, они могут быть разбиты на несколько рядов, то есть 3 х 5, но я бы хотел, чтобы они были заблокированы вместе, т.е.

row 9 ..(some seats)..[5 seats]..(some seats)..
row 8 ..(some seats)..[5 seats]..(some seats)..
row 7 ..(some seats)..[5 seats]..(some seats)..

т.е. они были бы 3 ряда все друг перед другом. ряд 9 мест от 10 до 25, ряд 8 мест от 10 до 25, ряд 7 мест от 10 до 25.

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

Любое руководство в форме улучшения SQL или некоторого алгоритма или некоторого кода PHP. Я ломал свой мозг большую часть недели.

CREATE TABLE `seats` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `event_id` int(11) DEFAULT NULL,
  `performance` int(11) DEFAULT NULL,
  `block` int(11) DEFAULT NULL,
  `row` int(11) DEFAULT NULL,
  `seat` int(11) DEFAULT NULL,
  `status` int(10) DEFAULT 1,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

Мой запрос на сегодняшний день - который возвращает комбинации блоков X мест.

SELECT    a.event_id, a.performance, a.block,
          a.row, a.seat AS start_seat,
          a.seat + (4 - 1) AS end_seat,
          4 AS requested_seats,
          a.id AS start_allocation_id
FROM      seats a
          LEFT JOIN seats b ON
              a.event_id = b.event_id AND
              a.performance = b.performance AND
              a.block = b.block AND
              a.row = b.row AND
              a.seat < b.seat AND
              b.seat < a.seat + 4 AND
              b.status = 1
WHERE     a.status = 1 AND
          a.event_id = 1
GROUP BY  a.seat
HAVING COUNT(b.seat) + 1 = 4
ORDER BY performance

Заранее спасибо, нужна дополнительная информация, пожалуйста, спросите!

Answer 1

Эта проблема гораздо лучше решается за пределами mysql, на другом языке. Другими словами, у вас есть матрица мест, некоторые из которых заняты (серые):

и вы хотите найти все прямоугольники заданных размеров , скажем, 3x5. Вы можете сделать это очень эффективно с помощью двухпроцессорного алгоритма linear O(n) time (n - количество мест):

1) в первом проходе , проходите по столбцам снизу вверх, и для каждого места обозначьте количество последовательных мест, доступных до этого:

повтор, до:

2) во втором проходе , проходите по строкам и ищите как минимум 5 последовательных чисел, больших или равных 3:

итак, наконец, вы получите:

, которое дает решение: эти числовые последовательности (зеленые области) являются верхними краями 2 возможных прямоугольников 3x5 свободных мест.

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

Answer 2

Из вашего описания это не проблема базы данных, а проблема алгоритмическая.Я предлагаю схему листов, возможно, квадродерево или кривую заполнения пространства.Возможно, пространственный индекс в MySQL также поможет вам решить вашу проблему.Si подразделяют 2-ую плоскость на 4 плитки.

Answer 3

Я пришел сюда в поисках решения Python. Вот мой, который возвращает все позиции:

import numpy

s = '''0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 1 0 1 0 1
0 1 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0'''

area = 15
nrows = 6
ncols = 11
skip = 1

a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
    for c in range(ncols):
        if a[r][c] == skip:
            continue
        if r == 0:
            h[r][c] = 1
        else:
            h[r][c] = h[r-1][c]+1
        if c == 0:
            w[r][c] = 1
        else:
            w[r][c] = w[r][c-1]+1
        minw = w[r][c]
        for dh in range(h[r][c]):
            minw = min(minw, w[r-dh][c])
            if (dh+1)*minw == area:
                print(
                    'area', area, 'row', r, 'col', c,
                    'height', dh+1, 'width', minw)

Выход:

area 15 row 4 col 8 height 3 width 5
area 15 row 5 col 10 height 3 width 5

Answer 4

Вот простой подход. Это может быть недостаточно быстро для ваших нужд, но это место для начала.

Давайте упростим задачу и рассмотрим таблицу с именем seat, имеющую столбцы row, col и taken. Первые два являются целыми числами, а другое - логическим. Мы хотим найти значения row и col, ограниченные прямоугольниками определенного размера, где taken универсально ложно. Мы попробуем запрос, который перемещает прямоугольник и записывает сумму значений taken внутри. У прямоугольников, которые мы хотим, будет сумма нуля.

Скажем так, мы ищем 2x2 блока открытых мест. Вот запрос.

SELECT row, col,
       (select sum(taken) from seat as s2
               where s2.row >= s1.row and s2.row < s1.row + 2
                 and s2.col >= s1.col and s2.col < s1.col + 2) as count
       FROM seat as s1

Просто отфильтруйте выходные данные этого запроса, где count = 0. row и col будут обозначать верхний левый угол открытого блока. Последний недостаток заключается в том, что вам нужно отфильтровать верхние левые углы, которые срезаются слишком близко к правому или нижнему краям посадочных мест, поскольку это искусственно уменьшит их сумму (проверенный прямоугольник обрезается по краям посадочных мест). В случае блоков 2x2 это означает row < max(row) и col < max(col).

Теперь в случае поиска 15 смежных мест вы ищете прямоугольники 15x1, 1x15, 3x5 и 5x3. Вы можете превратить указанный выше запрос в хранимую процедуру, которая принимает параметры ширины и прямоугольника, и затем вызывать его с этими размерами, пока не найдете соответствие.

Answer 5

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

CREATE TABLE Seat {
   SeatID int,
   Status int,
   ...
   NorthID int,
   NorthWestID int,
   WestID int,
   ...
   NorthEastID int
}

По сути, я смогу создать «график мест» и пройти его согласно потребностям в запросах. Затем вы можете создавать запросы для получения определенных фигур или блоков.

Сетка 3х3 будет состоять из выбора открытого места, где также открыты непосредственно связанные места во всех направлениях. Да, это будет восемь JOINS, но попробуйте и оптимизируйте позже.

SELECT * FROM Seat x
INNER JOIN Seat n ON x.NorthID = n.SeatID
INNER JOIN Seat nw ON x.NorthWestID = n.SeatID
...

Блок 1x15 - это запрос для выбора открытого места, где вы присоединяетесь 14 к глубине вдоль EastID или WestID.

Возможно, вы можете обобщать и генерировать запросы программно.

PS: в зависимости от того, какой движок вы используете, у вас могут быть встроенные пространственные возможности.

Удачи.

Answer 6

Я бы просто написал запрос для каждой строки и скомбинировал бы его, используя UNION, если вы можете программно создать свой запрос, а затем просто используйте один и тот же запрос X раз, просто продолжайте добавлять их с UNION.

Из руководства mysql

UNION используется для объединения результата из нескольких операторов SELECT в один набор результатов.

Answer 7

    $nr_tickets = 15; // or whatever


// build an array of different configurations:
// since you always want people as close to eachother as possible this is a suggestion:

$configurations = array();
for($columns=1; $columns<=$nr_tickets; $columns++)
{
    $BLOCK = array();
    $remainder = $nr_tickets % $columns;
    // $nr_tickets - $remainder = greatest number divisible exactly by $i (columns) which is the number of rows you want.
    $rows = (($nr_ticket-$odd) / $i);
    //$configurations[$columns] = $rows // make a rectangle configuration or $columns x $rows with $remainder tickets left.
    $BLOCK[] = array_fill(0, $columns, array_fill(0, $rows, X); // multidimensional array
    for($a=0; $a<$odd; $a++)
    {

        // each of the remainder seats need to be 'stuck on to the block/rectangle of seats you already have, this can be done in
        // ($rows + $columns * 2) - $a ways for each of the consecutive non-assigned tickets
        /*
            lets say you have a block of 2x7 (s) with 1 (N) possible ticket left 
                   N  N  N  N  N  N  N  
            N  s  s  s  s  s  s  s  N 
            N  s  s  s  s  s  s  s  N   
               N  N  N  N  N  N  N 
        */
        // so basically we can add a ticket to each of the rows and for each of those configurations we need to add $a more
        // this may be simpler with a recursive function call that adds $a more for each 1 ticket you add here to a row or a column. 
    }


}



// now you can go select all different permutations of settings from the database and select one you like :)