Forse è possibile generare i propri dati di test?
Questo sicuramente non sarà un test completo, ma potrebbe essere d'aiuto. Nota: il seguito riguarda il percorso hamiltoniano e se stai cercando cicli, qualcosa di simile funzionerà.
È possibile effettuare le seguenti operazioni:
Dire si è dato un grafo non orientato G con n nodi.
Ora si crea un grafico ponderato G ', impostando il peso dei bordi in G come 1, e aggiungendo i bordi non in G, e dando loro un peso casuale> 1, cioè G' è un grafico completo con pesi assegnati a tutti i suoi bordi.
Ora se si esegue un algoritmo TSP valido su G 'e si genera un percorso di dimensione n-1, G ha un percorso hamiltoniano. Altrimenti G non ha un percorso hamiltoniano.
Così ora è possibile utilizzare i grafici si sapere che hanno/non hanno cammini hamiltoniani (per es: Hypercube ha cammini hamiltoniani) e generare dati di test per il vostro algoritmo TSP.
Questa pagina ha alcune condizioni sufficienti che potrebbero rivelarsi utili nella generazione di grafici che hanno percorsi hamiltoniani: http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
immagino che non avrà difficoltà a trovare i dati su grafici con/senza cammini hamiltoniani.
Spero che aiuti. In bocca al lupo!
fonte
2010-06-02 16:33:06
C'è sempre la vendita su eBay, che a quanto pare è O (1). :-P http://xkcd.com/399/ –