Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 6322
Последний выпуск: 19.06.2015

Задача о прямоугольниках (чисто алгоритмическая)

350
11 октября 2006 года
cheburator
589 / / 01.06.2006
Когда ночью не спится, включаю телик. Как-то раз напоролся на игру "деньги на проводе" по ТНТ. Вот и возникла идея решить одну из предложенных там задач в общем случае.

Задача такая. Дан прямоугольник (n строк, m столбцов), "разлинованный" на клетки (как тетрадь в клетку). Но некоторые "границы" между клетками отсутствуют. Нужно подсчитать количество прямоугольников, образуемых этой системой клеток. Думаю, не нужно объяснять, что в данном случае считать прямоугольником: прямоугольником является любая система клеток, ограничиваемая двумя вертикальными и двумя горизонтальными линиями, при этом, естественно, линии не должны проходить по непрочерченным "стенкам".
В приведенном ниже примере пять прямоугольников:
____
|_|_|
|___|
- левая верхняя клетка;
- правая верхняя клетка;
- прямоугольник, образованный двумя верхними клетками;
- нижний прямоугольник;
- вся система тоже является прямоугольником.

Мой вариант решения использует комбинаторику. Обозначения: n - размер генерального прямоугольника в ширину, m - размер генерального прямоугольника в длину, k - количество "непрочерченных" стенок. Абсциссы и ординаты как клеток, так и стенок нумеруются по математическим правилам - от единицы.

Прямоугольник однозначно идентифицируется парой противоположных углов - скажем, левым верхним и правым нижним. Поэтому мы можем подсчитать число прямоугольников, которые мы могли бы образовать, если бы все стенки между клетками существовали, были "прочерчены".
Очевидно, абсциссу левого верхнего угла мы можем выбрать n способами. Причем для каждой выбранной абсциссы левого верхнего угла абсцисса правого нижнего выбирается n+1-i способами, где i - абсцисса текущего левого верхнего угла. Соответственно, число способов образовать абсциссу левого верхнего угла и абсциссу правого нижнего угла равно:
Сумма от i=1 по n (n+1-i) = сумма от i=1 по n (i) = n * (n+1) / 2.
Независимо от выбора абсциссы, ординаты мы можем выбрать
m (m+1) / 2 способами. Благодаря независимости выбора абсциссы и ординаты, получаем общее количество способов (обозначим через S0):
S0 = n * (n+1) / 2 * m * (m+1) / 2.
Теперь для каждой непрочерченной стенки (в нашем примере такая стенка одна) число прямоугольников, которое нельзя провести через данную стенку. Сумму этих чисел обозначим S1.
Используя метод включения и исключения, возьмем полученное число S0 и вычтем из него число прямоугольников, которое нельзя провести через каждую отдельно взятую стенку, т. е. S1. Но при этом мы дважды вычли прямоугольники, которые нельзя провести одновременно через две стенки, поэтому подсчитаем их количество и прибавим их, и т. д.:

S = S0 + S1 - S2 + S3 - ... (+-) Sk

"Непрочерченную стенку" можно идентифицировать координатой клетки, для которой эта стенка является левой (если стенка вертикальная) или верхней (если горизонтальная). Если же стенка находится в самом низу генерального прямоугольника, ей не соответствует ни одна клетка; присвоим ей ординату m+1; если она находится на правой "стене" генерального прямоугольника, т. е. опять же вне зоны клеток, присвоим ей абсциссу n+1. Таким образом, абсцисса стенки меняется от 1 до n+1, ордината от 1 до m+1.

Тогда число S1 (число прямоугольников, проходящих через каждую "непрочерченную" стенку, просуммировано по всем таким стенкам) можно посчитать по нижеследующим формулам.

1. Если стенка горизонтальная, через нее нельзя провести i * (n+1-i) * m прямоугольников.
2. Если стенка вертикальная, через нее нельзя провести j * (m+1-j) * n прямоугольников.
Здесь (i, j) - соответственно абсцисса и ордината стенки. Отмечу, что для горизонтальной стенки число не зависит от ее ординаты, а для вертикальной - от абсциссы.
Очевидно, для подсчета S1 требуется время порядка O(k), где k - количество непрочерченных стенок.

Теперь нужно сосчитать число S2 (число прямоугольников, проходящих через пару "непрочерченных" стенок, просуммировано по всевозможным парам стенок).

1. Для пары горизонтальных стенок (i1, j1); (i2, j2):
1а. Если их ординаты не равны (j1 <> j2), т. е. стенки лежат на противоположных стенках прямоугольника, имеем формулу i1 * (n+1-i2)
(предполагается, что i1 <= i2, в противном случае просто переобозначим их).
1б. Если их ординаты равны (j1 = j2), т. е. стенки лежат на одной стороне прямоугольника, имеем формулу i1 * (n+1-i2) * m (опять же предполагается i1 <= i2).
2. Для пары вертикальных стенок формулы идентичны.
3. Для пары "горизонтальная-вертикальная" (обозначим через (i1, j1) горизонтальную, (i2, j2) вертикальную):
3а. Если i1 < i2 и j2 < j1: i1*j2
3б. Если i1 < i2 и j2 >= j1: i1 * (m+1-j2)
3в. Если i1 >= i2 и j2 < j1: (n+1-i1) * j2
3г. Если i1 >= i2 и j2 >= j1: (n+1-i1) * (m+1-j2)
Число всевозможных пар стенок равно C (2, k) = k! / (2! * (k-2)!) = k * (k-1) / 2, т. е. для подсчета S2 требуется время порядка O (k^2), где k - количество стенок.

Формулы для S3 и т. д. я приводить не буду, поскольку это займет много места. Однако добавлю, что можно вывести формулы и для S4; а дальнейшие случаи сводятся к S1-S4 (поскольку прямоугольник имеет только 4 стороны).

Итак, выводы. Для подсчета числа прямоугольников используется метод включения и исключения, для чего нам нужно провести 1 вычисление для подсчета S0, k вычислений для подсчета S1, k (k-1) / 2 вычислений для подсчета S2 и т. д. Получим общее число вычислений:
Сумма от i=0 по k C(i,k) = 2^k.
Таким образом, алгоритмическая сложность такого решения O (2^k).
Тут есть возможность для оптимизации. Если при вычислении какого-то из чисел Si мы получили ноль, дальнейшие числа вычислять не имеет смысла - они также будут нулевыми (если ни один прямоугольник не проходит, скажем, через произвольную тройку стенок, то ни один прямоугольник не будет также проходить и через четверку стенок). Поэтому в этот момент имеет смысл прервать вычисления и выдать результат. Однако оценку сложности такого оптимизированного алгоритма провести сложно, поскольку нельзя даже сказать определённо, с какой вероятностью алгоритм прервется на каком-то определенном шаге, поэтому будем считать, что сложность алгоритма не хуже O (2^k).
Отмечу, что если решать задачу "напролом", простым перебором вариантов, сложность задачи составит O (2^(n*m)). Однако, если учесть, что для каждого варианта прямоугольника нужно выполнять поиск стенок, через которые он может проходить, и предположить, что время поиска логарифмическое, получим несколько худшее время: O (2^(n*m) * log2 k).

Внимание, вопрос :) Есть ли более быстрый алгоритм?
Страницы:
3
30 октября 2006 года
Green
4.8K / / 20.01.2000
[QUOTE=cheburator]Согласен. Но согласись и ты: машина, способная за разумное время посчитать "большой" случай, т. е. имеющая хорошие "мозги", уж наверняка имеет и достаточное количество памяти. Не интересовался статистикой, но думаю, что с ростом одного ресурса у машин второй ресурс вряд ли становится меньше.
К тому же, расходы времени - кубичны, расходы памяти на такой массив квадратичны. То бишь относительный расход памяти устремляется к нулю.[/QUOTE]
Это типичная ошибка - заменять оптимизацию алгоритмическую, оптимизацией "железной". Иногда это просто невозможно. :)

В данном алгоритме можно обойтись памятью 2*m*n (заметь, умножить на 2, а не в степени).
Т.е. для прямоугольника 1000x1000 потребуется меньше 4Mb памяти.
3
04 ноября 2006 года
Green
4.8K / / 20.01.2000
[QUOTE=Мerlin]В дополнительный массив записывается длина непрерывной гор. линии отсчитывая слева. В k-й ячейке есть прямоугольник ширины t, если есть ребра с обеих сторон и длина гор.линии в k-й позиции больше равна t.
[/QUOTE]
Да, есть дополнительный массив n*m.
Но в него записывается количество пропущенных нижних ребер начиная слева.
Если значение для левой границы и для правой одинаково, то это значит, что внутри прямоугольника нет пропущенных нижних ребер.

Таблица строиться единожды в самом начале алгоритма. Построение таблицы занимает O(n*m) времени, проверка произвоидится за константное время. Т.о. общий алгоритм не выходит за кубическое время.

[QUOTE=Мerlin]
Только в алгоритме (пост #16) НЕТ НИ СЛОВА о доп. массиве.
Даже во время проверки прямоугольников ширины 1, она не строится. Т.е. она строится уже после этого или ты просто что-то не досказал?
[/QUOTE]
Ну не мог же я сразу расскрыть все карты. Должна была быть какая-то загадка, интрига. :)
63
09 ноября 2006 года
Zorkus
2.6K / / 04.11.2006
[QUOTE=Green]Это типичная ошибка - заменять оптимизацию алгоритмическую, оптимизацией "железной". Иногда это просто невозможно. :)
[/QUOTE]
О железе нельзя забывать. Не зря на олимпиадах участникам сообщаются хар-ки железа сервера, на котором тестится код. При жестких ограничениях на время задача, проходящая на железе Атлон х2 3800 не пройдет на сервере с процем 800 М.
3
13 ноября 2006 года
Green
4.8K / / 20.01.2000
Коллега предложил вариант (n^2)*log(n).
Непростой алгоритм, но впечатляет.
Может, кто-то сделает за n^2 ?
54K
06 декабря 2009 года
Станислав Володарский
4 / / 06.12.2009
Спустя три года :).

mnlog(mn) можно посмотреть здесь:
http://slavav.ru/contours/

Конечно, хочется быстрее...
3
08 декабря 2009 года
Green
4.8K / / 20.01.2000
Спустя три года :).

mnlog(mn) можно посмотреть здесь:
http://slavav.ru/contours/

Конечно, хочется быстрее...



Слава, ты как всегда основателен и педагогичен... :)
Чувствуется рука мастера. Даже я всё понял из объяснения.

Уважаемые форумчане, Станислав - это и есть тот коллега, о котором я часто упоминал (в основном, хорошими словами).

Кстати, люди требуют новых задач. Так что, Слава, если таковые появятся, пожалуйста, заливай их сюда.

А пока небольшая загадка: найди Славу на фотографиях сайта creatstudios.com :D

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог