Test Foro de elhacker.net SMF 2.1

Espero que al menos no les quitaran las medallas... (que se han ganado ellos, con su esfuerzo).

Creo haber contado las medallas que España consiguió, que son 15 medallas, también y teniendo en cuenta que en España los deportistas (olímpicos) tiene mejores instalaciones depotrivas a su alcance, es todo un mérito que Cuba logre 15 medallas...

Aunque la eficiencia es un país (no recuerdo ahora si era San Marino o un país africano), que con solo presentar 5 deportistas a las olímpiadas, lograron 3 medallas. 

Al final lo dejé corriendo hasta el final...

Cuando me fuí a dormir llevaba calculando alrededor de 24 horas y cuando me levanté (unas 6 horas después ya había terminado), con lo que ha tardado entre 24 y 30 horas (1 sólo núcleo 1'5Gh. el programa está en vb6, programado en NET sería bastante más rápido), pero vamos la idea de este programa no es la velocidad, si no la versatilidad de soluciones que puedo aplicarle y que cada cierto tiempo suelo ampliar.

El número de nodos visitados ha sido: 954.207.241.839 (casi 1 billón). En realidad aunque sea un número muy grande es mucho menor que todas las posibilidades que para 20 nodos (1*2*3*4*5*6*7*8*9... *19*20=  2.432.902.008.176.640.000 2'43Trillones ) .

Hay que añadir que usando fuerza bruta, todavía es posible evitar recorrer ciertos nodos por cortocircuito... para ello basta reordenar los pesos de mayor a menor... así cuanto antes una suma alcance y supere el valor menor actual, antes cortocircuita todas las derivaciones tras ese nodo. Es suficiente por tanto (para mi programa) con preparar los datos de entrada sin tocar nada del código... la desventaja en este caso es que las soluciones aparecerían 'desordenadas', aunque para lo que se pretende carece de importancia.

He aquí el resto de soluciones hasta el final...
1 ---> JDPFRCQHNTIGSBLMKEAO   6743168
1 ---> JDPRFCQHMKEAOLBSGITN   6736689
1 ---> JDPRFCQHMKEOALBSGITN   6638313
1 ---> JDPRFCQHNTIGSBLMKEAO   6614272
1 ---> JPDRFCQHNTIGSBLMKEAO   6611159 <--- Solución final mínima
1 ---> OAEKMLBSGITNHQCFRDPJ   6611159 <--- Solución final mínima
(estas dos últimas son iguales, porque el requisito era '< ó =' (interesa tener soluciones que sean iguales especialmente cuando sean la solución definitiva, si bien como se ve es el recorrido inverso... los recorridos inversos de las solucuones previas no aparecen porque antes de su tratamiento se alcanzó una solución menor).

- Revisando las soluciones se puede ver ciertas 'aglomeraciones' 'KEAO', 'GITN', 'LMBSG', etc... que van apareciendo contínuamente en cada solución con ligeras diferencias de orden. Lo que sugiere 'barriadas' de ciudades...
- Otra curiosidad es que todas las soluciones acaban (o empiezan si se considera las soluciones del revés), en unos pocos nodos específicos: O, S, J y N.

Cita de: jca1 en 12 Agosto 2021, 21:55 PM
...también incluye la necesidad o no de que sea completo el sistema; es decir que no haya conexiones entre ciudades que existan.

Sí, mi programa al operar con grafos, puedes evitar tmbiñén eso, sin tocar el código, si no solamente los datos de entrada. De hecho, 'codificar' correctamente los datos de entrada con los parámetros debidos es parte del problema, que uno debe saber resolver.

Hola.

Hice algunos cambios para adaptarlo y lo puse anoche antes de irme a dormir a calcular, sigue calculando...

Nota que el programa está diseñado para mostrar cada solución que supera el límite previo... de ahí la lista de soluciones, cada línea siguiente supera la anterior acortando la distancia.

Sin embargo al venir a poner este mensaje me doy cuenta que tu diseño es 'circular', es decir, exige que tras visitar todas las 'ciudades' vuelva al origen.
En este programa adaptado mínimamente, no está considerado dicha opción... en realidad aún siendo el mismo problema son casos distintos y es conveniente tener (en tu algoritmo), un parámetro para indicar el caso y por tanto poder solucionar ambos.
Ya sacó las soluciones (omito las previas), dando como origen el nodo 1. Introduje los datos para considerar la ruta más corta sin consierar cual es la ciudad de origen (aunque lógicamente empieza en la 1 (A) y sin considerar regreso al nodo de origen.

Aunque veas que las soluciones que presento, ofrecen una distancia menor, considera el caso donde no se exige volver al origen (pero sigue visitando todas las ciudades), tiene por lo general (sobretodo si los datos son al azar), una solución más corta y no solo por eliminar el trayecto entre la última ciudad visitada y la ciudad de origen. Ya que al exigir la vuelta, ciertos nodos en su camino son evitados para poder 'volver'... por tanto no consideres aún fallida tu solución.

Mira de ver si puedes crear otro algoritmo equivalente donde no precise volver al origen (desde tu implementación (asumo que) esto debería serte relativamente sencillo, además es algo que sí o sí debes tener igualmente resuelto).
Desde mi programa no es más complejo si me hubiera percatado de ello al inicio... pues tira de grafos y el diseño está orientado a consideraciones generales aunque luego pueda especificar ciertos detalles... que deben darse como parametro en la entrada de datos.



Nota que el número asignado a cada nodo (1-20) ha sido remplazado por una etiqueta en el rango (A-T), pues de ese modo es más cómodo representarlo al ocupar cada uno un solo carácter (dígito) y también es más fácil de una simple ojeada distinguir letras de números (de los pesos)...


01-02-03-04-05-06-07-08-09-10-11-12-13-14-15-16-17-18-19-20
A- B- C- D- E- F- G- H- I- J- K- L- M- N- O- P- Q- R- S- T

Si damos por hecho que se exige que la ciudad inicial sea la 1 (A), entonces los datos siguientes ofrencen la solución final. En realidad los datos de entrada están expuestos de tal manera, para continuar hasta que la última ciudad (nodo 20 (T)), fuere la ciudad de origen.
Soluciones (cada entrada (temporalmente la solución) supera la previa, se omiten las primeras (habría unas 50-100 soluciones temporales previas desde ABCDE...T con una distancia inicial de unos 22 millones):
...
1 ---> ABLHQCPJDRFNTIGSMKEO   8045241
1 ---> ABLKEOMHQCPJDRFNTIGS   8029724
1 ---> ABLMHQCDJPRFNTIGSKEO   7944387
1 ---> ABLMHQCPJDRFNTIGSKEO   7909997
1 ---> ABLOEKMHQCDJPRFNTIGS   7842256
1 ---> ABLOEKMHQCPJDRFNTIGS   7807866
1 ---> ABLSGITNFDJPRCQHMKEO   7771109
1 ---> ABLSGITNFRDJPCQHMKEO   7631457
1 ---> ABSGITNFDJPRCQHMLKEO   7573052
1 ---> ABSGITNFRDJPCQHMLEKO   7534083
1 ---> ABSGITNFRDJPCQHMLKEO   7433400
1 ---> AEKMHQCDJPRFNTIGSBLO   7397106
1 ---> AEKMHQCPJDRFNTIGSBLO   7362716
1 ---> AEKOLMBSGITNHQCFRDPJ   7359071
1 ---> AKEOLMBSGITNHQCFRDPJ   7346176
1 ---> ALBSGITNFRDJPCQHMKEO   7264340 <--- esta solución es la MISMA que la tuya (sin vuelta al origen):
1 ---> AOEKBLMHQCPJDRFNTIGS   7240895
1 ---> AOEKCHQMLBSGITNFRDPJ   7201363
1 ---> AOEKCQHMLBSGITNFRDJP   7150228
1 ---> AOEKCQHMLBSGITNFRDPJ   7028573
1 ---> AOEKLMBSGITNHQCFRDPJ   6991267
1 ---> AOEKMLBSGINTHQCFRDPJ   6963299
1 ---> AOEKMLBSGITNHQCFRDJP   6924025
1 ---> AOEKMLBSGITNHQCFRDPJ   6802370  <---- solución final: La ruta más corta partiendo del nodo 1, sin regreso al origen y sin especificar tampoco el nodo destino.




1 ---> ALBSGITNFRDJPCQHMKEO   7264340 <--- esta solución es la MISMA que la tuya (sin vuelta al origen): 1-12-2-19-7-9-20-14-6-18-4-10-16-3-17-8-13-11-5-15
Si a tu solución le quitamos la distancia entre las ciudades 15-1 (que es el caso que yo calculo), debería resulta lo mismo que lo que aquí aparece: 7561324 - 296984 = 7264340

Considera además que en una solución circular (como la que presentas), puedes cortar por el par de ciudades cuya distancia es mayor, al caso en tu solución circular esto sucede en los los nodos 7-9 y cuya distancia es 628171, y por tanto incluso así tendrías una solución más óptima con distancia de: 7561324 - 628171 = 6933153 ...pero como digo, sin considerar el regreso al origen hay soluciones más óptimas aún (salvo (generalmente) casos simétricos y otros que se diseñasen al efecto), que considerando el caso circular y retirar la distancia entre los nodos que determinen el origen y el final.
Si necesitas alguna demostración que lo aclare, avisas y en cuanto saque un tiempo te hago algún boceto sencillo que lo refleje y demuestre...



También nota que el algoritmo aún no ha terminado. Terminaría cuando el nodo 20 (T), fuera la ciudad de origen...
Empezando por el nodo 4 (D), aún se localizan soluciones más cortas que empezando por A.
1 ---> DJPRFCQHMKEOALBSGITN   6769839
1 ---> DJPRFCQHNTIGSBLMKEAO   6745798
...dejarlo corriendo hasta Z llevaría muchas horas más, aunque como cada vez la solución temporal es más corta, se cortocircuita antes (cuando la suma parcial de nodos visitados superan ya esa distancia temporal), por lo que a medida que se encuentran soluciones corre más deprisa y necesita visitar menos nodos... el programa cuando lo pare (o a petición), muestra la cantidad de nodos recorridos (no cuenta los no visitados si los cortocircuita).
Lo dejaré funcionando unas horas más a ver que sale...



Por último, te recomiendo que hagas también las siguientes variaciones a tu algoritmo (pongo las más genéricas que podrían pedirte):
Y exponlas como parámetro, así una función general pública recibe los parámetros de entrada y una vez claro que se quiere hacer llama a una de las siguientes funciones privadas:
* Dado un nodo de origen, visitar todos los nodos y vuelta al origen      <---- esto es lo que tienes hecho.
- Dado un nodo de origen, visitar todos los nodos, pero sin requerir vuelta al origen.  <----- esta es la solución que yo te he presentado.
- Dado un nodo de origen y otro de destino visitar todos los nodos intermedios. <--- esta opción suele arrojar presumiblemente (obvio), una solución con mayor distancia que la previa, pero a menudo el origen y el destino están prefijados, luego debe considerarse).
- Hallar la distancia menor sin considerar un nodo de origen ni de destino <---- Esto es lo que está haciendo mi programa (mientras no lo pare). Esto suele requerirse cuando una operación ha de repetirse millones de veces, y entonces poder elegir la ruta más corta es lo óptimo cuando el acceso a un nodo de origen y de destino es indiferente... (suele ser el caso por ejemplo de muchas máquinas CNC, para dibujado, corte, soldadura, fabricación de microchips, etc...).

Lo aconsejable es que sea la que sea la dirección en que se avance, es que los cambios a efectuar permitan a futuro otros cambios y no que los de ahora vinieren a suponer luego un lastre para seguir 'evolucionando'.

En ese sentido cuanto menos dependiente de 'algo' más libertad te deja... por otro lado, la comodidad de 'depender' de algo ya hecho elimina la complicación de aplicar cambios al precio de esa dependencia que lastra para cambios a futuro. Lo idela sería pues encontrar algo en un punto intermedio, algo que resuelva lo fundamental con las bases de datos y que al mismo tiempo tolere la libertad de ciertos cambios en la estética sin que rompa con el sistema elegido.

Simple Machines, así como Ip.Board, vBulletin, phpBB y otros tantos, no han evolucionado demasiado con los tiempos... Pero me pregunto si no habría alguno que haya escapado a esa dinámica y que pudiera facilitar todos o por lo menos una gran parte de la intencionalidad esperada.
https://en.wikipedia.org/wiki/Category:Virtual_communities
https://en.wikipedia.org/wiki/Category:Internet_forums
https://en.wikipedia.org/wiki/Category:Bulletin_board_systems

En sus tiempos, recuerdo un board altamente complejo (al menos en la apariencia con la primera impresión) y altamente configurable, que permitía casi toda clase de control incluso wiki, RSS, juegos, calendario... lástima que no recuerde su nombre, aunque en algún disco duro debo tener copia del mismo, pués me lo descargué para instalarlo en local y probar.

El textbox tiene su propiedad alineacion...
Ahora bien, me parece que tu quieres mantener una alineación 'múltiple' al mismo tiempo, tal cual aparece en los chats...

No has aclarado como debe aparecer verticalmente, es decir si el 'append' se realiza debajo de lo previo (quedando último mensaje abajo) o encima d elo previo (quedando lo último arriba dle todo).
Normalmente queda abajo, pero requiere scroll por parte del usuario. El caso es que esto debe queda claro antes de nada para desarrollar un sistema y no el otro.

Esto se puede hacer de varias maneras:
- Mantener 2 controles, uno alineado a la derecha y otro a la izquierda, ambos deberían mantener un aspecto transparente de modo que uno no tape al otro, si no que los textos se solapen como si estuvieran en la misma área. La complicación aquí es mantener la verticalidad , un mensaje debado de otro. Esto se logra fácil y chapuceramente manteniendo sendos controles otro oculto, donde se pega primero y se contabilida las líneas que ocupa, luego al texto a pegas hay que endosarle dichos saltos de línea (tantos como líneas).

- Mantener 1 solo control. Eliges una alineación (por ejemplo izquierda), cuando pegas el texto a izquierda no tienes nada más que hacer, pero cuando pegas el texto alineado a la derecha, debes calcular el espacio a añadir a la izquierda. Como consejo, se puede simplificar los cálculos si eliges una fuente monoespaciada (todos los caracteres tienen le mismo ancho), luego sabiendo el ancho del textbox, sabes cuantos caracteres caben en una línea. A la noche si estás interesado y saco un tiempito te pongo un sencillo pseudocódigo para esto...

- Mantener 2 controles ocultos cada uno con su alineación. El textbox donde se ve la imagen en realidad sería ahora un control de imagen. Tú pegas el texto en cada control oculto (que además tienen el mismo ancho que el control de imagen), y luego recortas (copias) el gráfico generado en el textbox de turno, y lo pegas en el control de imagen. Si tiene un fondo este control el pegado debe ser con transparencias y para ello el fondo de los textbox deben ser del color a enmascarar en el control de imagen.

En cualquier caso, date cuenta que si el control donde se expone al usuario es modificable (el menos en ancho), cada vez que se modifique dicho ancho requiere volver a renderizar todo su contenido, por lo que para que sea efectivo, todo el texto debe irse guardando en un fichero, diferenciando lo que se alinea a un lado de lo que se alinea al otro...

Ejemplo
Como se guarda en el fichero:
Pedro:
Hola Juan, que harás esta noche?. Podríamos ir al cine...
Juan:
Hola Pedro, tengo toda la noche ocupada

Como se ve en la interfaz:

--------------------------------------------
Pedro:
Hola Juan, que harás esta noche?. Podríamos 
ir al cine...
                                      Juan:
                Hola Pedro, tengo toda la no
                                che ocupada
--------------------------------------------

'Pedro:' y 'Juan:' (+ solo el salto de línea), hacen en el ejemplo el identificador de alineación en el fichero...

Citar
Aca te mando un tabla donde la primer columna es la distancia, en la segunda una de las ciudades y la tercera es la otra ciudad que une.

Ese sistema es muy laaaaaargo de definir y sobretodo de interpretar al programarlo, pues va a requerir rellenar huecos...

Citar
623939   1   2
1341230   1   3
1652150   1   4
354682   1   5
...

No es necesario que me lo mandes por privado, son simplemente datos, cifras, nada que requiera discrección, de hecho si se deja público puede que alguien más se anime a hacer un cálculo por su cuenta... o pruebe con su propia solución... y te dé 'su solución'.

Una tabla es sencilla de hacer.... te paso un dibujo de ejemplo, pero tú debes anotarlo en un fichero de texto, que luego yo pueda leer desde el programa para cargar los datos... meterlo manualmente tiene el riesgo de error en la introducción de datos, aparte de lo tedioso de la introducción manual que supone cuando los datos son varios.

Un ejemplo y te comento brevemente:

Cada número supone el nodo enésimo representado por el número en su fila o columna. Nota que los números de fila y columna en la imagen están solo por claridad, en el fichero es preferible omitirlos, su orden de ubicación lo representa y es suficiente, si no, exige filtrarlo.

Cada fila representa un nodo (ciudad por ejemplo), y a su derecha se señala la distancia que hay de él a cada uno de los nodo bajo cuya columna se ubica.
En la imagen se observa que solo he rellenado las distancias que parten del nodo 4 al resto de nodos: Al nodo 1 hay una distancia de 15, al nodo 2 una distancia de 22, al nodo 3 una distancia de 36, al nodo 4 (a sí mismo), una distancia de 0 (pero que he marcado como 'x', todos los nodos a sí mismo tienen igual valor representan la violación de pasar 2 veces por él mismo...), al nodo 5 hay una distancia de 81, al nodo 6 de 54... ...y finalmente al nodo 13 de 61.

Como ves cada nodo ocupa una fila, lo que se traduce en el fichero de texto como una línea de texto, al final de la misma un salto de línea (no te preocupes si tu sistema exige salto de línea y avance de carro, o solo uno de dichos caracteres (diferencias entre win2, mac y Linux) ya lo determino yo mismo al cargar el fichero al programa).
Separa la distancia entre nodos en el fichero con un simple espacio (no te preocupes si en alguno pusiste 2 o más espacios, se filtrarán)...

Al final guarda el fichero, verifica que esté correctamente editado, lo comprimes en zip (para evitar que sea manipulado), lo subes a una página de descarga y publicas el enlace.

Si el texto fuera muy pequeño (pongamos 10-20 nodos), y las líneas no muy largas puedes copiar el texto una vez completo el fichero y pegarlo directamente aquí en el foro entre etiquetas code...
Si las líneas son muy largas, incluso las etiquetas code pueden forzar saltos de línea, cuando una línea exceda x tamaño de longitud, aunque supongo que con etiquetas code el tamaño de línea será más generoso (que con eqtiquetas quote o que sin etiquetas).
...si se cortan automáticamente las líneas, falsea la interpretación de los datos a la hora de leerlos con un programa que entiende que los datos de un nodo están en una línea.
Si a pesar de todo las líneas fueran tan largas, que quedaren cortadas, entonces es preferible subir el fichero a alguna página de descargas y poner enlace y listo.

Con el ejemplo de la imagen, el fichero se vería así (nota que como solo he rellenado la fila 4, debe suponerse 3 filas por delante, y muchas más por detrás).
...
15 22 36 x 81 54 21 7 13 103 84 52 20 61
...

Yo haría lo último que señalas... una cola de salida y otra de entrada.

Debes cuidar la cola de salida... para que no se envíen más peticiones por unidad de tiempo de las que está capacitado a recibir, ya que el puerto serie tiene sus limitaciones. Un temporizador que se  encargue de ver si tiene salidas pendientes, y si las hay enviar la primera en curso y si se espera una devolución asignarle un id y pasarlo a la cola de entrada, que cuando sea despachado del dispositivo (con el mismo id), se envía a la cola de entrada (devolución) que seguramente podrá actuar a una mejor velocidad, y una vez servida borrar de esta cola.

Con ambas colas evitas la necesidad del bloqueo que seguramente te haga perder notificaciones.

Es importante que recabes las especificaciones del puerto serie, para aprovecharlo al máximo... no saturarlo ni tampoco dejarlo inactivo y que caiga su eficiencia por debajo de sus capacidades.

No sé vosotros, pero yo desde hace muchos, muchos años, recibo en mi router (PC) peticiones de IPs chinas... constantemente. Ahora es más difícil rastrear el origen pero entonces (muchos años atrás), era más simple, no había tanta intencionalidad de ocultar el origen.

A menudo basta prender el PC y abrir la red, bloquear todas las peticiones de red salientes y solo esperar, y llegan peticiones.

Es algo más que sabido que China espía a todo el mundo por internet, da igual qué equipo tengas, da igual que programas tengas o no tengas, parece ser algo sistemático...

Cita de: inma55 en  8 Agosto 2021, 13:30 PM
A la hora de almacenar informacion,¿todo se reduce a celdas con dos estados posibles?
Es decir,hay muchos tipos de celdas,pero al final en todos hay dos estados posibles,no?

¿se podria hacer una clasificacion de los tipos de celda? Deduzco que habrá varios criterios para hacer una clasificacion,habrá carios subtipos...

¿se podria hacer un intento?

Me salen 3 tipos:

Las celdas de la SRAM
Las celdas de la DRAM
Las celdas de los flipflops (biestables)

¿esas son las 3 grandes tipologicas de celda? Comentad y desarrollad mi "boceto".
MUCHAS GRACIAS

Las memorias son todo un mundo.
Sin embargo no debes confundir la tecnología de implementación con la teoría subyacente en las memorias.
Léete antes el hilo en wikipedia que te han citado, para aclarar ideas...

De entrada el biestable es la unidad básica de memoria... Luego es superado por diseños más 'costosos', por ejemplo el flip-flop JK, D, etc... antes del transistor de chip, se hacían con mallas poniendo toros de ferrita en las uniones, la fila y columna identificaban unívocamente cada bit, y con las líneas de Set o Reset se cambiada el estado.
https://www.electronics-tutorials.ws/sequential/seq_2.html

Nota que una cosa es la teoría y otra la tecnología... la tecnología es más barata cuando todos los circuitos combinacionales se hacen de un mismo tipo de puerta (puerta lógica), para realizar un chip... típicamente puertas NAND, incluso NOR, esto puede cambiar también con el desarrollo de nuevos materiales...
Así que la teoría es bueno estudiarla conforme a la simplicidad, considerando transistores. De ahí no será complicado saltar a las puertas para entender los circuitos combinacionales... Y cuando te resulte asequible entenderlo, luego avanza hacia los diseños de implementación en la tecnología de frabricación. Pero nota que éstas dependen mucho de la cuestión económica... elegir un material o un tipo de diseño suelen obedeces a cuestiones económica, sean monetarias o de características (que suelen influir finalmente en las económicas, salvo desarrollos teóricos de futuro en la investigación).

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.