Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor

[painkillerpucela]

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!

[Oblivi0n]

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 ), vamos, que la única manera de hacerlo sin debanarse mucho los sesos es hacer fuerza bruta sobre el grafo, probando TODOS los caminos posibles