Пятнашки глазами алгоритмиста. Часть 2: думаем и улучшаем оценки!

Необходимая теория:
Инвариантом называется свойство объекта, которое не меняется при выполнении определённых преобразований. Если найден инвариант, значения которого для двух объектов не совпадают, то превратить один объект в другой рассматриваемыми преобразованиями не удастся. Иными словами, нахождение инварианта, «различающего» два данных объекта, доказывает неразрешимость задачи превращения одного объекта в другой.
В случае игры в «15» таким инвариантом оказывается чётность суммы двух следующих чисел, A и B. Число A — это число пар плиток, в которых плитка с большим номером идёт перед плиткой с меньшим номером (количество инверсий перестановок). Число B — это номер строки, в которой находится пустое поле.
Например, в позиции на рисунке пять «неправильных» пар — (4,2), (4,3), (4,1), (2,1), (3,1) — поэтому A = 5. Число B в этом примере равно 2.
Джонсон (Johnson) в 1879 г. доказал, что если A + B нечётно, то решения не существует, а Стори (Story) в том же году доказал, что все позиции, для которых A + B чётно, имеют решение.
Для обобщённых пятнашек NxN критерий разрешимости можно определить как чётность суммы A + B + N.
(Можно самостоятельно проверить, что любой обмен двух костяшек меняет чётность, а любой ход, т. е. обмен местами костяшки и пустого поля, — не меняет).

Смотрим на формулу и начинаем рассуждать.
Для того, чтобы посчитать количество инверсий, нам необходим вложенный цикл: проходим по массиву, для каждого непустого элемента подсчитывая количество элементов с меньшим номером путём прохода по оставшейся части массива.
Это типичный шаблон, используемый во многих алгоритмах обработки данных (например, в сортировках), и любой программист должен, не задумываясь, отвечать, что трудоёмкость его квадратична относительно размера массива.
У нас N^2 элементов (считая и “дырку”), таким образом, сложность составит O((N^2)^2) = O(N^4).
Вот, например, типичный пример кода решения “в лоб” из онлайн-сборника алгоритмов:


Вот ещё симпатичный компактный вариант на Питоне:
from itertools import chain
from operator import gt
def is_valid(field):
permutation = chain(*field)
return len(filter(None, [gt(permutation[i], a) for i in xrange(len(permutation)) for a in permutation[i+1:]])) % 2 == 0

А теперь вспомним ответ к прошлой задачке, и у нас должен возникнуть естественный вопрос: как получилось, что простая проверка на разрешимость сложнее самого решения?

Парадокс?!

Правильное решение:
Для начала проведём оценку нижней границы. Простейший метод её получения основан на подсчёте количества элементов, которые надо обработать. Поскольку любой алгоритм должен как минимум “прочесть” все данные, с которыми он будет работать, и записать все “выходные” данные, такой подсчёт приводит к тривиальной нижней границе. [хорошо о вычислении нижних границ в “Алгоритмы: введение в разработку и анализ” Левитина]
Элементов у нас N^2, и очевидно, что чётность позиции существенно зависит от значения каждого из них. То есть имеем Ω(N^2). А достижима ли она? Можно ли как-то понизить класс сложности алгоритма с квадратичного до линейного относительно количества костяшек?

Во-первых, надо понять, что нас интересует именно чётность, а не точное количество инверсий текущей позиции само по себе (это количество имеет квадратичный порядок). Формула (A + B + N) % 2 лишь удобный способ выражения, но не обязательно руководство к действию!
Во-вторых, вспомнить, что любой обмен двух костяшек меняет чётность (подсказка уже была дана выше!).
В-третьих, сообразить, что, имея возможность поменять две любых костяшки, мы очень быстро (за один проход) можем восстановить правильный порядок (с расположением цифр костяшек по возрастанию)!

Если у нас есть под рукой таблица прямого доступа, то тривиально расставляем костяшки по порядку начиная с 1й цифры, обменивая костяшку местами с тем, что находится на её законном месте. (Если костяшка уже на своём месте, соответственно, ничего не меняем и счётчик обменов не увеличиваем).
Можно обойтись и без таблицы, не используя дополнительной памяти. Делаем почти то же самое. Проходим по массиву, начиная с 1й ячейки, меняя местами очередную костяшку с тем, что находится по адресу, равному её цифре.
Ну а теперь, зная, что чётность позиции с правильным порядком равна 0, просто смотрим на чётность количества совершённых обменов!
Имеем O(N^2), а с учётом нижней границы Θ(N^2).

Может быть, задачка кажется и несложной, но я, погуглив, сходу не нашёл упоминания оптимального способа вычисления.
…Вспоминается: в своё время основным результатом моей дипломной стало построение полиномиального алгоритма вычисления вектора Шепли для теоретико-игровой постановки конкретной прикладной задачи. Формула вектора Шепли сама по себе задаёт экспоненциальное количество вычислений, а ключевая идея, как и здесь, заключалась в непосредственной комбинаторной работе со входными данными…

Ну и, в заключение, бонус (немного истории):


“Старые обитатели страны головоломок, наверное, помнят, как в начале семидесятых годов *[XIX века] я свел с ума весь мир маленькой коробочкой, заполненной небольшими кубиками, которая называлась игрой в 14–15. Пятнадцать перенумерованных кубиков лежали в квадратной коробке в правильном порядке, за исключением кубиков с номерами 14 и 15, которые поменялись местами, как показано на рисунке. Головоломка состоит в том, чтобы, передвигая по очереди по одному кубику, добиться того, чтобы номера 14 и 15 поменялись местами и чтобы все кубики лежали по порядку, причем после всех перестановок правый нижний угол должен остаться свободным, как в начале игры.
Приз в 1000 долларов, предлагавшийся за первое правильное решение, никогда никому не был присужден, хотя тысячи людей утверждали, будто они решили задачу.
Люди буквально помешались на этой головоломке. Из уст в уста передавались удивительные рассказы о лавочнике, забывшем открыть свой магазинчик, об одном почтенном священнике, простоявшем под уличным фонарем долгую зимнюю ночь в надежде вспомнить, как ему удалось решить задачу. Таинственная особенность данной головоломки состоит в том, что, видимо, никто не в состоянии вспомнить последовательность ходов, тогда как многие совершенно уверены, что они добились успеха. Говорят, лоцманы сажали свои корабли на рифы, а паровозные машинисты проносились мимо станций… фермеры забывали о своем плуге!” (с) Сэм Лойд “Энциклопедия головоломок”


Сэмюэль (Сэм) Лойд, знаменитый автор головоломок, приписывал создание игры себе.

Настоящий изобретатель – почтмейстер Ной (Нойес) Чепмэн (США, 1870-е гг.).

Начало 1880 года – некий дантист Чарльз Певи привлёк внимание общественности, предложив $1000 за решение.

1879-1880 гг. – пик популярности головоломки в США и Европе.


Политическая карикатура о поиске кандидата в президенты США от республиканской партии в 1880 году

"…За последние несколько недель вошла в моду новая игрушка-головоломка... и что от Атлантического океана до Тихого все население Соединенных Штатов прекратило работу и занимается только этой игрушкой; что в связи с этим вся деловая жизнь в стране замерла, ибо судьи, адвокаты, взломщики, священники, воры, торговцы, рабочие, убийцы, женщины, дети, грудные младенцы, — словом, все с утра до ночи заняты одним-единственным высокоинтеллектуальным и сложным делом... что веселье и радость покинули народ — на смену им пришли озабоченность, задумчивость, тревога, лица у всех вытянулись, на них появились отчаяние и морщины — следы прожитых лет и пережитых трудностей, а вместе с ними и более печальные признаки, указывающие на умственную неполноценность и начинающееся помешательство; что в восьми городах день и ночь работают фабрики, и все же до сих пор не удалось удовлетворить спрос на головоломку…" (с) Марк Твен «Американский претендент»
Продолжение