Меандры на сетке

Задача подсчета количества гамильнтоновых циклов специального вида:

Подсчитать количество различных замкнутых путей, проходящих через каждую клетку квадратной решетки nxn по крайней мере один раз так, что любые границы между соседними квадратами не пересекаются более одного раза и путь не содержит самопересечений.

from OEIS[1]: The sequence counts the distinct closed paths that visit every cell of an n-by-n square lattice at least once, that never cross any edge between adjacent squares more than once, and that do not self-intersect.

Пример такого пути (путь и его кодирование взяты из описания задачи в OEIS):

-2+3-2+3-2+3|+2+4-3+2-3+1|-2-3-2+3-2-3|+2+3+2+4-4+3|-2-3-2+4-3+1|+2-1-3+2-1-3

Задача может решаться и для прямоугольных сеток nxk. Возможны также два варианта подсчета количества путей: пути, получаемые отражениями и/или вращением могут считаться различными (not reduced for symmetry) или не считаться таковыми (reduced for symmetry).

Полученные значения для первого варианта (пути, получаемые поворотом/вращением считаются различными) приведены по ссылке слева. Для расчета использовано динамическое программирование по профилю[2].

Задача значительно усложняется, если пути, получаемые отражениями/вращениями считать одинаковыми. Для подсчета количества уникальных путей использована следующая схема:

  • Квадратная сетка разбивается на четыре части. Для одной из них (например, можно взять левый верхний угол) считается количество путей, симметричных относительно диагонали и количество путей, несимметричных относительно диагонали. Для подсчета использовано динамическое программирование по профилю. Алгоритм практически не отличается от подсчета общего количества путей для всей сетки. В результате мы получаем список групп путей, для каждой из которых известно количество, окончания снизу и справа и признак симметричности относительно диагонали. Список таких групп для сетки 6x6 приведен слева.
  • Для полученного списка групп можно проверить все возможные соединения частей, которые дают корректный путь. Алгоритм проверки корректности соединения достаточно простой. Представьте, что все соединения частей - это отверстия и мы продеваем иголку с ниткой через эти отверстия. Когда иголка попадет в уже занятое отверстие, путь замыкается. Если при этом не осталось свободных отверстий, значит путь корректно замкнут и четыре части описывают некоторое множество полных путей.
  • Для каждого замыкания четырех частей мы знаем достаточно признаков, чтобы посчитать количество уникальных путей, которые получаются из такого замыкания.

Такая схема позволила рассчитать количество уникальных путей для четных n до 10 включительно. Полученные значения приведены в таблице слева.

18 декабря 2011
27 мая 2012

Comments
24.06.2017 08:28 Deweystype
 If you have a desire to learn how to earn from $ 500 per day and work only for yourself, t
 hen write to us at email: admin@makemoneyonline.universalxyzdom.xyz
 
Вы можете оставить комментарий или задать вопрос
Ваше имя:

Текст сообщения:


Copyright © 2009-2014 by