Задачку придумал для любителей сочинять алгоритмы. Что-то
все кому ни дам, никто работоспособного алгоритма не дает
(т.е. дают быстрые но ошибочные). Не пойму, она
действительно что ли сложная ?
Исходные данные: матрица NxN, содержит числа. Надо найти
прямоугольник внутри оной матрицы, сумма числел в котором
была бы максимальна (размеры прямоугольника неизвестны).
Параллельные алгоритмы неинтересны, они точно есть на гугле.
Очевидно, что решение не может быть быстрее N^2 (по числу
элементов). Требуется найти алгоритм сложности не
медленнее N^3 (мой) и узнать, возможны ли более быстрые.
Для нагула идей имеет смысл решить одномерный вариант
задачи, когда выбирается (непрерывный) подмассив
одномерного массива с максимальной суммой элементов
за линейное время (эту задачку можно найти на гугле).
Mikhail
Posted via RSDN NNTP Server 1.9
Re: задачка
От:
Аноним
Дата:
23.06.05 16:02
Оценка:
Здравствуйте, kittown, Вы писали:
K>Hi!
K>Задачку придумал для любителей сочинять алгоритмы. Что-то K>все кому ни дам, никто работоспособного алгоритма не дает K>(т.е. дают быстрые но ошибочные). Не пойму, она K>действительно что ли сложная ?
K>Исходные данные: матрица NxN, содержит числа. Надо найти K>прямоугольник внутри оной матрицы, сумма числел в котором K>была бы максимальна (размеры прямоугольника неизвестны). K>Параллельные алгоритмы неинтересны, они точно есть на гугле.
K>Очевидно, что решение не может быть быстрее N^2 (по числу K>элементов). Требуется найти алгоритм сложности не K>медленнее N^3 (мой) и узнать, возможны ли более быстрые.
K>Для нагула идей имеет смысл решить одномерный вариант K>задачи, когда выбирается (непрерывный) подмассив K>одномерного массива с максимальной суммой элементов K>за линейное время (эту задачку можно найти на гугле).
K>Mikhail
wrote: > > K>Исходные данные: матрица NxN, содержит числа. Надо найти > K>прямоугольник внутри оной матрицы, сумма числел в котором > K>была бы максимальна (размеры прямоугольника неизвестны). > K>Параллельные алгоритмы неинтересны, они точно есть на гугле. > > K>Очевидно, что решение не может быть быстрее N^2 (по числу > K>элементов). Требуется найти алгоритм сложности не > K>медленнее N^3 (мой) и узнать, возможны ли более быстрые. > решение
Это решение не той задачи.
Если бы нам надо было найти максимальный прямоугольник, все
числа в котором независимо друг от друга удовлетворяли бы
некоторому критерию, тогда это было бы решение.
Здравствуйте, kittown, Вы писали:
K>Исходные данные: матрица NxN, содержит числа. Надо найти прямоугольник внутри оной матрицы, сумма числел в котором была бы максимальна (размеры прямоугольника неизвестны).
Лобовое решение.
Пусть s(x,y1,y2) — сумма элементов в строках y1..y2 столбца x.
Если мы зафиксируем (y1,y2) — получится последовательность s(x).
За один проход (та самая разминочная подзадача) найдём (x1,x2) для которых сумма S(x1,x2,y1,y2) = sum s(x1)..s(x2) максимальна.
Очевидно, что нахождение s(x,y1,y2) тупым способом требует O(N) времени, так что на один проход мы потратим O(N^2).
Количество разных сочетаний y1,y2 — это C(N,2) = N*(N-1)/2, то есть на перебор всего-всего нам потребуется O(N^4).
Вроде бы, правильный алгоритм?
Его можно очевидным способом улучшить, разогнав до O(N^3).
(Это я крикнул "Первый, блин! (комом)" )
Здравствуйте, kittown, Вы писали:
K>Для нагула идей имеет смысл решить одномерный вариант K>задачи, когда выбирается (непрерывный) подмассив K>одномерного массива с максимальной суммой элементов K>за линейное время (эту задачку можно найти на гугле).
Можно попробовать применить нечто похожее и для матрицы, используя вместо start, end прямоугольник (x1,y1, x2,y2). Ну и вложенный цикл по x,y. Впрочем не уверен в успехе.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, kittown, Вы писали:
K>Hi!
K>Задачку придумал для любителей сочинять алгоритмы. Что-то K>все кому ни дам, никто работоспособного алгоритма не дает K>(т.е. дают быстрые но ошибочные). Не пойму, она K>действительно что ли сложная ?
Нет, и ты не первый ее придумал
K>Исходные данные: матрица NxN, содержит числа. Надо найти K>прямоугольник внутри оной матрицы, сумма числел в котором K>была бы максимальна (размеры прямоугольника неизвестны). K>Параллельные алгоритмы неинтересны, они точно есть на гугле.
K>Очевидно, что решение не может быть быстрее N^2 (по числу K>элементов). Требуется найти алгоритм сложности не K>медленнее N^3 (мой) и узнать, возможны ли более быстрые.
K>Для нагула идей имеет смысл решить одномерный вариант K>задачи, когда выбирается (непрерывный) подмассив K>одномерного массива с максимальной суммой элементов K>за линейное время (эту задачку можно найти на гугле).
K>Mikhail
Самое лобовое решение слудующее:
Одномерный вариант будем использовать в качестве подзадачи.
Затем заполним дополнительный массив
B[i][j] = Сумма элементов i-ой строки исходного массива от 1 до j элемента.
Сложность построения этой матрицы O(n^2).
С помощью нее можно за константное время узнать сумму элементов в i-ой строке в интервале [j,k]
B[i][k]-B[i][j-1] (нулевой столбец заполнен нулями)
Теперь просто переберем все варианты расположения левой и правой границы прямоугольника (O(n^2) вариантов). И для каждого расположения решим линейную задачу с помощью построенной матрицы B. Получим алгоритм со сложностью O(n^3).
kittown wrote: > Hi! > > Задачку придумал для любителей сочинять алгоритмы. Что-то > все кому ни дам, никто работоспособного алгоритма не дает > (т.е. дают быстрые но ошибочные). Не пойму, она > действительно что ли сложная ? > > Исходные данные: матрица NxN, содержит числа. Надо найти > прямоугольник внутри оной матрицы, сумма числел в котором > была бы максимальна (размеры прямоугольника неизвестны). > Параллельные алгоритмы неинтересны, они точно есть на гугле. > > Очевидно, что решение не может быть быстрее N^2 (по числу > элементов). Требуется найти алгоритм сложности не > медленнее N^3 (мой) и узнать, возможны ли более быстрые. > > Для нагула идей имеет смысл решить одномерный вариант > задачи, когда выбирается (непрерывный) подмассив > одномерного массива с максимальной суммой элементов > за линейное время (эту задачку можно найти на гугле).
Недавно эта задача была у друга на программировании на мехмате..
Я ему за небольшое время кинул идею.. Он это написал,
оттестировал, сдал. Задача, как мне кажется, простая.
Про более быстрые алгоритмы не думал, но вряд ли они
есть. Ваш алгоритм — это ведь перебирать пары (left,right)
и искать для каждой из них ответ за O(N)?
_DAle_ wrote: > Здравствуйте, kittown, Вы писали: > > K>Hi! > > K>Задачку придумал для любителей сочинять алгоритмы. Что-то > K>все кому ни дам, никто работоспособного алгоритма не дает > K>(т.е. дают быстрые но ошибочные). Не пойму, она > K>действительно что ли сложная ? > > Нет, и ты не первый ее придумал
_DAle_ wrote: > > K>Hi! > > K>Задачку придумал для любителей сочинять алгоритмы. Что-то > K>все кому ни дам, никто работоспособного алгоритма не дает > K>(т.е. дают быстрые но ошибочные). Не пойму, она > K>действительно что ли сложная ? > > Нет, и ты не первый ее придумал
Я и не говорил что первый. Но гуглом нашел только параллельные
алгоритмы.
> Самое лобовое решение слудующее: > Одномерный вариант будем использовать в качестве подзадачи. > Затем заполним дополнительный массив > B[i][j] = Сумма элементов i-ой строки исходного массива от 1 до j элемента. > > Сложность построения этой матрицы O(n^2). > С помощью нее можно за константное время узнать сумму элементов в i-ой > строке в интервале [j,k] > B[i][k]-B[i][j-1] (нулевой столбец заполнен нулями) > > Теперь просто переберем все варианты расположения левой и правой границы > прямоугольника (O(n^2) вариантов). И для каждого расположения решим > линейную задачу с помощью построенной матрицы B. Получим алгоритм со > сложностью O(n^3).
Да, алгоритм близок, мой только тратит меньше памяти. Без создания
дополнительного массива, с использованием информации предыдущего
шага.
Итого вывод — с местными (не в смысле рсдн) господами задачки
решать неинтересно.
Однако остается вопрос, как проверить наличие или отсутствие
более быстрых алгоритмов, где искать методологию.
Здравствуйте, kittown, Вы писали:
K>Hi!
K>Задачку придумал для любителей сочинять алгоритмы. Что-то K>все кому ни дам, никто работоспособного алгоритма не дает K>(т.е. дают быстрые но ошибочные). Не пойму, она K>действительно что ли сложная ?
K>Исходные данные: матрица NxN, содержит числа. Надо найти K>прямоугольник внутри оной матрицы, сумма числел в котором K>была бы максимальна (размеры прямоугольника неизвестны). K>Параллельные алгоритмы неинтересны, они точно есть на гугле.
K>Очевидно, что решение не может быть быстрее N^2 (по числу K>элементов). Требуется найти алгоритм сложности не K>медленнее N^3 (мой) и узнать, возможны ли более быстрые.
K>Для нагула идей имеет смысл решить одномерный вариант K>задачи, когда выбирается (непрерывный) подмассив K>одномерного массива с максимальной суммой элементов K>за линейное время (эту задачку можно найти на гугле).
)
Перекуём баги на фичи!
