🚀 go-pugleaf

Hola Francisco.

No he encontrado ningun algoritmo en los libros b�sicos de Investigaci�n
Operativa ni de Grafos que poseo, s�lo en: "The Traveling Salesman Problem".
Editado por Wiley&Sons (1985). Si haces una b�squeda por internet buscando
procedimientos de Branch & Cut para el viajante del comercio encontrar�s algo
(busca por TSP y "Subtour Elimination Constraints"). El problema es el mismo que
t� describes pero en otro ambiente (para resolver el viajante de comercio con
programaci�n lineal entera es necesario ir a�adiendo restricciones que eviten
subciclos en la soluci�n, ya que la soluci�n del TSP siempre es un �nico ciclo,
como el n�mero de restricciones que evitan subciclos es enorme, se resuelve el
problema sin ellas y se van a�adiendo poco a poco, se hacen m�s cosas, pero esto
no interesa aqu�). En Concorde debes buscar tambi�n notas que referencien al
t�rmino antes citado (lo siento, no puedo decirte d�nde est� el algoritmo porque
Concorde como t� bien has dicho es un mastodonte con c�digo mal documentado).
Igualmente como soluci�n r�pida haz la prueba que te coment� en el post
anterior. Cambia en la matriz de adjacencia los 1 por -1 y corre un algoritmo de
caminos m�nimos entre toda pareja de v�rtices (esto s� puedes encontrarlo por
doquier). Si hay suciclos el algoritmo no finalizar� (porque el camino m�nimo
entre una pareja de �tomos formantes de un suciclo tender� a menos infinito).
Cuando lleves un buen n�mero de iteraciones, todas aquellas parejas que tengan
valores por encima de una cota (n�mero total de �tomos del problema) formar�n
parte de un subciclo.

    Jordi

Francisco de Asis Tarancon Jodral wrote:

> En primer lugar, me gustaria agradecer tanto a Jordi como a Andres su
> inestimable ayuda.
> No estoy seguro de haber dejado claro lo que intento hacer, asi que me
> gustaria explicarlo otra vez.
> Antes no comente de que parto de una matriz de adyacencias, esta matriz de
> adyacencia representa a un compuesto quimico, posteriormente debo de extraer
> de esa matriz de adyacencia, todos aquellos atomos que formen ciclo, y
> guardar dicho ciclo, asi con todos los ciclos que haya, tambien he de
> extraer aquellos atomos que no formen ciclo, pero claro, esos atomos, serian
> los restantes de extraer los atomos que forman los ciclos, por eso no me
> preocupa mucho.
> Creo que eso es lo que deberia de haber explicao anteriormente, lo que me
> gustaria es si alguien sabe de algun sitio donde este ese algoritmo.
>
> Jordi, muchas gracias por enviarme a lo del Concorde, le estoy hechando un
> vistazo y parece que tiene bastante documentacion, pero por desgracia, no
> hay ni un solo comentario en el codigo que te explique que va haciendo, y no
> tengo mucho tiempo para ponerme a "descifrar" tanto codigo, pero muchisimas
> gracias.
>
> Andres, gracias por tu documento pdf, le he hechao un vistazo y parece
> interesante, pero tengo que leerlo mu detenidamente por que mi ingles.... no
> es que sea mi fuerte, pero voy a leerlo.
>
> Gracias a los dos, y a todo aquel que pueda ayudarme.
>
> Un saludo