| Главная | Эксперименты | Утилиты | Компоненты | Что почитать | Контакты |
| |||||||||||||||||||||||||||||||||
|
Подсчитать количество различных замкнутых путей, проходящих через каждую клетку квадратной решетки nxn по крайней мере один раз так, что любые границы между соседними квадратами не пересекаются более одного раза и путь не содержит самопересечений.
|
|
Задача может решаться и для прямоугольных сеток nxk. Возможны также два варианта подсчета количества путей: пути, получаемые отражениями и/или вращением могут считаться различными (not reduced for symmetry) или не считаться таковыми (reduced for symmetry).
Полученные значения для первого варианта (пути, получаемые поворотом/вращением считаются различными) приведены по ссылке слева. Для расчета использовано динамическое программирование по профилю[2].
Задача значительно усложняется, если пути, получаемые отражениями/вращениями считать одинаковыми. Для подсчета количества уникальных путей использована следующая схема:
- Квадратная сетка разбивается на четыре части. Для одной из них (например, можно взять левый верхний угол) считается количество путей, симметричных относительно диагонали и количество путей, несимметричных относительно диагонали. Для подсчета использовано динамическое программирование по профилю. Алгоритм практически не отличается от подсчета общего количества путей для всей сетки. В результате мы получаем список групп путей, для каждой из которых известно количество, окончания снизу и справа и признак симметричности относительно диагонали. Список таких групп для сетки 6x6 приведен слева.
- Для полученного списка групп можно проверить все возможные соединения частей, которые дают корректный путь. Алгоритм проверки корректности соединения достаточно простой. Представьте, что все соединения частей - это отверстия и мы продеваем иголку с ниткой через эти отверстия. Когда иголка попадет в уже занятое отверстие, путь замыкается. Если при этом не осталось свободных отверстий, значит путь корректно замкнут и четыре части описывают некоторое множество полных путей.
- Для каждого замыкания четырех частей мы знаем достаточно признаков, чтобы посчитать количество уникальных путей, которые получаются из такого замыкания.
Такая схема позволила рассчитать количество уникальных путей для четных n до 10 включительно. Полученные значения приведены в таблице слева.
|