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

Ваш аккаунт

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

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

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

Разминка для ума

3
22 октября 2005 года
Green
4.8K / / 20.01.2000
Интересную задачку подкинули:
Цитата:

Есть клетчатое поле NxN.
Клетки этого поля могут быть белыми и черными в некотором хаотичном порядке.
Необходимо найти площадь максимального белого прямоугольника.


Ну что, кто может предложить алгоритм, а заодно и определить его асимптотическую сложность?
Кстати, может кто предложит к какой сложности надо стремится? :)

P.S. Чужие варианты (если кто знает ответ) не предлагать, только свои мысли.

Страницы:
239
10 ноября 2005 года
Dolonet
1.7K / / 20.05.2000
Цитата:
Originally posted by Green
Чтоб не развивать опять наш минискандал, подождем устоявшегося алгоритма. :)

Так какая степень тебя устроит от размерности стороны доски? n^6? Есть мысль.

Один проход (n^2) - записываем все возможные "начала" белого прямоугольника и два параметра - максимальную его ширину и высоту.

Промежуточный итог - имеем массив только тех элементов, которые могут быть верхними левыми углами нашего клиента. Замечательно. Теперь проходим по нашему новому массиву (напр $results1[$xpos][$ypos][$width][$height]), что в среднем случае уже не n^2, a (n^2)/(10~50). И, проходя, проверяем ширину и высоту исходя из того, что меньше чем $maxfound, который пополняется, нам искать не интересно (не тратим время на лишние проверки). К концу прохода мы имеем результат.

Итого получается меньше чем полтора раза по n^2, если учесть, что n - размерность доски, т.е. квадратный корень из количества элементов.

443
10 ноября 2005 года
REmindER
292 / / 23.03.2003
s[][0] - стек высот;
s[][1] - счетчик повторений высоты.

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

Цитата:
Это аналог моего первого шага, т.е. построение проекций:
 
Код:
if(matrix[y][x]==1)
                    m[x]++;
                else
                    m[x]=0;
                h=m[x];

Итерация x==n введена для раскрутки стека. Так?



Абсолютно. Для раскрутки в конце строки.

Цитата:

Не понятен вот этот участок:
 
Код:
if(h==s[0])
                if(h!=0)
                    s[1]+=(c+1);



Да очень просто. Нет смысла итерировать счетчик нулевой высоты. Кроме того это связано с 'c'.

Цитата:

...В защиту своей реализации могу сказать, что два цикла лучше одного (IMHO) тем, что внутри них меньше условных операций.



Если выбросить вычисление высоты, то всего-то два, т.к. два последних if-а можно сделать через else. А у тебя сколько?

О 'c'.
Рассмотрим тот самый первый рисунок, начиная с 6-ой строки и 6-й клетки сразу:

Код:
проход: | условие: | i | c | стек высот / счетч.
начало               0       пуст          
1         1>0        1   0   1            1

2         2>1        2   0   1,2          1,1

3         1<2(max)   1   1   1            1
3         1=1        1   1   1            1+1+1=3

4         3>1        2   0   1,3          1,1

5         1<3(max)   1   1   1            3
5         1=1        1   1   1            3+1+1=5

6         0<1(max)   0   5   пуст


или такой рисунок с 5-ой строки и со 2-й клетки:

Код:
-X----
-XX---
-XXX--
-XXXXX
-XXXXX

проход: | условие: | i | c | стек высот / счетч.
начало               0       пуст          
1         5>0        1   0   5            1

2         4<5(max)   0   1   пуст
2         4>0        1   1   4            1+1=2

3         3<4(max)   0   2   пуст
3         3>0        1   2   3            1+2=3

4         2<3(max)   0   3   пуст        
4         2>0        1   3   2            1+3=4

5         2=2        1   0   2            4+1=5

6         0<2(max)   0   5   пуст


В целом - так. Хотя может можно сделать раскрутку в конце строки... Конечно, получается, что твое решение, так сказать, наглядней и проще.
443
10 ноября 2005 года
REmindER
292 / / 23.03.2003
Цитата:
Originally posted by Dolonet
Так какая степень тебя устроит от размерности стороны доски? n^6? Есть мысль.

Один проход (n^2) - записываем все возможные "начала" белого прямоугольника и два параметра - максимальную его ширину и высоту.

Промежуточный итог - имеем массив только тех элементов, которые могут быть верхними левыми углами нашего клиента. Замечательно. Теперь проходим по нашему новому массиву (напр $results1[$xpos][$ypos][$width][$height]), что в среднем случае уже не n^2, a (n^2)/(10~50). И, проходя, проверяем ширину и высоту исходя из того, что меньше чем $maxfound, который пополняется, нам искать не интересно (не тратим время на лишние проверки). К концу прохода мы имеем результат.

Итого получается меньше чем полтора раза по n^2, если учесть, что n - размерность доски, т.е. квадратный корень из количества элементов.


А изначально подразумевалось разве не общее количество замкнутых блоков операций для одной клетки? Имеется в виду то, что тут все равно придется просмотреть всю матрицу поэлементно.

239
10 ноября 2005 года
Dolonet
1.7K / / 20.05.2000
Цитата:
Originally posted by REmindER
А изначально подразумевалось разве не общее количество замкнутых блоков операций для одной клетки? Имеется в виду то, что тут все равно придется просмотреть всю матрицу поэлементно.

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

443
10 ноября 2005 года
REmindER
292 / / 23.03.2003
Цитата:
Originally posted by Dolonet
Ее прийдется просмотреть поэлементно полюбому, мы не можем пропустить элемент (хотя можем, конечно, но только действуя через черные методом "от противного"). Другой вопрос, как много раз мы это сделаем и сколько операций нам надо будет произвести на каждой.


Думаю, оптимальней в этом плане алгоритма Green'а не придумать, т.к. его можно свести к одному проходу.

239
10 ноября 2005 года
Dolonet
1.7K / / 20.05.2000
Цитата:
Originally posted by REmindER
Думаю, оптимальней в этом плане алгоритма Green'а не придумать, т.к. его можно свести к одному проходу.

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

443
10 ноября 2005 года
REmindER
292 / / 23.03.2003
Цитата:
Originally posted by Dolonet
Один проход не всегда лучше двух. Мои полтора тоже ничего. Т.к. одни и те же клетки дважды никогда не будут проверяться. Т.е. количество проверок будет строго меньше количества клеток. Всреднем в два-четыре раза, как я могу подсчитать на сей момент. Это уже что-то.


Мне кажется, тут надо обратить внимание на то, что подразумевается под проверкой. Собственно, это зависит от алгоритма.

443
10 ноября 2005 года
REmindER
292 / / 23.03.2003
Если брать проверку как что-то, то вопрос в том, когда это "что-то" применить. Каким будет соотношение его внутренней сложности к сложности выборки. Тут необходима конкретизация алгоритма.
239
10 ноября 2005 года
Dolonet
1.7K / / 20.05.2000
Цитата:
Originally posted by REmindER
Если брать проверку как что-то, то вопрос в том, когда это "что-то" применить. Каким будет соотношение его внутренней сложности к сложности выборки. Тут необходима конкретизация алгоритма.

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

То, что я сначала написал в два прохода, делается, конечно, в один.

443
10 ноября 2005 года
REmindER
292 / / 23.03.2003
Цитата:
Originally posted by Dolonet
Я предлагаю алгоритм, в котором будет естественно иерархия ифоф с глубиной, скажем, четыре вложенности (не рекурсия, конечно), и который обратится по факту проверить вообще клетка черная или белая количество раз меньшее количесва клеток примерно в полтора раза. Думаю, что быстрее ничего не придумать.

То, что я сначала написал в два прохода, делается, конечно, в один.



Не совсем понял. Нельзя ли пояснение?

443
11 ноября 2005 года
REmindER
292 / / 23.03.2003
Кстати, совсем необязательно пропускать итерацию нулевой высоты. Т.е. алгоритм будет таким:
Код:
s[0][0]=0;

for(y=0;y<n;y++)
{
i=0;

for(x=0;x<=n;x++)
  {
  c=0;

  if(x==n) h=0; else
    {
    if(matrix[y][x]==1) m[x]++; else m[x]=0;
    h=m[x];
    }

  if(h<s[0])
    {
    while(h<s[0])
      {
      ...max s[0]*(s[1]+c)
      c+=s[1];
      i--;
      }
    }

  if(h==s[0]) s[1]+=(c+1); else
    {
    i++;
    s[0]=h;
    s[1]=c+1;
    };
  };
};
443
11 ноября 2005 года
REmindER
292 / / 23.03.2003
Короче, каждый о своем... Может, эта тема уже себя изжила?
239
11 ноября 2005 года
Dolonet
1.7K / / 20.05.2000
Цитата:
Originally posted by REmindER
Не совсем понял. Нельзя ли пояснение?

Проходим по каждому элементу. Причем, естественно, не поклеточно, а диагоналями. т.е. для матрицы 10 на 10 действуем так: (1,1) (3,1) (2,2) (1,3) (5,1) (4,2) etc. если попадаем на белую клетку, то анализируем ситуацию вверх и влево с учетом того, что уже знаем.

Алгоритм достаточно непросто описать, но логика примерно такая.

3
11 ноября 2005 года
Green
4.8K / / 20.01.2000
Цитата:
Originally posted by REmindER
Конечно, получается, что твое решение, так сказать, наглядней и проще.


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

Mоngооsе предлагает совершенно иной вариант алгоритма. Правда пока не видно его преимуществ, т.к. не определен ещё второй шаг, а первый (IMHO) не приближает к решению.

Алгоритм Dolonet я пока не понимаю, т.к. он уж очень абстрактен.
Что касается "начал белого прямоугольника", то их действительно будет N^2, а вот возможных длин и высот только для одного такого "начала" N^3, а для всех прямоугольников в общем случае N^6.

239
11 ноября 2005 года
Dolonet
1.7K / / 20.05.2000
Цитата:
Originally posted by Green
Алгоритм Dolonet я пока не понимаю, т.к. он уж очень абстрактен.
Что касается "начал белого прямоугольника", то их действительно будет N^2, а вот возможных длин и высот только для одного такого "начала" N^3, а для всех прямоугольников в общем случае N^6.

Мой алгоритм никогда не будет проверять одну и ту же клетку дважды. Т.е. спрашивать ее, черная она или белая. Поэтому n^6 тут не получается. получится меньше чем во второй в абсолютно любом случае.

Мне нарисовать схему алгоритма?

3
11 ноября 2005 года
Green
4.8K / / 20.01.2000
Цитата:
Originally posted by Dolonet
Мне нарисовать схему алгоритма?


давай

239
11 ноября 2005 года
Dolonet
1.7K / / 20.05.2000
Цитата:
Originally posted by Green
давай

Ок. Только в понедельник, как из Дании вернусь )

43K
10 апреля 2009 года
Imperator_of_RusFed
9 / / 26.02.2009
В чем прикол задачи? Максимальная площадь-n*n!
3
11 апреля 2009 года
Green
4.8K / / 20.01.2000
Цитата: Imperator_of_RusFed
В чем прикол задачи? Максимальная площадь-n*n!


Ну а ты подумай, тема то называется "Разминка для ума".

43K
12 апреля 2009 года
Imperator_of_RusFed
9 / / 26.02.2009
Черных и Белых одинаковое кол-во?
255
12 апреля 2009 года
Dart Bobr
1.4K / / 09.04.2004
А что есть претензии на дискриминацию по цвету? :D
43K
12 апреля 2009 года
Imperator_of_RusFed
9 / / 26.02.2009
Пардон Белых и Афроамериканских...:)
41K
02 мая 2009 года
vakmus
11 / / 25.10.2008
Я, признаюсь, тему не читал полностью, но может быть кого-нибудь заинтересуют мои соображения.
Я не готов дать какой-либо хороший алгоритм для решения задачи, но мне придумались две вещи, которые могут задачу несколько упростить.

Для начала, давайте будем рассматривать заданный квадрат как граф, в котором его вершины (квадратики) соединены ребрами со своими соседями, плюс к том из условия ясно, что каждая из вершин рассматриваемого графа имеет вес: либо 0, либо 1. Несложно, с помощью поиска в ширину или в глубину, выделить все области заданного квадрата, все "квадратики" в которых имели бы одинаковый вес. Если я не ошибаюсь, сложность этой операции не привысит O(N*N). Теперь поиск прямоугольников можно будет осуществлять лишь внутри конкретной области, число которых, вообще говоря, не может превысить N*N.

И о поиске. Будем считать, что все квадратики (вершины) упорядочены. Например, заданы в виде двумерного массива. При этом вершина (a_n,b_m) (n,m = 0..(N-1)) смежна с (a_{n-1},b_m), (a_{n+1},b_m), (a_n,b_{m-1}), (a_n,b_{m+1}), если таковые существуют. Давайте выберем систему счисления с основанием B большим N. Теперь в нашем графе, кроме имеющегося веса вершин (раскраска), добавим еще и другой по следующему правилу (a_n,b_m).новый_вес := (B в степени (n+1));
Теперь, стоит заметить, что какой бы мы не взяли прямоугольник составленный из квадратиков, его суммарный новый_вес будет равен cc...c0...0, т.е. будет "состоять" лишь из одних-и-те-же-цифр-а-за-ними-нулей (нули, конечно, опциальны). Просуммировав все "c" из получившейся суммы имеем площадь прямоугольника.
31K
14 апреля 2010 года
serg76
2 / / 23.07.2007
зы тему только нашел

Цитата: Green
Ладно расскажу первый шаг N^2 алгоритма:

Идем по столбцам и считаем белые клетки, при встрече черной клетки сбрасываем счетчик. Т.о. формируем матрицу NxN.
Продемонстрирую на примере:
1 1 0 1
1 1 1 1
0 0 1 1
1 0 1 1
идем по первому столбцу и формируем столбец новой матрицы:
1
2
0
1
для второго столбца
1
2
0
0
Т.о. получаем матрицу
1 1 0 1
2 2 1 2
0 0 2 3
1 0 3 4
После чего исходная матрица нам не нужна.
Думаю, что не нужно объяснять, что сложность этой операции N^2.
Для бережливых до памяти замечу, что т.к. исходная матрица далее не нужна, мы можем писать новую матрицу прямо поверх старой.

Над следующим шагом подумайте сами.


не понял на каком вар-те остновились
имхо в таком вар-те будет работать для размеров не больше 7х7, при большем возможны ошибочные варианты

зыы тупого перебора не избежать, если ещё актуально выложу свои соображения

100.0M
04 ноября 2019 года
pelmenka
0 / / 04.11.2019
очень интересная тема!
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог