elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor  (Leído 2,214 veces)
painkillerpucela

Desconectado Desconectado

Mensajes: 23


Ver Perfil
Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor
« 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!


En línea

Oblivi0n


Desconectado Desconectado

Mensajes: 392

Odio las ranas.


Ver Perfil
Re: Duda algoritmo búsqueda primero en anchura y búsqueda primero el mejor
« Respuesta #1 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 ), vamos, que la única manera de hacerlo sin debanarse mucho los sesos es hacer fuerza bruta sobre el grafo, probando TODOS los caminos posibles


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Google vuelve a cambiar el algoritmo de búsqueda
Noticias
wolfbcn 0 1,156 Último mensaje 3 Noviembre 2011, 21:26 pm
por wolfbcn
Duda sobre el algoritmo de busqueda de Google
Desarrollo Web
crazykenny 5 2,027 Último mensaje 18 Enero 2013, 19:07 pm
por el-brujo
Contratar indigentes para ser el primero en conseguir el nuevo iPhone
Noticias
wolfbcn 0 1,096 Último mensaje 23 Septiembre 2013, 01:56 am
por wolfbcn
Algoritmo A* , Busqueda en Profundidad y Busqueda en Anchura
Java
HackingLikor 0 1,484 Último mensaje 4 Mayo 2016, 01:08 am
por HackingLikor
Primero en Entrar, primero en salir FIFO, Cola o Fila
Programación C/C++
AlbertoBSD 9 1,258 Último mensaje 3 Diciembre 2018, 00:01 am
por CalgaryCorpus
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines