Визуализация проблемы с неисправной шахматной доской

Проблема неисправной шахматной доски, также известная как проблема мозаики, представляет собой интересную проблему. Обычно она решается с помощью подхода «разделяй и властвуй». Алгоритм имеет временную сложность O (n²).

Эта проблема

Для доски n на n, где n имеет форму 2 ^ k, где k ›= 1 (в основном, n является степенью двойки с минимальное значение как 2). На доске отсутствует один квадрат). Заполните доску трионимо. Трионимо - это L-образная плитка, представляющая собой блок 2 × 2, в котором отсутствует одна ячейка размером 1 × 1.

Эффективное решение проблемы не является целью этой статьи. Однако, на мой взгляд, гораздо интереснее визуализировать доску во время работы алгоритма. Давайте сначала обсудим алгоритм.

Алгоритм

Как упоминалось ранее, для решения проблемы используется метод «разделяй и властвуй» (DAC). DAC влечет за собой разделение более крупной проблемы на подзадачи, гарантируя, что каждая подзадача является точной копией более крупной, хотя и меньшей. Вы можете увидеть, к чему мы идем, но давайте сделаем это явно.

Перед написанием алгоритма мы должны задать вопрос: возможно ли это вообще? Ну да. Общее количество квадратов на нашей доске составляет n ² или 4 ^ k. Удалив дефект, мы получим 4 ^ k - 1, что всегда кратно трем. Это довольно легко доказать с помощью математической индукции, поэтому я не буду это обсуждать.

Базовый случай

Каждый рекурсивный алгоритм должен иметь базовый вариант, чтобы гарантировать его завершение. Для нас давайте рассмотрим случай, когда n, 2 ^ k равно 2. Таким образом, у нас есть блок 2 × 2 с одним дефектом. Решить эту проблему несложно: оставшиеся 3 квадрата естественным образом образуют трионимо.

Рекурсивный шаг

Чтобы сделать каждую подзадачу уменьшенной версией нашей исходной проблемы, все, что нам нужно сделать, это добавить наши собственные дефекты, но очень специфическим образом. Если вы присмотритесь поближе, добавление трионимо «дефект» в центре с одним квадратом в каждом из четырех квадрантов нашей доски, за исключением квадрата с нашим исходным дефектом, позволит использовать четыре правильных подзадачи: в то же время гарантируя, что мы сможем решить полную проблему, добавив последний трионимо, чтобы скрыть три добавленных псевдодефектных квадрата.

Когда мы закончим добавление «дефектов», рекурсивное решение каждой из четырех подзадач приведет нас к нашему последнему шагу, который уже обсуждался в предыдущем абзаце.

Шаг комбайна

После решения каждой из четырех подзадач и объединения их в единую доску у нас есть 4 дефекта в нашей доске: исходный будет лежать в одном из квадрантов, а остальные три - те, которые мы намеренно добавили к решению. проблема с использованием DAC. Все, что нам нужно сделать, это добавить последний трионимо, чтобы скрыть эти три «дефекта», и все готово.

Таким образом, рекурсивное уравнение для временной сложности принимает следующий вид:

T(n) = 4T(n/2)+c

4 исходит из того факта, что для решения каждой задачи ввода n мы делим ее на 4 подзадачи с размером ввода n / 2 (половина длины исходного доска). Когда мы закончим решение этих подзадач, все, что осталось сделать, это объединить их: это делается путем добавления последнего трионимо, чтобы скрыть добавленные псевдодефекты. Это, конечно, делается в постоянное время.

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

Основная теорема гласит, что для рекуррентного отношения вида:

T(n) = aT(n/b) + f(n)

сложность зависит от сложности f (n) и n ^ log_b (a) (журнал ведется по основанию b).

Кейсы на изображении ниже говорят нам, какой кейс нам нужно использовать здесь.

Поскольку значение n ^ log (a) base b равно n ², а термин f (n) имеет постоянную сложность, мы используем случай 1, , что в конечном итоге говорит нам, что наш алгоритм имеет порядок n ². Другими словами, временная сложность нашего алгоритма равна O (n ²).

Код

Первоначально каждый квадрат представлен цифрой 0. «-1» представляет собой дефектный квадрат и на графиках будет отображаться черным цветом. Каждый трионимо будет отображаться с уникальным номером, который будет увеличиваться по мере добавления новых трионимо.

Опять же, цель кода не в оптимизации, а в том, чтобы сделать как можно больше с нуля (на простом Python).

Я прокомментировал код ниже, так что он должен быть довольно простым.

Импорт необходимых библиотек

Библиотека random используется для случайного выбора квадрата, который считается дефектным, просто для запуска проблемы, а seaborn, конечно же, для визуализации.

Создание доски

Ничего особенного: просто создание двухмерного списка Python. Алгоритм можно оптимизировать, используя такие структуры, как массивы numpy вместо обычных списков Python. Список инициализируется нулями.

Случайное добавление дефекта

Здесь мы случайным образом выбираем элемент с помощью randint () и делаем его дефектным тайлом. Мы будем обозначать дефекты знаком -1.

Обнаружение дефекта при решении каждой подзадачи

Здесь мы делаем две вещи:

поиск строки и столбца дефекта
определение того, в каком квадранте платы лежит дефект

Первый шаг можно оптимизировать, используя функции numpy вместо подхода «с нуля», описанного ниже.

Добавление трионима

Эта функция добавляет трионимо к разделу доски 2 x 2. Здесь нам пригодится квадрант дефекта, поскольку мы можем просто определить словарь, чтобы решить, как добавить наш трионимо.

Рекурсивная функция мозаики

Это реализация нашего алгоритма мозаики по принципу «разделяй и властвуй». Функция выполняет следующее:

определение местоположения дефекта в данном разделе платы (строки r1 и r2 и столбцы c1 и c2 позволяют функции сосредоточиться на конкретном участке платы).
добавление трионимо, если мы имеем дело с разделом доски 2 x 2
в противном случае добавление трех дефектов к центру
рекурсивное решение каждого квадранта доски
добавление последнего трионимо, чтобы скрыть три дефекта, которые мы добавили в центре.

Функция родительских листов

Это просто делает интерфейс чище, поскольку технически у нас есть только два независимых аргумента: плата и параметр k (ну, k можно вычислить или использовать как глобальную переменную, но это зависит от программиста).