Пятнашки глазами алгоритмиста. Часть 1: асимптотическая оценка сложности

Ещё задачка на анализ сложности. // Навеяно постом avva



Ответ: Θ(N^3).

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

Длина пути, который надо пройти отдельной костяшке, ограничена 2*N (максимум - из угла в противоположный угол).
Находим костяшку с нужным номером, сдвигаем к ней "дырку" (тоже не более 2*N, т. е. O(N) движений), а потом начинаем перемещать саму костяшку, передвигая каждый раз окрестность так, чтобы "дырка" оказывалась впереди, - не более 6 движений, т. е. O(1).
Итого O(N)+O(N)*O(1) = O(N). Всего N^2-1 костяшек, следовательно, общая длина последовательности движений O(N)*O(N^2) = O(N^3).

Сложность самого алгоритма, очевидно, определяется количеством движений.
Действительно, определить координаты очередного движения несложно, мы всегда можем сделать это за константу.
Единственный нюанс: поиск очередной костяшки для перемещения на правильное место при очередной итерации.
Последовательный поиск в массиве по номеру занял бы O(N^2), поэтому предварительно можно завести дополнительный массив (таблицу прямого доступа), где по индексу хранятся текущие координаты костяшки с соответствующим номером.
Заполнение таблицы потребует одного прохода по нашему основному массиву размера N^2, что не скажется на общей трудоёмкости: O(N^2)+O(N^3) = O(N^3).
Поиск в таблице прямого доступа всегда занимает O(1).
Правда, придётся при каждом движении менять соответствующую координату и в таблице, но это, опять же, домножение на константу, не влияющее на асимптотику алгоритма.

Теперь осталось показать, что наша оценка достижима, а именно, общее количество движений можно оценить в худшем случае как Ω(N^3).
Для этого достаточно привести пример, в котором каждая из O(N^2) костяшек должна пройти путь длиной не менее O(N), чтобы встать на своё место.
"Отрежем" нижнюю половину доски и переместим её вверх (для простоты будем считать, что N чётно)
9 10 11 12
13 14 15
1 2 3 4
5 6 7 8
Теперь для каждой костяшки расстояние до исходного места равно N/2, т. е. O(N). (Если получилась недопустимая позиция, то дополнительно поменяем местами в любой строчке какие-нибудь две соседние костяшки, оценку это не уменьшит.)

Так как верхняя и нижняя оценка совпадают, итоговая точная оценка вычислительной сложности Θ(N^3).

Необходимая теория: https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое#Другие_подобные_обозначения

З.Ы. Кстати, код для решения пятнашек должен хорошо писаться на Прологе (для малых N).

Любопытные факты: любую из 10 461 394 944 000 разрешимых конфигураций «классической» головоломки 4 × 4 можно перевести в начальную не более чем за 80 ходов. Уже для варианта 5 x 5 (с 7,7556·10^24 разрешимыми конфигурациями) точное число ходов (так называемое "Число Бога") неизвестно! наилучшие нижняя и верхняя оценки на 2011 год составляли 152 и 208.

З.З.Ы. Про пятнашки и мировое господство:
“…Сварог открыл коробочку и сказал:
– Вот это – головоломка. Как по-вашему, что с ней нужно делать?
Дворянин был ронерцем и потому раздумывал не более минуты:
– Тринадцать… Пятнадцать… Ага, вот так… – он довольно ловко стал двигать квадратики грязноватым пальцем. – Нужно их передвинуть так, чтобы цифры стояли по порядку, верно? Не вынимая?
– Совершенно верно, – сказал Сварог. – Вы сейчас отвезете мешки в лавки, где торгуют головоломками. По мешку в лавку.
– Ваша милость, лучше бы сначала выправить патент, это ж приличные деньги…
– Это долго?
– За полчаса можно справиться.
– Валяйте, – сказал Сварог. – Можете взять патент на свое имя, мне безразлично. И меня не интересуют вырученные от продажи деньги.
– Благодарю, ваша милость! Прикажете бежать?
– Стоп, – сказал Сварог. – Теперь начинается самое главное. – Он выстроил квадратики по порядку, от первого до пятнадцатого, потом поменял местами «15» и «14». – Насколько я знаю, решение задач на премию у вас обставляют так, что сжульничать невозможно? Стряпчий, свидетели…
– Верно, ваша милость.
– Найдите такого стряпчего. Пусть оформит все, как надлежит, – ну, вам лучше знать… И объявите: тот, кто вернет квадратики в прежнее положение – из этого, именно из этого! – получит тысячу ауреев золотом. Все поняли? Выполняйте.
Дворянин махнул лакеям, они взвалили брякающие содержимым мешки на плечи, и вся компания скрылась. Сварог самодовольно улыбнулся, гордый собой.
Память у него была необычайно цепкая, и в ней, словно в рыбацкой сети с мелкими ячейками, застревало превеликое множество самых разных сведений, случайно прочитанных или услышанных…
Когда в семидесятых годах девятнадцатого века в США придумали эту игрушку, моментально проникшую в Европу, разразилось форменное национальное бедствие. Играли все – в городах и деревнях, на заседаниях германского рейхстага и в лондонском Сити. Хозяева контор и магазинов специальным приказом запрещали клеркам и продавцам брать в руки «пятнашку» в рабочее время. Когда за решение одной из позиций была назначена большая премия, торговцы забывали открывать магазины, крестьяне – кормить скотину и пахать, машинисты – останавливать поезда на станциях. Люди ночами простаивали под уличными фонарями, двигая квадратики.
А та позиция, та задача, между прочим, оказалась неразрешимой. Но математики доказали это гораздо позже, и чума под названием «пятнадцать» свирепствовала еще долго. В Равене, никаких сомнений, горячка вспыхнет еще более азартная…” (c) Бушков “Летающие острова”


Продолжение
.