Qual o comprimento esperado do caminho hamiltoniano mais curto em pontos selecionados aleatoriamente em uma grade plana?

$k$ pontos distintos são selecionados aleatoriamente em uma grade . (Obviamente, e é um dado número constante.) Um gráfico ponderado completo é construído a partir desses pontos modo que o peso da aresta entre o vértice vértice seja igual à distância de Manhattan de dois vértices na grade original . $p\times q$ $k\leq p\times q$ $k$ $i$ $j$

Estou procurando uma maneira eficiente de calcular o comprimento esperado do caminho hamiltoniano mais curto (peso total mínimo) que passa por esses $k$ nós. Mais precisamente, as seguintes abordagens ingênuas não são desejadas:

$\bullet$ Calculando o comprimento exato do caminho para todas as combinações de nós k e derivando o comprimento esperado.

$\bullet$ Calculando o comprimento aproximado do caminho para todas as combinações de k nós usando a heurística básica do uso da árvore de abrangência mínima, que gera até 50% de erro. (Uma heurística melhor com menos erros pode ser útil)

graph-theory co.combinatorics planar-graphs hamiltonian-paths Javad
fonte

Atualmente, não há esperança para um algoritmo eficiente, pois o problema do caminho hamiltoniano não ponderado na grade plana é NP-completo.

Mohammad Al-Turkistany

Quando você fala do caminho hamiltoniano, está pensando no caminho hamiltoniano com menor peso (também conhecido como problema do vendedor ambulante)?

a3nm

@ MohammadAl-Turkistany a dureza do HAM PATH não é necessariamente um obstáculo, já que o OP é apenas uma estimativa para pontos aleatórios.

Suresh Venkat

@ a3nm sim, e eu consertei.

Suresh Venkat

O que há de errado em calcular a duração exata do passeio para muitas amostras aleatórias de pontos e encontrar a expectativa e o desvio padrão? Qual é o tamanho de para ser?

k

$k$

k, p, q

$k, p, q$

quer

Respostas:

Supondo que e sejam razoavelmente grandes, seria de esperar que o comprimento esperado dependesse principalmente da densidade, com algum termo de correção dependendo do perímetro. Portanto, seria, em primeira ordem, uma função da seguinte forma. $p$ $q$

L \approx (p q k)^{1 / 2} f (k / p q) + (p + q) g (k / p q) .

$L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$

Agora, você pode usar experimentos com problemas de tamanho menor para descobrir o que e são. Primeiro, para estimar , você quer fazer experimentos com uma amostra sem um limite: a maneira mais fácil de fazer isso é usar uma grade com o lado esquerdo ligado à direita e parte superior para a parte inferior, formando um toro . Para estimar , você pode usar experimentos em uma grade . $f$ $g$ $f$ $p\times p$ $g$ $p \times q$

Para a estimativa, você precisa resolver (exatamente ou aproximadamente) TSPs relativamente grandes, pois quanto maiores os usados para a estimativa, melhores serão os resultados. Você pode usar heurísticas que vêm dentro de alguns por cento ou o código TSP exato. Veja aqui algumas boas heurísticas. O solucionador Concorde TSP de Bill Cook encontrará o ideal exato para instâncias razoavelmente grandes (é o melhor código TSP disponível) e pode ser usado gratuitamente para pesquisas acadêmicas.

Peter Shor
fonte

Usando a terminologia do TSPLIB , eu estava procurando por SOP e não por TSP. Multiplicar o

calculado para TSP por

fornece um limite superior para SOP. Infelizmente, o solucionador Concorde TSP não suporta SOPs e não encontrei nenhum solucionador de SOP online.

E [L]

$E[L]$

(k - 1) / k

$(k-1)/k$

Javad

Eu acho que, para o cálculo de

, os casos com

maior e

menor são igualmente distribuídos em torno de

, portanto, pode-se chegar a uma abordagem construtiva para encontrar um arranjo de

pontos na grade que (talvez aproximadamente) dá

. Encontrar esse arranjo obviamente reduziria drasticamente o custo da computação.

E [L]

$E[L]$

L

$L$

L

$L$

E [L]

$E[L]$

k

$k$

E [L]

$E[L]$

Javad

Também não entendi bem o motivo do coeficiente

. Por que não deveria ser

? Como essa formulação de aproximação muda para valores menores de

k^{2}

$k^2$

k^{2} / (p q)

$k^2/(pq)$

p

$p$

q

$q$

Javad

@Javad: Boa pergunta. Eu estava errado, porque de alguma forma estava pensando

pontos quando escrevi minha resposta. O coeficiente vem da minha suposição de que a grade

possui arestas de comprimento unitário; portanto, toda a região é do tamanho

. A aresta média deve ter comprimento

k^{2}

$k^2$

p \times q

$p\times q$

p \times q

$p \times q$

θ (\sqrt{p q / k})

$\theta(\sqrt{pq/k})$

k

$k$

f

$f$

\sqrt{p q k} f (k / p q)

$\sqrt{pqk} f(k/pq)$

k \approx 10^{6}

$k \approx 10^6$