Don't take life too seriously: it's just a temporary situation

Commesso viaggiatore (costante del)

Matematica combinatoria 

Il nome deriva dal noto problema del “commesso viaggiatore”: trovare il minimo percorso che passi per un insieme di punti fissati.

E’ un ben noto esempio di problema NP-completo: sebbene siano noti ottimi algoritmi per trovare soluzioni approssimate, il tempo di calcolo nei casi peggiori cresce esponenzialmente col numero di punti, almeno con gli algoritmi oggi noti. Trovare il percorso minimo tra tutti i capoluoghi di provincia italiani è un compito ai limiti delle possibilità dei calcolatori odierni.

 

E’ stato dimostrato che se L(n, d) è la lunghezza minima del cammino chiuso che tocca n punti in un ipercubo a d dimensioni, comunque siano scelti i punti Limite superiore della lunghezza minima del cammino chiuso che tocca n punti e per quasi tutte le posizioni dei punti Limite superiore della lunghezza minima del cammino chiuso che tocca n punti in quasi tutti i casi, dove le costanti α(d) e β(d) dipendono solo dalle dimensioni.

 

Su queste costanti sappiamo che:

  • Limiti per il valore di α(2);

  • Limiti per il valore di α(3);

  • Limiti per il valore di α(4);
  • Limiti per il valore del limite di α(n);

  • Limiti per il valore di β(2);

  • Limiti per il valore di β(3);

  • Limiti per il valore di β(4);

  • Limiti per il valore dei limiti di β(n).

In queste formule Formula per la definizione di γ(n).

 

In due dimensioni, definendo la costante K come Formula per la definizione di K, vale Limiti per il valore di K e vari esperimenti numerici hanno portato alla conclusione che K sia vicina a 0.7120.

 

Considerando un particolare tipo di curva, definita per iterazioni successive e capace di riempire il quadrato di lato unitario, taluni esperti hanno supposto che la costante sia uguale a Formula per la costante del commesso viaggiatore, dove Lm è la lunghezza della curva dopo m iterazioni e nm è il numero di punti raggiunti, e questa costante è detta “costante del commesso viaggiatore”.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.