[image]https://leganerd.com/wp-content/uploads/LEGANERD_040183.jpg[/image]
[quote]Il problema con la formulazione hamiltoniana è che è bidirezionale.[/quote]
L’algoritmo di routing è alla base dei protocolli di [url=http://it.wikipedia.org/wiki/Instradamento]instradamento[/url] nelle reti di calcolatori. Queste sono generalizzabili come grafi -dei quali avevamo accennato qualcosa nella [url=https://leganerd.com/2011/02/21/xkcd-np-completo/]prima puntata[/url] di questa rubrica- e quindi gli algoritmi che gestiscono l’instradamento dei pacchetti di dati (ovvero la spedizione dei byte da un computer all’altro lungo un percorso) sono di solito derivati tramite la [url=http://it.wikipedia.org/wiki/Teoria_dei_grafi]teoria dei grafi[/url].
Si parla di [url=http://it.wikipedia.org/wiki/Cammino_hamiltoniano]cammino hamiltoniano[/url] quando si trova un percorso che passi per tutti i vertici una e una sola volta, se questo percorso è chiuso, ovvero se inizia e finisce dallo stesso nodo, si dice che esso è un ‘ciclo hamiltoniano’.
Vignetta originale su [url=http://xkcd.com/230]XKCD[/url].