Пятнашки глазами алгоритмиста. Часть 4 с половиной: демоны и декомпозиция
Часть 1: асимптотическая оценка сложности
Часть 2: думаем и улучшаем оценки!
Часть 3: константная оценка точности
Часть 4: ПОЧТИ лирическое отступление
son_0f_morning задавал логичный вопрос – останется ли верной полученная в части 1 оценка, если разрешены сдвиги целых рядов (действительно, такой вариант игровой постановки задачи известен). Я сначала предположил, что да, но, подумав, нашёл асимптотически лучшее решение.
"Игра в пятняшки" с мультисдвигами на доске размера NxN.
Помимо обычных ходов, разрешены мультисдвиги (одновременное перемещение нескольких плиток, образующих сплошной вертикальный или горизонтальный ряд).
Какова вычислительная сложность оптимального алгоритма, генерирующего для любой допустимой (решаемой) начальной позиции последовательность движений (не обязательно кратчайшую), приводящую к правильному порядку?
//Будет ли она по-прежнему оставаться равной Θ (N^3)?
Вспомним известный в термодинамике мысленный эксперимент – демон Максвелла, который позволяет пролетать быстрым (горячим) молекулам газа только из правой части сосуда в левую, а медленным (холодным) молекулам — только из левой части сосуда в правую. Тогда через большой промежуток времени «горячие» (быстрые) молекулы окажутся в левом сосуде, а «холодные» останутся в правом.
А давайте попробуем скосплеить его для пятнашек!
Как и прежде, для простоты предположим, что N кратно двум. Назовём “горячими” те костяшки, законное место которых находится в левой половине поля, и “холодными” – в правой. Разработаем алгоритм подпрограммы – “демона Максвелла”, которая последовательно перемещает костяшки в соответствующие половины.
И для этого опять воспользуемся методом уменьшения размера задачи (стараемся придумать алгоритм, не обязательно лучший, но максимально простой в описании).
Сначала проделаем требуемое для первой строки, после чего её уже не трогаем, потом – для следующей и т.д.
1. В цикле выполняем следующее: если горячие и холодные костяшки строки стоят вперемешку, то сдвигаем вниз первую встреченную “холодную” костяшку, а на её место двигаем влево весь ряд вплоть до последней встреченной “горячей” (вторая строчка используется в качестве “буфера”).
Цикл будет состоять не более чем из O(N) сдвигов и мультисдвигов.
2. Теперь у нас есть k последовательно стоящих “горячих” и N-k ”холодных”. Предположим, что k < N-k. Выбираем строчку ниже с максимальным количеством “горячих” костяшек. Легко показать, что в ней будет содержаться не менее N/2 – k “горячих”.
// Заметим, что нахождение количеств костяшек каждого типа в каждой строке строках требует O(N^2), поэтому можно один раз вычислить в начале работы “демона”, а затем лишь обновлять при ходах.
3. Упорядочиваем костяшки в этой строке, точно так же, как и в верхней, используя буфером одну из соседних строк – O(N) действий.
4. Двигаем “паровозиком” полученный внизу ряд “горячих костяшек” вверх по первому столбцу – O(N) действий (сдвигов и мультисдвигов).
5. Двигаем общий паровозик из “горячих” костяшек первой строки и первого столбца вправо, до тех пор, пока не получим искомое разделение пополам – O(N) действий.
// Если в п.2 получили k > N-k, то проделываем аналогичные операции с “холодными” костяшками, используя последний столбец
Все вышеперечисленные действия в цикле повторяем для каждой строки сверху вниз. Имеем в результате N*O(N) = O(N^2) операций.
// Для порядка надо бы доказать, что для двух последних строчек (где возникают трудности с наличием буфера) тоже можно обойтись O(N) действиями. Но нам это не важно, так как знаем, что даже обычный метод уменьшения размера задачи, описанный ранее, справится тут за O(N^2), что на общую оценку не повлияет: O(N^2) + O(N^2) = O(N^2).
Нашего демона нетрудно приспособить работать с любым прямоугольником, в том числе и сдвигать не вправо-влево, а вверх-вниз. Рекурсивно вызываем его для каждой половины, и так до тех пор, пока не будем иметь дело с маленькими квадратиками или прямоугольничками, в которых костяшки будет уже нетрудно расставить по местам.
// Строго говоря, нужно ещё перебрасывать “дырку” от одного прямоугольничка к другому, но это не учитываем, так как потребует лишь линейное количество действий, что не влияет на общую оценку.
Таким образом, мы воспользовались (помимо метода уменьшения размера задачи) ещё и другим классическим методом разработки алгоритмом – декомпозицией (https://ru.wikipedia.org/wiki/Разделяй_и_властвуй_(информатика)).
Оценку трудоёмкости алгоритма можно произвести при помощи Oсновной теоремы о рекуррентном соотношении.
В общем случае задача размера n делится на экземпляры задачи размера n/b, из которых a требуется решить (b > 1, a ≥ 0).
Время T(n) работы алгоритмы, основанного на методе декомпозиции, равно
T(n) = aT(n/ b) + f(n), (*)
где f(n) – функция, учитывающая затраты времени на разделение задачи на экземпляры и комбинирование их решений.
Рекуррентное соотношение (*) – это обобщённое рекуррентное уравнение декомпозиции.
Теорема. Если в обобщённом рекуррентном уравнении декомпозиции функция f(n) = Θ(n^d), где d ≥ 0, то вычислительная сложность алгоритма равна
В нашем случае имеем: T(N) = 2T(N/2) + O(N^2), видим, что это первый случай. Разделение задачи на экземпляры занимает бОльшую часть времени, и оно же определяет порядок сложности. Таким образом, T(N) = O(N^2). Учитывая тривиальную нижнюю границу, Θ(N^2).
На самом деле, общая идея “растаскивания” объектов по разные стороны “медианы” при декомпозиции напоминает хорошо известный алгоритм быстрой сортировки Хоара (https://ru.wikipedia.org/wiki/Быстрая_сортировка). Правда, у “демона” уходит больше времени на переброску (так как работаем с двумерным массивом, а не с одномерным), зато легко определяем “перегородку”, делящую множество элементов на две части равной мощности, в то время как опорный элемент сортировки может быть выбран неудачно. В результате чего в худшем (но не в среднем!) случае сортировка также имеет оценку O(N^2).
К сожалению, встречаются ошибочные представления о анализе сложности. Вот как раз сегодня на Хабре вижу переводную статью со следующими утверждениями:
Разделяй и властвуй (Divide and Conquer) всегда O(log n)
Итерации которые использую Divide and Conquer это O(n log n)
которые, разумеется, неверны, как мы уже убедились на примере. Логарифм при использовании декомпозиции действительно появляется часто, но отнюдь не всегда, вообще говоря, вычислительная сложность может быть любой, от O(logN) и выше.
З.Ы. В честь прошедшего недавно Рождества, посвящаю сей алгоритм Светлой Богине! ^_^
З.З.Ы. Общая просьба. Буду благодарен за уточняющие вопросы и замечания по изложению текстов, а также за подкидывание интересных малоизвестных задачек на разработку алгоритмов и анализ сложности.
Продолжение следует
Часть 2: думаем и улучшаем оценки!
Часть 3: константная оценка точности
Часть 4: ПОЧТИ лирическое отступление
son_0f_morning задавал логичный вопрос – останется ли верной полученная в части 1 оценка, если разрешены сдвиги целых рядов (действительно, такой вариант игровой постановки задачи известен). Я сначала предположил, что да, но, подумав, нашёл асимптотически лучшее решение."Игра в пятняшки" с мультисдвигами на доске размера NxN.
Помимо обычных ходов, разрешены мультисдвиги (одновременное перемещение нескольких плиток, образующих сплошной вертикальный или горизонтальный ряд).
Какова вычислительная сложность оптимального алгоритма, генерирующего для любой допустимой (решаемой) начальной позиции последовательность движений (не обязательно кратчайшую), приводящую к правильному порядку?
//Будет ли она по-прежнему оставаться равной Θ (N^3)?
Вспомним известный в термодинамике мысленный эксперимент – демон Максвелла, который позволяет пролетать быстрым (горячим) молекулам газа только из правой части сосуда в левую, а медленным (холодным) молекулам — только из левой части сосуда в правую. Тогда через большой промежуток времени «горячие» (быстрые) молекулы окажутся в левом сосуде, а «холодные» останутся в правом.
А давайте попробуем скосплеить его для пятнашек!
Как и прежде, для простоты предположим, что N кратно двум. Назовём “горячими” те костяшки, законное место которых находится в левой половине поля, и “холодными” – в правой. Разработаем алгоритм подпрограммы – “демона Максвелла”, которая последовательно перемещает костяшки в соответствующие половины.
И для этого опять воспользуемся методом уменьшения размера задачи (стараемся придумать алгоритм, не обязательно лучший, но максимально простой в описании).
Сначала проделаем требуемое для первой строки, после чего её уже не трогаем, потом – для следующей и т.д.
1. В цикле выполняем следующее: если горячие и холодные костяшки строки стоят вперемешку, то сдвигаем вниз первую встреченную “холодную” костяшку, а на её место двигаем влево весь ряд вплоть до последней встреченной “горячей” (вторая строчка используется в качестве “буфера”).
Цикл будет состоять не более чем из O(N) сдвигов и мультисдвигов.
2. Теперь у нас есть k последовательно стоящих “горячих” и N-k ”холодных”. Предположим, что k < N-k. Выбираем строчку ниже с максимальным количеством “горячих” костяшек. Легко показать, что в ней будет содержаться не менее N/2 – k “горячих”.
// Заметим, что нахождение количеств костяшек каждого типа в каждой строке строках требует O(N^2), поэтому можно один раз вычислить в начале работы “демона”, а затем лишь обновлять при ходах.
3. Упорядочиваем костяшки в этой строке, точно так же, как и в верхней, используя буфером одну из соседних строк – O(N) действий.
4. Двигаем “паровозиком” полученный внизу ряд “горячих костяшек” вверх по первому столбцу – O(N) действий (сдвигов и мультисдвигов).
5. Двигаем общий паровозик из “горячих” костяшек первой строки и первого столбца вправо, до тех пор, пока не получим искомое разделение пополам – O(N) действий.
// Если в п.2 получили k > N-k, то проделываем аналогичные операции с “холодными” костяшками, используя последний столбец
Все вышеперечисленные действия в цикле повторяем для каждой строки сверху вниз. Имеем в результате N*O(N) = O(N^2) операций.
// Для порядка надо бы доказать, что для двух последних строчек (где возникают трудности с наличием буфера) тоже можно обойтись O(N) действиями. Но нам это не важно, так как знаем, что даже обычный метод уменьшения размера задачи, описанный ранее, справится тут за O(N^2), что на общую оценку не повлияет: O(N^2) + O(N^2) = O(N^2).
Нашего демона нетрудно приспособить работать с любым прямоугольником, в том числе и сдвигать не вправо-влево, а вверх-вниз. Рекурсивно вызываем его для каждой половины, и так до тех пор, пока не будем иметь дело с маленькими квадратиками или прямоугольничками, в которых костяшки будет уже нетрудно расставить по местам.
// Строго говоря, нужно ещё перебрасывать “дырку” от одного прямоугольничка к другому, но это не учитываем, так как потребует лишь линейное количество действий, что не влияет на общую оценку.
Таким образом, мы воспользовались (помимо метода уменьшения размера задачи) ещё и другим классическим методом разработки алгоритмом – декомпозицией (https://ru.wikipedia.org/wiki/Разделяй_и_властвуй_(информатика)).
Оценку трудоёмкости алгоритма можно произвести при помощи Oсновной теоремы о рекуррентном соотношении.
В общем случае задача размера n делится на экземпляры задачи размера n/b, из которых a требуется решить (b > 1, a ≥ 0).
Время T(n) работы алгоритмы, основанного на методе декомпозиции, равно
T(n) = aT(n/ b) + f(n), (*)
где f(n) – функция, учитывающая затраты времени на разделение задачи на экземпляры и комбинирование их решений.
Рекуррентное соотношение (*) – это обобщённое рекуррентное уравнение декомпозиции.
Теорема. Если в обобщённом рекуррентном уравнении декомпозиции функция f(n) = Θ(n^d), где d ≥ 0, то вычислительная сложность алгоритма равна
В нашем случае имеем: T(N) = 2T(N/2) + O(N^2), видим, что это первый случай. Разделение задачи на экземпляры занимает бОльшую часть времени, и оно же определяет порядок сложности. Таким образом, T(N) = O(N^2). Учитывая тривиальную нижнюю границу, Θ(N^2).
На самом деле, общая идея “растаскивания” объектов по разные стороны “медианы” при декомпозиции напоминает хорошо известный алгоритм быстрой сортировки Хоара (https://ru.wikipedia.org/wiki/Быстрая_сортировка). Правда, у “демона” уходит больше времени на переброску (так как работаем с двумерным массивом, а не с одномерным), зато легко определяем “перегородку”, делящую множество элементов на две части равной мощности, в то время как опорный элемент сортировки может быть выбран неудачно. В результате чего в худшем (но не в среднем!) случае сортировка также имеет оценку O(N^2).
К сожалению, встречаются ошибочные представления о анализе сложности. Вот как раз сегодня на Хабре вижу переводную статью со следующими утверждениями:
Разделяй и властвуй (Divide and Conquer) всегда O(log n)
Итерации которые использую Divide and Conquer это O(n log n)
которые, разумеется, неверны, как мы уже убедились на примере. Логарифм при использовании декомпозиции действительно появляется часто, но отнюдь не всегда, вообще говоря, вычислительная сложность может быть любой, от O(logN) и выше.
З.Ы. В честь прошедшего недавно Рождества, посвящаю сей алгоритм Светлой Богине! ^_^
З.З.Ы. Общая просьба. Буду благодарен за уточняющие вопросы и замечания по изложению текстов, а также за подкидывание интересных малоизвестных задачек на разработку алгоритмов и анализ сложности.
Продолжение следует