Um problema específico de programação que encontrei recentemente reduz a localização de caminhos hamiltonianos em uma grade retangular que seria algo como,
A 0 0 0
0 0 0 0
0 0 C D
Quais são algumas heurísticas eficazes que podem ser aplicadas para encontrá-las - e particularmente técnicas para aparar / descartar caminhos ao longo do caminho?
Editar: Apenas para esclarecer, as arestas são formadas quando os elementos são conectados horizontal e verticalmente, mas não na diagonal. O problema também afirma que qualquer elemento marcado como 0 pode ser usado para formar um caminho, mas os elementos que não são 0 são "obstáculos" que precisam ser evitados.
A-0-0-0
|
0-0-0-0
|
0-0-C D
poderia ser um caminho, por exemplo. Outro pode ser,
A 0-0-0
| | |
0 0 0-0
| | |
0-0 C D
ds.algorithms
hamiltonian-paths
viksit
fonte
fonte
Respostas:
Não vejo uma maneira fácil de contar sem enumerar. Você pode visitar facilmente todos os caminhos hamiltonianos com uma pesquisa exaustiva e profunda com retorno. Você pode realmente trapacear um pouco e perceber que, se N é o número de caminhos hamiltonianos que começam indo para a direita, o número total de caminhos hamiltonianos é 2N (devido à simetria se a grade). Isso não se estende até o fim (para alguns vértices, nem todos os caminhos levam ao mesmo número de ciclos, mas você pode limitar o número de caminhos hamiltonianos facilmente com um argumento semelhante (com o bônus de que você pode resolver partes dele exatamente para melhorar sua ligação com argumentos de simetria.) Essa é a estratégia que eu escolheria.
Mas se você não quiser isso, algumas heurísticas genéricas:
Você também pode facilmente colocar no limite superior o número de caminhos hamiltonianos como | E | escolha | V | -1 (onde | E | é o número de arestas e | V | o número de vértices no gráfico), o que pode ser muito melhor para um gráfico esparso que | V |! (o limite ingênuo que assume que o gráfico está completo).
Uma maneira fácil de melhorar esse limite é aparar combinações conhecidas e ruins, não considerando duas arestas do mesmo vértice. Então você obteria algo como prod_v (deg_v-1) (que ainda deve limitar o número de caminhos hamiltonianos, já que agora você está contando ciclos mais de uma vez, eu acho).
fonte