Задача замощения

Основная идея алгоритма

Алгоритм пытается последовательно поместить полимино одно за другим в таблицу. Если на каком-то этапе поставить полиомино не удаётся, возвращаемся на предыдущий этап и пытаемся там поставить полиомино в другое положение, затем опять идём дальше (или возвращаемся ещё на один этап назад) и т.д.

Особенности и алгоритм программы

Программа достаточно оптимальна по памяти и используемым ресурсам. В качестве основной структуры данных для манипуляций c объектами используются NumPy массивы (тип элементов int64). Полиомино кодируются матрицами. За начало координат берётся левый верхний угол прямоугольника, ось ординат направлена вниз. Затем к матрицам применяются преобразования сдвига и поворота.

Для подбора замощения применяются генераторы, это также сильно экономит память, позволяет не использовать рекурсию (что может переполнить стек вызовов) и позволяет не запоминать специально состояния, а также уже рассмотренные комбинации.

Таким образом, по памяти оценка будет порядка (сумма размерностей всех полиомино + сумма размерностей L-полиомино + размерность таблицы*(количество полиомино и L-полиомино))*8 байт. То есть O(n), где n - количество всех полиомино и L-полиомино при константной таблице.

По сложности алгоритм в худшем случае будет пропорционален (4М_1М_2)^(H_1+H_2). Таким образом, в общем случае будет экспоненциальная сложность. На сколько я понял из описаний в интернете, данная проблема в общем случае является NP сложной [1], так что такая оценка вполне ожидаема.

Из вариантов решения можно также предложить генетические алогоритмы, например, с использованием модулей pyeasyga или DEAP [2, 4].

Системные требования

Программа запускалась в среде

• Ubuntu 20.10 (Linux 5.8.0-50-generic x86_64 GNU/Linux)
• Python 3.8.6
• numpy 1.20.2

а также в Docker-контейнере c

• Linux Alpine 3.12
• Python 3.9.4
• numpy 1.20.2.

Запуск программы

Вариант 1. Запуск из виртуального окружения

1. Устанавливаем виртуальное окружение

virtualenv env

2. Активируем окружение

. ./env/bin/activate

3. Устанавливаем модули Python

pip install -r requirements.txt

4. В файле example1.py параметры считываются из файла parameters.txt. В соответствии с заданием параметры следующие:

• первая строка — тапл-пара с размером прямоугольника
• вторая строка - H_1 - количество полиомино
• на следующих строках указывается сначала мощность полиомино-множества, порожденного соответствующим прямоугольником-полоимино как опорным, затем тапл-пара — размер порождающего полиомино.
• затем аналогично для L-полиомино.

5. В файле example2.py совокупность полиомино определяется непосрественно в коде (с немного другими данными).

6. Запуск

python example1.py
python example2.py

Вариант 2. Запуск из Docker контейнера

1. Создаём Docker образ

docker build -t poliominos .

2. Запускаем контейнер

docker run --rm poliominos

Вариант 3. Запуск с Docker Hub

docker run --rm vol1ura/poliominos

Ссылки

1. Голомб С.В. Полимино \Пер. с англ. В. Фирсова — Москва: Мир, 1975 - с.207.
2. https://pyeasyga.readthedocs.io/
3. https://habr.com/ru/post/498308/
4. https://deap.readthedocs.io/en/master/examples/
5. https://habr.com/ru/post/501008/
6. https://habr.com/ru/post/408299/
7. https://www-cs-faculty.stanford.edu/~knuth/programs.html
8. https://www.ugatu.su/media/uploads/MainSite/Science/dissovet/03/2014/ChirikovHY/autoref.pdf