Estou tentando resolver uma versão ligeiramente modificada doHamiltonian Path problema. É modificado no sentido de fornecer os pontos inicial e final e, em vez de determinar se existe uma solução, queremos encontrar onúmer de soluções (que pode ser 0

O gráfico é fornecido como uma matriz 2D, com os nós sendo os elementos da matriz. Além disso, só podemos nos mover na horizontal ou na vertical, e não na diagonal. Escusado será dizer que não podemos ir de uma cidade para duas cidades porque, para fazer isso, precisaríamos visitar uma cidade duas veze

Eu escrevi uma solução de força bruta que tenta todos os 4 movimentos possíveis (3 ou 2 para nós nas bordas) em cada nó e conta o número de soluções (que é quando atinge a meta e também vê todos os outros nós), mas funcionou por quantidades ridículas de tempo em entradas de tamanho modesto (como, digamos, uma matriz 7x7

Eu também pensei em usarbidirectional search já que conhecemos o objetivo, mas isso realmente não ajudou, já que não queremos apenas que as franjas se encontrem, queremos também garantir que todos os nós tenham sido visitados. Além disso, pode ser que quando todos os nós estiverem esgotados entre as duas franjas, eles terminem de uma maneira que não possam ser unido

Sinto que há algo que não sei que me deixa com apenas uma solução de força bruta. Eu sei que o problema em si é NP-completo, mas estou me perguntando se há alguma melhoria em relação à força bruta. Alguém pode sugerir outra coisa?

--Editar-

Mencionei que o uso da pesquisa bidirecional não ajuda muito e gostaria de esclarecer por que achava isso. Considere um gráfico 2x3 com os nós superior esquerdo e inferior direito sendo o início e o objetivo, respectivamente. Deixe as margens da pesquisa bidirecional moverem-se para a direita desde o início e para a esquerda da meta. Após 2 movimentos, todos os nós teriam sido visitados, mas não há como juntar as franjas, pois só podemos ir em uma direção a partir de um nó. No entanto, pode ser possível fazer o algoritmo funcionar com algumas modificações, como David apontou em sua resposta abaix