Hola, soy un alumno de informática al que se le ha ocurrido una teoría y me gustaría que me dijerais si estoy en lo cierto.
En el algoritmo de búsqueda en anchura, por ejemplo este:
FUNCION BUSQUEDA-EN-ANCHURA()
1. Hacer ABIERTOS la cola formada por el nodo inicial (es decir, el nodo
cuyo estado es *ESTADO-INICIAL* y cuyo camino es vacío);
Hacer CERRADOS vacío
2. Mientras que ABIERTOS no este vacía,
2.1 Hacer ACTUAL el primer nodo de ABIERTOS
2.2 Hacer ABIERTOS el resto de ABIERTOS
2.3 Poner el nodo ACTUAL en CERRADOS.
2.4 Si ES-ESTADO-FINAL(ESTADO(ACTUAL)),
2.4.1 devolver el nodo ACTUAL y terminar.
2.4.2 en caso contrario,
2.4.2.1 Hacer NUEVOS-SUCESORES la lista de nodos de SUCESORES(ACTUAL)
cuyo estado no está ni en ABIERTOS ni en CERRADOS
2.4.2.2 Hacer ABIERTOS el resultado de incluir
NUEVOS-SUCESORES al final de ABIERTOS
3. Devolver FALLO.
FUNCION SUCESOR(NODO,OPERADOR)
1. Hacer ESTADO-SUCESOR igual a APLICA(OPERADOR,ESTADO(NODO))
2. Si ESTADO-SUCESOR=NO-APLICABLE
devolver NO-APLICABLE
en caso contrario,
devolver un nodo cuyo estado es ESTADO-SUCESOR y cuyo camino
es el resultado de añadir OPERADOR a CAMINO(NODO)
FUNCION SUCESORES(NODO)
1. Hacer SUCESORES vacío
2. Para cada OPERADOR en *OPERADORES*,
si SUCESOR(NODO,OPERADOR) =/= NO-APLICABLE,
incluir SUCESOR(NODO,OPERADOR) en SUCESORES
3. Devolver SUCESORES
Según tengo entendido, cuando hacemos una búsqueda en anchura en un grafo cuyos arcos son todos bidireccionales y tienen el mismo coste, cada nodo "actual" posee una longitud de camino mínima. Cuando generamos sus sucesores, comprobamos si ese sucesor ya había sido explorado anteriormente, o lo que es lo mismo, comprobamos si se encuentra en el conjunto "cerrados".
Mi duda es, para cada sucesor, ¿Es cierto que no podría existir en el conjunto de los nodos cerrados un nodo con el mismo estado y una cuya longitud sea la misma que el sucesor menos 2?
Lo que me lleva a pensar esto es que si existiera tal nodo, significaría que existe un camino entre el nodo que se encuentra en cerrados y el nodo actual (al que le habíamos generado los sucesores) por lo tanto existiría un camino con una longitud menor que la que ya habíamos calculado.
Si mi teoría es correcta me vendría muy bien para optimizar una búsqueda que tengo que hacer para un trabajo de la universidad, ya que en vez de buscar si los sucesores se encuentran en abiertos y cerrados, solo tendría que buscar entre los nodos abiertos y los nodos en cerrados a distancia máxima 2 del nodo actual.
Un saludo, y gracias por adelantado por la contestación
