|
Título: Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor Publicado por: painkillerpucela en 19 Noviembre 2012, 19:50 pm Buenas a todos!! Estoy implementando estos dos algoritmos para resolver el mítico problema del viajante. Para resolver el problema tengo dos listas una con nodos cerrados (ciudades ya visitadas) y otro con nodos abiertos. Os quería preguntar si en la lista de nodos abiertos puede haber nodos repetidos o no.
Un saludo! Título: Re: Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor Publicado por: Oblivi0n en 20 Noviembre 2012, 13:37 pm Para resolver el problema del viajante te sería mas optimo lo siguiente :
1) Almacenar pesos de los caminos entre nodos ( ciudades ) en una matriz, y una matriz de adyacencias , y aplicar el algoritmo de kruskal y haciendole unas pequeñas modificaciones ( ya que kruskal realmente da el arbol generador minimo, ergo no volverías nunca a la ciudad ), consegurías un camino, pero no te va a garantizar que este sea minimo. 2) La solución existente que hay del problema, es NP-COMPLETO ( http://es.wikipedia.org/wiki/NP-completo (http://es.wikipedia.org/wiki/NP-completo) ), vamos, que la única manera de hacerlo sin debanarse mucho los sesos es hacer fuerza bruta sobre el grafo, probando TODOS los caminos posibles |