Quelle est la longueur attendue du chemin hamiltonien le plus court sur des points sélectionnés au hasard à partir d'une grille planaire?

$k$ points distincts sont choisis au hasard dans une grille . (Évidemment et est un nombre constant donné.) Un graphique pondéré complet est construit à partir de ces points de telle sorte que le poids de l'arête entre le sommet et le sommet est égal à la distance Manhattan de deux sommets sur la grille d'origine . $p\times q$ $k\leq p\times q$ $k$ $i$ $j$

Je cherche un moyen efficace de calculer la longueur attendue du chemin hamiltonien le plus court (poids total minimum) passant par ces nœuds. Plus précisément, les approches naïves suivantes ne sont pas souhaitées: $k$

$\bullet$ Calcul de la longueur exacte du chemin pour toutes les combinaisons de k nœuds et dérivation de la longueur attendue.

$\bullet$ Calcul de la longueur approximative du chemin pour toutes les combinaisons de k nœuds en utilisant l'heuristique de base de l'utilisation d'un arbre couvrant minimum qui donne jusqu'à 50% d'erreur. (Une meilleure heuristique avec moins d'erreur peut être utile)

graph-theory co.combinatorics planar-graphs hamiltonian-paths Javad
la source

Actuellement, il n'y a aucun espoir d'algorithme efficace car le problème de chemin hamiltonien non pondéré sur la grille planaire est NP-complet.

Mohammad Al-Turkistany

Quand vous parlez de chemin hamiltonien, pensez-vous au chemin hamiltonien avec le plus petit poids (aka. Le problème du voyageur de commerce)?

a3nm

@ MohammadAl-Turkistany la dureté de HAM PATH n'est pas nécessairement un obstacle, puisque le PO n'est qu'une estimation pour des points aléatoires.

Suresh Venkat

@ a3nm oui, et je l'ai corrigé.

Suresh Venkat

Qu'y a-t-il de mal à calculer la longueur exacte du tour pour de nombreux échantillons aléatoires de points et à trouver l'attente et l'écart-type? Quelle taille avez-vous besoin de pour être?

k

$k$

k, p, q

$k, p, q$

Peter Shor

En supposant que et soient assez grands, on s'attendrait à ce que la longueur attendue dépende principalement de la densité, avec un terme de correction dépendant du périmètre. Il serait donc, au premier ordre, fonction de la forme suivante. $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).$

Maintenant, vous pouvez utiliser des expériences sur des problèmes de plus petite taille pour déterminer ce que sont et . Tout d'abord, pour estimer , vous voulez faire des expériences sur un échantillon sans frontière: la façon la plus simple de le faire est d'utiliser une grille avec le côté gauche connecté à droite et le haut vers le bas, formant un torus. Pour estimer , vous pouvez utiliser des expériences sur une grille . $f$ $g$ $f$ $p\times p$ $g$ $p \times q$

Pour l'estimation, vous devez résoudre (exactement ou approximativement) des TSP relativement grands, car plus ceux que vous utilisez pour l'estimation sont grands, meilleurs seront vos résultats. Vous pouvez soit utiliser des heuristiques de l'ordre de quelques pour cent, soit du code TSP exact. Voir ici pour quelques bonnes heuristiques. Le solveur Concorde TSP de Bill Cook trouvera l'optimum exact pour des instances raisonnablement importantes (c'est le meilleur code TSP disponible) et peut être utilisé sans frais pour la recherche universitaire.

Peter Shor
la source

En utilisant la terminologie de TSPLIB , je cherchais SOP et non TSP. La multiplication de calculé pour TSP par donne une limite supérieure pour SOP. Malheureusement, le solveur Concorde TSP ne gère pas les SOP et je n'ai trouvé aucun solveur SOP en ligne.

E [L]

$E[L]$

(k - 1) / k

$(k-1)/k$

Javad

Je suppose que pour calculer , les cas qui ont des plus grands et des plus petits sont également répartis autour de , donc on peut trouver une approche constructive pour trouver un arrangement de points dans la grille ce qui (peut-être approximativement) donne . Trouver un tel arrangement diminuerait évidemment considérablement le coût du calcul.

E [L]

$E[L]$

L

$L$

L

$L$

E [L]

$E[L]$

k

$k$

E [L]

$E[L]$

Javad

Je n'ai pas non plus bien compris la raison du coefficient . Pourquoi ne serait-ce pas ? Comment cette formulation d'approximation change-t-elle pour des valeurs plus petites de et ?

k^{2}

$k^2$

k^{2} / (p q)

$k^2/(pq)$

p

$p$

q

$q$

Javad

@Javad: Bonne question. J'avais tort, parce que je pensais en quelque sorte à points quand j'ai écrit ma réponse. Le coefficient vient de mon hypothèse que la grille a des bords de longueur unitaire, donc toute la région est de taille . Le bord moyen doit être de longueur , et il y a bords, donc si vous voulez que reste à peu près constant, le premier terme doit être .

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)$

Peter Shor

Pour , la différence entre la longueur TSP et la longueur SOP devrait être presque négligeable.

k \approx 10^{6}

$k \approx 10^6$

Peter Shor

Quelle est la longueur attendue du chemin hamiltonien le plus court sur des points sélectionnés au hasard à partir d'une grille planaire?

Réponses: