No estará lo que buscas en GitHub???...

Saludos.

 

Es muy difícil verificar "que tan eficaz es" tu algoritmo comparado con otro para un problema cuya resolución no existe salvo la fuerza bruta.

Si tu algoritmo también sigue el método de ramificación y poda, el rendimiento de tu algoritmo, va a depender casi exclusivamente de la profundidad de conocimiento en el lenguaje usado. En casos así elegir la estructura de datos adecuada, puede suponer una gran diferencia aun cuando otras partes del algoritmo, no sean igual de eficientes.

Considera la eficiacia (para este caso) como la mejor aproximación al resultado real y la eficiencia o rendimiento como el tiempo empleado. Ambos son igual de deseables...
La eficacia en estos casos están basado en heurísticas y ahí es muy dependiente de los ejemplos usados. Es perfectamente posible que un algoritmo arroje mejores resultados con ciertos ejemplos respecto de otro algoritmo y peores resultados con otros ejemplos.

Por otro lado el mayor limitante para verificar la eficacia es el tiempo preciso para encontrar resultados allí donde el tiempo es una premisa mayor... para acotaciones limitadas, siempre podrá modificarse un algoritmo para arrojar mejores resultados, más aproximados a la solución real.
Con la eficiencia, pasa lo mismo. Hay algoritmos que son muy rápidos para un cierto orden y a medida que aumenta el orden, disminuye su eficiencia y viceversa (por ejemplo la 'búsqueda por el método de burbuja' es más eficiente que quicksort, para (por ejemplo) 100 elementos, es comparativamente similar con 1000 elementos, pero es notablemente deficiente con 1.000.000 de elementos). Dado la explosión combinatoria del problema del agente viajero, la eficiacia y eficiencia de un algoritmo frente a otro exige pruebas exhaustivas, precisamente en diferentes órdenes de tamaño, y la que mayor determine la eficacia es prohibitiva en el tiempo, aunque si para pocas es menor y con cada aumento en la complejidad, sigue una curva de menor, parece que no vaya a cambiar la tendencia. Aún así es fácil demostrar esto para la eficiencia, pero no para la eficacia (exactitud en el resultado), ya que no hay forma de valorar una eficacia basada en los resultados que se arrojen.

Si tienes una soluciones (hipotéticas, pongamos) como en la siguiente tabla:

nº de prueba  items en juego   solucion real   tu solucion su solucion
-------------------------------------------------------------------------------
1                 5                   500          500          500     
2                 10                 1800         1800         1800
3                 20                 4723         4723         4723
4                 40                22000        22000        22000
5                 80               110000       109000       109600
6                 160              456000        44000       438000
7                 320             1380000      1350000      1360000
8                 640             9000000      8880000      8879000
9                 1280           25000000     24820000     24840000

Como ves, cuando la cantidad de items es poca, la solución puede ser real, o variar muy levemente, pero a medida que aumenten los valores, y sobretodo dependiente de cada ejemplo, un algoritmo podría arrojar una solución más cercana a la real en un problema concreto y más elejada en otro.. entonce no hay forma de valorarlo con precisión para decidir que uno es más eficaz que otro. Más bien en estos casos, lo que se valoran son las premisas requeridas, en resumen se adapta a las necesidades que la situación exija. Por ejemplo el factor tiempo puede dar más peso... así un sistema que solucione en pongamos 10 segundos aunque el valor real pudiera ser menos preciso, puede ser preferible a otro sistema que arroja una mejor precisión pero que demore 5 minutos en dar dicha solución.
En este problema la precisión (eficacia) y el tiempo (eificnecia) están en contraposición y debe valorarse un equilibrio entre ambos.

No. Es un problema no resuelto.
No existe ningún algoritmo conocido al margen de la fuerza bruta que garantice la solución correcta.
Nota que el diseño de un algoritmo que lo resuelva debe resolver todos los casos (para ser tenido como tal), y no uno que solo resuelva casos demasiado simples (para estos casos siempre podrá crearse un algoritmo eficaz y aceptable en tiempo).

Se recurre a heurísticas (aproximación a la solución, pero sin poder saber realmente si es la solución real), como te comentaba al señalarte:

Bien...
Si crees haber creado un algoritmo que resuelva el problema, lo primero es asegurarte que es así.
Para ello genera muy diferentes ejemplos, calculas por fuerza bruta la solución y tiempo empleado y luego lo comparas con tu algoritmo (importa sobre todo que la solución sea correcta, pués el tiempo es de suponer que será más eficiente que la fuerza bruta, si esto último no fuere así, no solucionaría nada, obviamente).
Cuando lo anterior quede satisfecho, intenta ponerte en contacto con un centro que tenga un superordenador, pregúntales si tienen datos de algún problema del viajero cuya solución hayan calculado, pídeles los datos para algo como 1000, 100.000 y 10 millones (por ejemplo), cuando lo resuelvas con tu algoritmo, dales la solución para que la comparen con la que ellos obtuvieron, si no coincide, pide la solución donde no coincide (la comparación en primera instancia sería la medida total, fallando, conviene tener como solución la ruta seguida, de modo que tú mismo puedas comparar si la suma de ellos es errónea, aunque pudiera ser que el problema fuere debido a la precisión de los decimales (es habitual esta discrepancia cuando se usa un PC y se compara el resultado con los obtenidos en un superordenador cuya coma flotante es muy superior), es decir que quede claro si la discrepancia es debida a la cuestión de la precisión o a un error en tu algoritmo.

- Si la solución coincide perfectamente, plánteate primero registrar tu algoritmo (al menos la propiedad intelectual, que quede acreditada a tu nombre), luego según lo que quiesieres hacer debes operar, si quieres que quede libre, solicita ayuda técnica para publicar un paper a los que te ayudaron en el superordenador... y si quieres obtener beneficios, podrías ponerte en contacto con grandes empresas.
Es muy conveniente antes de esto, intentar optimizarlo, pues no faltará quien partiendo de tu algoritmo haga unos simples cambios (a veces obvios) y reclamar que hizo una mejora sustancial sobre tu algoritmo (en general suele pasar a la historia el autor del algortimo más óptimo, especialmente si los menos óptimos, son además muy engorrosos de implementar).
Al margen de ello, el instituto Clay ofrece una recompensa para los 'Problemas del Milenio', creo recordar que éste (no exactamente el problema, si no que su resolución demostraría que los problemas NP son equivalentes a los problemas P y que por tanto pueden ser resueltos en tiempo polinómico). Por supuesto ese 'paper' debieras crearlo antes, porque sería lo que al final entregarías para reclamar el premio. (prize.problems@claymath.org , admin@claymath.org Nota para Admins, no borrar emails, son públicos)

- Si la solución no coincide (y ya probaste que no fue debido a error en la precisión de decimales), intenta escrutar donde pudiera estar el problema y tratar de arreglarlo. Si lo consigues, considera el paso anterior.

Si la solución no coincide, y no consigues resolverlo, intenta al menos determinar hasta que tamaño tu algoritmo resulta válido, seguramente todavía tenga interés un algoritmo que resuelva eficientemente (la fuerza bruta es muy ineficiente), para un número medio de nodos (pongamos entre cientos y pocos miles, pues cosas como semáforos, paradas de buses, etc... andan en esos términos). Simplemente sería un 'algoritmo menor del agente viajero' y a buena fé podría dar pistas a otros para intentar partiendo del mismo una solución total.

Considera que aunque se diga 'fuerza bruta' a menudo es razonable no practicarla en su totalidad, si no que puede ser podada... por ejemplo mi intuición me dice que en la práctica si los nodos tienen una distribución uniforme, bastaría con considerar para cada nodo la raíz cuadrada de los nodos, luego estos se escogerían entre los x más cercanos al mismo.
Resulta obvio lo absurdo de considerar cualquier ruta cuyo tramo parcial consista en ir de un nodo al nodo más lejano a éste, lo cual se puede descartar para todos los nodos, igualmente podría decirse lo mismo para el penúiltimo más lejano, etc... no queda claro el punto donde esto deja de ser cierto (ya digo que mi intuición me señala que es la raíz cuadrada aprox. para una distribución más o menos uniforme, como regla general).

Eso sí... prueba también con nodos cuya posición sea elegida al azar dentro de un área dada, para garantizar que no hay cierto vicio en los mapas seleccionados.

Tengo por ahí un programa de grafos para resolver determinados problemas, creo que se podría ajustar perfectamente para hallar soluciones por fuerza bruta (en realidad cortocircuita una ruta cuando la suma de un nodo supera la longitud de un trayecto que previamente ha sido más corto). Quizás tuviera que reajustarlo, porque creo recordar que lo hice para operar con pesos de valor entero (no con decimales)... Además tampoco precisa recorrer todas las rutas, ya que A-B-C es equivalente a C-B-A, a lo sumo precisa explorar = (((n-1)*2)/2) rutas.
...para nodos de pocas decenas calcularía perfectamente la solución en un tiempo asumible, así que si precisas comparar tus resultados, basta que me pases un mapa (una tabla de los nodos con las distancias al resto de ellos). Así se podría comparar si efectivamente tu algoritmo genera la solución óptima.

Gracias por la explicacion, aca te envio de manera mas aceptable.

La solucion que encontre como optima fue de 7561324 como costo de trayecto, cual seria el siguiente: 1-12-2-19-7-9-20-14-6-18-4-10-16-3-17-8-13-11-5-15-1.