Quindi questa potrebbe essere una domanda nata dalla mia incapacità di esprimere correttamente le mie intenzioni su Google.
In un grafo non direzionale completamente connesso tale che qualsiasi tre punti possa essere correttamente rappresentato in un triangolo nella geometria euclidea, sembrerebbe che un primo algoritmo avido che sceglie il bordo più corto troverà il percorso più breve da un punto di partenza per visitare tutti gli altri punti.
Non riesco a trovare una condizione in cui ciò sia falso, ma uno dei miei vicini (un altro programmatore) insiste che ho torto, anche se non riesco ancora a trovare una condizione in cui io abbia torto.
Modifica:
Non sono sicuro che questa domanda sia un'istanza del TSP generale, che so essere difficile da NP, o se penso che tutti i vincoli sui grafici consentiti avrebbero influito sulla difficoltà.
Da wiki: TSP è the shortest possible route that visits each city exactly once and returns to the origin city . In questo problema non è necessario tornare alla città di origine. Inoltre, non ci interessa selezionare la città di origine ottimale poiché la città di origine è impostata nel nostro esempio specifico di cui stavamo discutendo.
Inoltre, il grafico di questo problema deve essere conforme ai vincoli delle distanze euclidee in 2 o 3 dimensioni, quindi tre nodi grafici come sotto (la chiave è il nodo, val sono le distanze tra altri nodi) non potrebbero esistere poiché il bordo da A a B renderebbe i bordi da C a A e B non fattibili.
A:{B:80, C:10}, B:{A:80, C:5}, C:{A:10, B:5}
Anche per connessione completa intendevo che tutti i nodi hanno dei bordi tra loro e ogni altro nodo.
Ci scusiamo se la descrizione è confusa, ma mi chiedo se, data la totalità di questi vincoli, diventi risolvibile in un modo più semplicistico.