Случайный цикл самоопределения решетки внутри заданной ограничительной рамки

В связи с загадкой Slither Link мне было интересно: предположим, что у меня сетка квадратных ячеек, и я хочу найти простой цикл ребер сетки, равномерно случайным образом среди всех возможных простых циклов. $n\times n$

Один из способов сделать это - использовать цепь Маркова, состояния которой представляют собой наборы квадратов, границы которых являются простыми циклами, а переходы состоят из выбора случайного квадрата для переворачивания и удержания переворота, когда измененный набор квадратов все еще имеет простой цикл как его граница. Таким способом можно перейти от любого простого цикла к любому другому (используя стандартные результаты о существовании оболочек), так что в конечном итоге это сходится к равномерному распределению, но как быстро?

В качестве альтернативы, есть ли лучшая цепь Маркова или прямой метод выбора простых циклов?

ETA: см. В этом сообщении в блоге код для расчета количества циклов, которые я ищу, и указатели на OEIS для некоторых из этих чисел. Как мы знаем, подсчет - это почти то же самое, что и случайная генерация, и я заключаю из отсутствия какой-либо очевидной закономерности в факторизации этих чисел и отсутствия формулы в записи OEIS, что вряд ли существует известный простой прямой метод , Но это все еще оставляет вопрос о том, как быстро эта цепь сходится и есть ли лучшая цепь широко открыта.

ds.algorithms randomness markov-chains integer-lattice Дэвид Эппштейн
источник

Граница наборов, подсчитываемых последовательностью OEIS, не обязательно является простым циклом, например, для 3x3, один из 218 имеет все квадраты, кроме середины, а остальные четыре задаются путем дальнейшего удаления одного угла.

Колин МакКиллан

Для сеток 2xn числа указаны в oeis.org/A059020 . Для 3xn я уверен, что это 6,40,213,1049,5034,23984,114069,542295,2577870,12253948,58249011,276885683,1316170990,6256394122,29739651711,141366874247, ... (не в OEIS). Я настроил матрицу переноса, чтобы вычислить ее вручную, но сравнил ее с сгенерированной машиной матрицей, и единственное, что они отличали, это то, что рука была правильной, а машина - неправильной. (Это должно проявиться в случае 3x3 - матрица станка позволила бы октомино с отверстием в центре.)

Дэвид Эппштейн

Вы должны отправить эту последовательность Нилу Слоану, чтобы он мог поместить ее в OEIS.

Питер Шор

@ Дэвид: Спасибо. Возможно, пришло время изучить метод матрицы переноса более тщательно.

Ёсио Окамото

@ Давид: Вы просто потратили два часа моей жизни с этой ссылкой на головоломку .. Спасибо!

Домоторп

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

Обратите внимание, что число циклов в графе , содержащем ребро , равно числу циклов в плюс количество простых путей от до в . Таким образом, с помощью аппроксимации полиномиального времени для числа - путей аппроксимация полиномиального времени может быть достигнута путем постепенного наращивания до одного ребра за раз, аппроксимируя по мере движения. $G$ $(u, v)$ $G - (u, v)$ $u$ $v$ $G - (u, v)$ $u$ $v$ $G$

$G$ $n \times n$ $(u, v)$ $u$ $v$ $G$ $(u, v)$

$C$ $v_s$ $v_e$ $N$ $v_e$ $C$ $u \in N$ $u$ $v_s$ $G[V - (C - \{v_s, v_e \} ) ]$ $u$ $v_e$ $(v_e, u)$

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

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

bbejot
источник

Случайный цикл самоопределения решетки внутри заданной ограничительной рамки

Ответы: