Ciclo de treliça aleatória de auto-evitação dentro de uma determinada caixa delimitadora

Em conexão com a Slither Fazer a ligação quebra-cabeça, eu estive pensando: Suponha que eu tenho um grade de células quadrados, e eu quero encontrar um ciclo simples de bordas de grade, uniformemente de forma aleatória entre todos os ciclos simples possíveis.$n\times n$

Uma maneira de fazer isso seria usar uma cadeia de Markov cujos estados são conjuntos de quadrados cujos limites são ciclos simples e cujas transições consistem em escolher um quadrado aleatório para girar e mantê-lo quando o conjunto modificado de quadrados ainda possui um ciclo simples, como seu limite. Pode-se passar de qualquer ciclo simples para outro dessa maneira (usando resultados padrão sobre a existência de cascas), para que isso eventualmente converja para uma distribuição uniforme, mas com que rapidez?

Como alternativa, existe uma cadeia de Markov melhor ou um método direto para selecionar ciclos simples?

ETA: Veja esta postagem no blog para obter um código para calcular o número de ciclos que estou procurando e ponteiros para o OEIS para alguns desses números. Como sabemos, contar é quase o mesmo que geração aleatória, e deduzo da falta de qualquer padrão óbvio nas fatorações desses números e da falta de uma fórmula na entrada OEIS que é improvável que exista um método direto simples conhecido . Mas isso ainda deixa as questões sobre a rapidez com que essa cadeia converge e se há uma cadeia melhor aberta.

Parece que, como você está usando apenas as contagens do número de ciclos em um gráfico para escolher aleatoriamente um ciclo, que se você tivesse uma aproximação aleatória para esse número, ainda assim poderia escolher um ciclo aproximadamente uniformemente.

Observe que o número de ciclos em um gráfico , que contém a aresta ( u , v ) , é igual ao número de ciclos em G - ( u , v ) mais o número de caminhos simples de u a v em G - ( u , v ) . Assim, com uma aproximação de tempo polinomial para o número de caminhos u - v , a aproximação de um tempo polinomial pode ser alcançada construindo-se incrementalmente até G uma aresta por vez, aproximando-se à medida que avança. $G$$(u, v)$$G - (u, v)$$u$$v$$G - (u, v)$$u$$v$$G$

Na verdade, acho que existe um método mais direto para escolher um ciclo. Deixe ser o gráfico inteiro de bordas ao redor do n × n grade de quadrados. Para cada aresta ( u , v ), encontre o número de ciclos que contêm essa aresta (que é o número de caminhos u - v em G - ( u , v ) ). Em seguida, escolha aleatoriamente uma aresta ponderada pelo número de ciclos que a contêm. Essa será a primeira margem do seu ciclo escolhido aleatoriamente. Todas as outras arestas serão escolhidas estendendo uma aresta por vez.$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)$

Dessa maneira, um número polinomial de arestas é escolhido, cada um exigindo um pequeno número de cálculos de um algoritmo de aproximação de tempo polinomial. Assim, um ciclo pode ser escolhido uniformemente.

Atualmente, tenho uma pergunta stackexchange solicitando referências para algoritmos de aproximação de contagem de atalho. Li em alguns lugares que esses algoritmos existem, mas ainda não os encontraram.