algoritmo de tempo polinomial para encontrar uma caminhada hamiltoniano em um gráfico [fechado]

Question

Existe um algoritmo de tempo polinomial para encontrar uma caminhada hamiltoniano em um gráfico?

O meu algoritmo é N fatorial e é muito lento.

Answer 1

Você só pediu a milhões questão dólar . Encontrar um caminho Hamilton é um problema NP-completo. Alguns problemas NP-hard pode ser resolvido em tempo polinomial usando programação dinâmica, mas (a meu conhecimento), este não é um deles.

Answer 2

Em geral, como o (versão decisão do) problema do caminho hamiltoniano é NP-completo, você não pode esperar para obter um algoritmo de tempo polinomial para encontrar caminhos hamiltonianos. Você pode ligeiramente acelerá-lo com o N de costume! ? N ² 2 ^N truque de programação dinâmico (computação cv [V] [W] [S] = "existe um caminho que tem pontos de extremidade V e W e cujos vértices estão o subconjunto S" para cada subconjunto S ea cada dois vértices v e W no-lo usando DP), mas que ainda é exponencial.

No entanto, existem muitos tipos especiais de gráficos para que sempre existem caminhos hamiltonianos, e eles podem ser facilmente encontrados (ver o trabalho de Posa, Dirac, minério, etc.)

Por exemplo, o seguinte é válido: Se todos os vértices do gráfico tem um grau de pelo menos n / 2 , em seguida, o gráfico tem um caminho hamiltoniano. Você pode, de facto, encontrar um em O (n ² ), ou IIRC mesmo O (n log n) se você fizer isso mais inteligente.
[Áspero esboço: Em primeiro lugar, basta conectar todos os vértices em algum ciclo "Hamiltonian", deixa pra lá, se as bordas são realmente no gráfico. Agora, para cada aresta (v, w) do seu ciclo que não é, na verdade, no gráfico, considere o resto do ciclo: v ... w. Como deg (v) + deg (w)> = n, existem x consecutivo, y em sua lista (nessa ordem) tal que w é um vizinho de x e v é um vizinho de y. [Prova: Considere {o conjunto de todos os vizinhos de w} e {o conjunto de todos os sucessores na sua lista de vizinhos de v}; eles devem se cruzar.] Agora, mudar o seu ciclo [v ... xy ... wv] para [vy ... wx ... v] em vez disso, ele tem pelo menos uma borda menos inválida, então você vai precisar de, no máximo, n iterações para obter um verdadeiro ciclo hamiltoniano. Mais detalhes aqui .]

BTW: se o que você está procurando é apenas um passeio que inclui cada aresta uma vez, ele é chamado de pé Eulerian e para os gráficos que têm-lo (número de vértices de grau ímpar é 0 ou 2 ), pode-se facilmente ser encontrada em tempo polinomial (rápido).

Answer 3

completa Está NP. Mas se você conseguir encontrar um método bom, deixe-me saber e eu vou mostrar-lhe como ficar rico.

Answer 4

Encontrar um algoritmo melhor para o mais curto é improvável, uma vez que é NP difícil. Mas existem algumas heurísticas que você poderia tentar e, talvez, você pode querer consultar suas notas de aula para aqueles;)

.

Por menos complexidade que você poderia encontrar um pequeno (ish) andar usando o algoritmo guloso.

Answer 5

Hmmm .. isso depende do que suas definições são. Um caminho hamiltoniano é certamente NP-completos. No entanto, uma caminhada hamiltoniano que pode visitar arestas e vértices mais de uma vez (sim, ainda é chamado hamiltonian contanto que você adicionar o pouco caminhada no final) pode ser calculado em O (p ^ 2logp) ou O (max (c ^ 2plogp , | e |)), desde que o seu gráfico atende uma determinada condição que Dirac primeira conjecturou eo Takamizawa provado. Veja Takamizawa (1980) "Um algoritmo para encontrar um curto fechado abrangendo caminhada em um gráfico".

Paul

Answer 6

Dependendo apenas como os gráficos que você está trabalhando com são gerados que você pode ser capaz de se esperar tempo polinomial em uma instância aleatória, fazendo extensão caminho ganancioso e, em seguida, uma troca de borda aleatória quando que fica preso.

Isso funciona bem contra gerados aleatoriamente gráficos relativamente esparsas garantidos para ter uma caminhada hamiltoniano.

Answer 7

Meu Inquérito: Mostrar que um problema de pesquisa RHAM para encontrar um ciclo hamiltoniano no grafo G é auto-redutível A pesquisa problema R é auto-redutível se é Cook-redutível a um problema de decisão
SR={ x : R(x) ≠ ∅ }