Раздел «Образование».FIVTLecturesTerm4Lecture06:
<< Список лекций ФИВТ, 4-й семестр, 2009 г.

Лекция 6. Эвристические алгоритмы. Задача разбиения прямоугольника на квадраты.

Формулировка задачи разбиения прямоугольника на квадраты. Жадный алгоритм и доказательство его неточности

Дан прямоугольник с целыми сторонами N x M. Необходимо разбить его на минимальное число квадратов. При этом разбиение должно быть таким, чтобы можно было выполнить разрезание прямыми линиями от края до края разрезаемого куска. Данная задача имеет и альтернативную формулировку PROBLEM:099 — найти последовательно-параллельную схему из единичных резисторов, которая дает заданное сопротивление N/M.

Первая идея решения этой задачи - жадность — на каждом шаге отрезаем максимально возможный квадрат (от прямоугольника N x M, N < M, отрезаем квадрат N x N).

Укажите связь этого жадного алгоритма и алгоритма Евклида.

Найдите контрпример — прямоугольник, для которого описанный жадный алгоритм находит неоптимальное решение.

Ответ: 6 x 5.

Как решить данную задачу?

Поиск эвристического алгоритма

За неимением быстрого точного алгоритма, давайте поищем эвристический алгоритм, который будет лучше жадного алгоритма (аля алгоритм Евклида).

У нас на вооружении есть следующие теги-метаметоды:

Как для данной задачи можно было бы использовать scale? Например, так: огрубим отношение M/N до отношение M'/N', где M' < 20, N' < 20. Для маленьких чисел можно найти точное решение методом перебора. Полученное точнее решение для огрубленных N' и M' уточним, чтобы оно стало решением для исходных N и M. С выполненим последнего шага будут проблемы. Ясно, что для данной задачи тег scale не годится, так как решение не обладает свойством "непрерывности" — малое изменение входных данных не соответствует малому изменению оптимального разбиения.

Эвристика reduce + cache + prunning

Зато очевидно, что для данной задачи рабтает тег decompose. Прямоугольник несложно разбить на два прямоугольника и решать для них данную задачу по отдельности. Также из практики написания алгоритмов решения задач методов динамического программирования, мы помним, что тег decompose естественным образом сочетается с тегом cache (собственно, dynamic programming = (decompose||reduce) + cache).

Идея решения: * если сторона N делиться на K, и M достаточно большая, то от края прямоугольника можно отрезать K квадратов, размера N/K и свести задачу к другой — к разбиению прямоугольника (N, M - N/K). Можно ограничится K = 1,2,3 и 4. Тогда на каждом шаге у нас будет ветвление на 4. Перебор естественно реализовать с помощью рекурсии.

decompose.png

Перебор дерева вариантов можно уменьшить, если использовать отсечение и кеширование: * для пар (N, M) , N <= M, будем кешровать найденное лучшее разбиение, если N + M < 5000 (для кэширования ответов на все пары не хватит памяти) * выполняя поиск мы будем, мы будем знать текущее найденное лучшее решение, и если число квадратов уже превысило это оптимальное решение, то нет смысла искать разбиение на квадраты оставшегося кусочка.

Таким образом, эта идея теггируется как recursion + reduce + cache + prunning.