due venditori - una visita sempre il vicino più prossimo, l'altro il più lontano

Question

considerare questa domanda relativa alla teoria dei grafi: Let G un completo (ogni vertice è collegato a tutti gli altri vertici) grafo non diretto di dimensioni N x N. Due "venditori" viaggiano in questo modo: il primo visita sempre il vertice non visitato più vicino, il secondo il più lontano, fino a quando entrambi hanno visitato tutti i vertici. Dobbiamo generare una matrice di distanze e punti di partenza per i due venditori (possono essere diversi) tale che:

• Tutte le distanze sono Edit unico: interi positivi
• La distanza da un vertice è sempre 0.
• La differenza tra la distanza totale coperta dai due venditori deve essere un numero specifico, D.
• La distanza da A a B è uguale alla distanza da B ad A

Quali algoritmi efficienti cn essere utile per aiutare me? Posso solo pensare al backtracking, ma non vedo alcun modo per ridurre il lavoro che deve fare il programma.

Answer 1

La geometria è utile.

L'utilizzo delle distanze dei punti su un cerchio sembra funzionare. Sembra che potresti determinare la regolazione D aumentando o riducendo il raggio del cerchio.

In alternativa, è probabile che sia effettivamente possibile utilizzare qualsiasi forma 2D, in cui le distanze siano tutte diverse. In questo caso, è necessario aumentare o ridurre la forma per ottenere il valore corretto D.

• Edit: Ora che ci penso, la soluzione più semplice potrebbe essere quella di scegliere semplicemente punti 2D N casuali, dire coordina 32 interi bit per abbassare le probabilità di eventuali distanze di essere troppo vicino alla parità. Se due distanze sono troppo vicine, scegli un punto diverso per una di esse finché non è valido.

Idealmente, avresti solo bisogno di elaborare una formula per determinare la relazione tra D e il fattore di ridimensionamento, che non sono sicuro di offhand. Se non altro, si potrebbe anche usare solo la ricerca binaria o la ricerca di interpolazione o qualcosa per cercare il fattore di scala per ottenere il richiesto D, ma questo è un metodo più lento.