[ALGORITMO] Commesso viaggiatore euclideo

[oregon]

Originariamente inviato da Cesaropa12
Mi basta ...

Sarebbe stato "carino" che tu avessi fatto questo semplice discorso all'inizio, invece di porre in maniera "asettica" i testi degli esercizi ...

E magari con una "tua" idea su cui cominciare tutti a riflettere ...

[fisica]

Mmh, vediamo, raddoppio i punti totali in modo simmetrico
li numero da -n a n "saltando lo 0" (lo considero un punto di passaggio)
Vale la legge sel(a) <==> non/sel(-a)
ovvero, posso decidere di selezionare un numero se e solo se l'opposto non è selezionato

in questo modo sono rispettate le condizioni del problema iniziale

con questa premessa, considerando la richiesta che mi dice di dover passare per tutti i punti solo muovendomi da sinistra a destra posso dire che, arrivato a 0, i punti da 1 a n sono logicamente conseguenti dalla configurazione precedente (infatti devo passare per tutti i punti, muovendomi di +1)

genero un numero binario di n cifre e lo leggo in questo modo: l'ennesimo nodo del percorso è selezionato nel passaggio del primo tratto se la corrispondente parte del numero binario è 1, chiaramente arrivato al punto 0 (che ho detto, non è un punto ma una "linea di passaggio") le scelte sono conseguenti per quello che ho detto sopra, ora seguendo le istruzioni che mi dice tale numero calcolo la lunghezza del percorso e la tengo in memoria.
se il successivo è minore la scarto e tengo il successivo, se no no....

da dire che, per n punti ho (2^n)-1 percorsi, mentre per il problema del commesso viaggiatore ce ne vogliono n!

spero di aver fatto un ragionamento valido, altrimenti per favore ditemi dove ho sbagliato (c'è sempre qualcosa da imparare da un errore)