trabajo final grafos

Inteligencia ArtificialTrabajo de InvestigaciónGrafos

GRAFOS

Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos.El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A,C), (C, D), (C, F), para el siguiente grafo.

Si los pares de nodos en los arcos dirigidostienen una dirección definida, el grafo se denomina grafo directo, dirigido odígrafo.

TERMINOLOGÍA

Al número de nodos del grafo se le llama orden del grafo. Un grafo nulo es un grafo de orden 0. Dos nodos son adyacentes si hay un arco que los une. En un grafo dirigido, si A es adyacente de B, no necesariamente B es

adyacente de A. Camino es una secuencia de uno o más arcos que conectan dos nodos. Un grafo se denomina conectado cuando existe siempre un camino que une

dos. nodos cualesquiera y desconectado en caso contrario. Un grafo es completo cuando cada nodo esta conectado con todos y cada

uno de losnodos restantes. El camino de un nodo así mismo se llama ciclo.

Página 1


Matriz de adyacencia

Un grafo sin ciclos es un árbol. El entregado de un nodo indica el número de arcos que llegan a se nodo. El fuera de grado de un nodo indica el número de arcos que salen de él. Un grafo de N vértices o nodos es un árbol si cumple las siguientes

condiciones

a) Tiene N-1 arcosb) Existe una trayectoria entre cada par de nodos.c) Esta mínimamente conectado.

Un grafo esta etiquetado si sus arcos tiene valores asignados.- Si este valor es numérico se dice que el grafo tiene peso.

Página 2


GRAFOS Y SUS APLICACIONES

Terminología de teoría de grafos:Esta sección recoge alguna de la terminología principal asociada con la teoría de grafos.

Podemos clasificar los grafos en 2 tipos básicos, dirigidos y no dirigidos.

1. Los grafos dirigidos están formados por vértices y arcos. Los arcos son pares ordenados de vértices, es decir, A -> B, el vértice A es el primero y B el segundo, y esta unidos por un arco que marca el orden.

2. Los grafos no dirigidos están formados por vértices y aristas, que son pares de vértices no ordenados, al contrario que pasa con los arcos.

3. Podemos asociar un grafo no dirigido a uno dirigido si ignoramos la dirección de los arcos y siempre que tengan en mismo conjunto de vértices.

4. Un grafo mixto es aquel que contiene tanto arcos como aristas.

5. Los extremos de una arista o arco (los vértices) se dice que sonincidentes con la arista o arco.

Los vértices A y B son incidentes con la arista e1.

6. Dos vértices que comparten una misma arista o arco, es decir, que sonincidentes con esta, se dice que son adyacentes el uno con el otro.

Página 3

http://blogs.ua.es/matematicadiscrecion/files/2010/11/dirigido.png

http://blogs.ua.es/matematicadiscrecion/files/2010/11/nodir.png

http://blogs.ua.es/matematicadiscrecion/files/2010/11/inci.png


Los vértices A y B son adyacentes.

7. Un bucle es una arista o arco cuyos extremos son el mismo vértice.

El vértice 1 tiene un bucle.

TIPOS PARTICULARES DE GRAFOS:

1. Un grafo simple es un grafo sin bucles y en el que no hay dos aristas que unan el mismo par de vértices. Si el grafo es dirigido diremos que es simple si no tiene bucles y no hay dos arcos uniendo el mismo par de vértices y con la misma dirección.

Cuando un grafo NO es simple, se le llama multigrafo.

Grafo simple

Multigrafo

Página 4

http://blogs.ua.es/matematicadiscrecion/files/2010/11/inci.png

http://blogs.ua.es/matematicadiscrecion/files/2010/11/dirigido.png

http://blogs.ua.es/matematicadiscrecion/files/2010/11/simple.jpg

http://blogs.ua.es/matematicadiscrecion/files/2010/11/lazo.jpg


Multigrafo

2. Un grafo se dice que es completo si hay al menos una arista o arco uniendo cada par de vértices distintos. A un grafo no dirigido y simple lo denominamos Kn.

Grafo completo K6

3. Un grafo no dirigido diremos que es bipartito si existe una partición {X, Y} del conjunto de vértices de forma que toda arista tiene un extremos en X y otro en Y.Para los grafos dirigidos diremos que es bipartito si lo es su grafo no dirigido asociado.

Página 5

http://blogs.ua.es/matematicadiscrecion/files/2010/11/lazo.jpg

http://blogs.ua.es/matematicadiscrecion/files/2010/11/k6completo07.gif


V1={A,B,C,D,E}, V2={F,G,H,I}

TEOREMA

1. Sea G=(V,A) un grafo, entonces:

2. Sea G=(V,A) un grafo dirigido, entonces:

COROLARIOEl número de vértices de grado impar de un grafo es par.

Grafos y multigrafos

Un grafo “G” consiste en dos cosas:

a) Un conjunto V de elementos llamados nodos (o puntos o vértices)b) Un conjunto E de aristas tales que cada arista e de E esta identificada por un

único (desordenado) par [u,v] de nodos de V, denotado por e-[v,u].

A veces denotamos un grafo escribiendo G= (V, E)

Página 6

http://blogs.ua.es/matematicadiscrecion/files/2010/11/Simple-bipartite-graph.png

http://blogs.ua.es/matematicadiscrecion/files/2010/11/1.png

http://blogs.ua.es/matematicadiscrecion/files/2010/11/2.png


Suponga que e = [u, v], entonces los nodos u y v se llaman extremos de e, u y v se diceque son nodos adyacentes o vecinos. El grado de un nodo u, escrito grad (u), es el número de artistas que contienen a u.

Si grad(u)= 0, o sea, si u no pertenece a ninguna arista, entonces se dice que u es un nodo aislado.Un camino P de longitud n desde un nodo u se define comola secuencia de n +1 nodos.

Tal que u =v0i, v1, es adyacente a vi-1 para i=1,2,…n; y vn=v. El camino P se dice que escerrado si v0 =vn .El camino P se dice que es simple si todos los nodos son distintos, aexcepción de v0 que puede ser igual a vn; es decir, P es simple si los nodos v0, v1……….vn-1…son distintos y los nodos v1, v2……….vn son distintos. Un ciclo es un camino simple cerradode longitud 3 o más. Un ciclo de longitud k se llama k-ciclo.Un grafo G se dice que es conexo si existe un camino entre cualesquiera dos de sus nodos.

Mostraremos en el problema 8.18 que si existe un camino P desde un nodo u a un nodo v, entonces eliminando las aristas innecesarias, se puede obtener un camino simple Q de ua v, de acuerdo con esto podemos establecer la siguiente proposición.

Proposición1 :Un grafo G es conexo si y sólo si existe un camino simple entre cualquiera de los nodos de G.Se dice que un grafo G es completo si cada nodo u de G es adyacente a todos los demásnodos de G claramente, un grafo así es conexo, un grafo completo de n nodos tendrá n(n-1)2 aristas.

Un grafo conexo T sin ciclos se llama grafo árbol o árbol libre o simplemente árbol. Estosignifica en particular, que existe un único camino simple P entre cada dos nodos uye deT mas aún, si T es un árbol finito de m nodos, entonces T tendrá(m -1) aristas.

Un grafo G se dice que esta etiquetado si sus aristas tiene datos asignados. En particular se dice que G tiene peso si cada arista e de G tiene asignado un valor numérico nonegativo w (e) llamado peso o longitud de e. En ese caso, a cada camino P de G se leasigna un peso o una longitud que es la suma de lo pesos de las aristas que constituyen el camino P, si no se da otra información sobre pesos, asumiremos que cada grafo G tienepeso pero de forma que los pesos w (e) de cada arista e de G es igual a 1.

La definición de un grafo puede ser generalizada si permitimos lo siguiente:

1) Aristas múltiples: Dos aristas e y e distintas se llama aristas múltiples si conectan losmismos extremos, o sea, si e [u, v] y e= [u, v].

Página 7


2) Bucles. Una arista ese llama bucle si tiene extremos idénticos, o sea, si e = [u, v].

Tal generalización M se llama multígrafo. En otras palabras la definición de un grafonormalmente no permite ni aristas múltiples ni bucles.

Un multígrafoM se dice que es finito si tiene un número finito de nodos y de aristas.Observe que un grafo G con un número finito de nodos debe tener automáticamente un númerofinito de aristas; pero esto no es necesariamente cierto para unmultigrafo M, ya que M puede tener múltiples aristas. A menos que se indique locontrario, los grafos y multigrafos de este texto serán finitos.

Ejemplo 1

(a) La figura 1(a) es un dibujo de un grafo conexo con cinco nodos—A,B,C,D y E— yseis aristas ;[A,B],[B,C], [C,D],[D,E], [A,E], [C,E], [A,C]Hay dos caminos simples de longitud 2 entre B y E; (B, A, E) y (B, C, E). Hay un solocamino simple de longitud dos desde B hasta D:(B, C, D). Anotamos que (B, A, D) no es un camino, ya que [A, D] no es una arista.

Hay dos 4-ciclos en el grafo:[A, B, C, E, A] y [A, C, D, E, A]Note que grad(A)=3, ya que A pertenece a tres aristas. Similarmente, grad(C)=4 y grad (D)=2.

(b)La figura 1(b) no es un grafo sino un multigrafo. La razón es que tiene aristasmúltiples ------>ei= [B, C] y e5= [B, C] --- y tiene un bucle e6=[D, D]. La definición deun grafo normalmente no permite aristas múltiples ni bucles.

(c) La figura 1(c) es un grafo árbol con m=6 nodos y, consecuentemente, m-1=5 aristas. Se puede verificar que hay un único camino simple entre cada dos nodos delgrafo árbol.

(d) La figura 1(d) es el mismo grafo que la figura 8-1(a), excepto que ahora el grafo tiene peso.Observe que P1=(B, C, D) y P2=(B, A, E, D) son ambos caminos del nodoB al nodo D. Sin embargo, aunque P2 contiene mas aristas que P1 el peso w(P2)=9 esmenor que el peso w(P1)=10.

Página 8


Figura 1

Grafos dirigidosUn grafo dirigido G, también llamado dígrafo o grafo, es lo mismo que un multigrafo, soloque cada arista e de G tiene una dirección asignada o, en otras palabras, cada arista e estáidentificada por un par ordenado (u, v) de nodos G en vez del par desordenado [u.v].Suponga que G es un grafo dirigido con una arista dirigida e=(u,v).Entonces e también sellama arco. Más aún se usa la siguiente terminología:

1) e empieza en u y termina en v2) u es el origen o punto inicial de e,y v es el destino o punto terminal de e .3) u es un predecesor de v y v es un sucesor o vecino de u4) u es adyacente hacia v y v es adyacente a u

El grado de salida de un nodo u de G, escrito gradsal (u), es el número de aristas queempiezan en u similarmente, el grado de entrada u, escrito gradent (u), es el número dearistas que terminan en u. Un nodo u se llama fuente si tiene un grado de salida positivo yun grado de entrada nulo. Similarmente u se le llama sumidero si tiene un grado de salidanulo y un grado de entrada positivo.

Las nociones de camino, camino simple y ciclo se aplican en los grafos dirigidos igual que en los grafos no dirigidos excepto que la dirección de cada arista de un camino (ciclo) debe coincidir con la dirección del camino (ciclo). Se dice que un nodo v es alcanzable desde un nodo u si existe un camino (dirigido) de u a v.

Un grafo dirigido G se dice que es conexo, o fuertemente conexo, si para cada par u,v de nodos de G existe un camino de u a v y también un camino de v a u. Por otro lado, G se dice que es unilateralmente conexo para cada par u,v de nodos de G hay un camino de u a v o un camino de v a u.

Página 9


Ejemplo 2 La figura 2 muestra un grafo dirigido G con cuatro nodos y siete aristas (dirigidas).Las aristas e2 y e3 se dice que son paralelas, ya que las dos empiezan en B y terminan en A.La arista e7-es un bucle, ya que empieza y termina en el mismo nodo B.

La secuencia P1=(D, C, B, A), no es un camino ya que (C, B) no es una arista o sea, la dirección de la arista e5=(B, C) no concuerda con la dirección del camino P1. Por otro lado P2=(D, B, A) es uncamino de D a A, ya que (D, B) y (B, A) son aristas .Así A es alcanzable desde D. No existe camino entre C y el resto de los nodos, así que G no es fuertemente conexo.

Sin embargo G es unilateralmente conexo. Observe que gradent(D)=1 y gradsal(D)=2. El nodo C es un sumidero, ya que gradent(C)=2 y gradsal(C)=0. Ningún nodo G es una fuente

Figura 2

Sea T un grafo árbol no vacío. Suponga que elegimos un nodo R de T. Así T con ese nodo R designado se llama árbol con raíz y R se llama su raíz. Recuerde que existe un único camino simple desde la raíz R hasta cualquier otro nodo de T. Esto define una dirección para las aristas de T, así que el árbol con raíz puede ser visto como un grafo dirigido. Más aún suponga que también ordenamos los sucesores de cada nodo v de T. Entonces T se llama árbol con raíz ordenado. Los árboles con raíz ordenados no son otra cosa que los árboles generales.

Un grafo dirigido G se dice que es simple si no tiene aristas paralelas. Un grafo simple G puede tener bucles, pero no puede tener mas de un bucle en un nodo dado. Un grafo G no dirigido puede verse como un grafo dirigido simple asumiendo que cada arista [u,v] de G representa dos aristas dirigidas (u,v) y (v.u). (Observe que usamos la notación (u,v) para denotar un par ordenado).

Página 10


2.-Representacion secuencial de grafos:

Matriz de adyacencia matriz de caminos

Existen dos formas estándar de mantener un grafo G en la memoria de una computadora. Una forma llamada presentación secuencial de G, se basa en la matriz de adyacencia de A.

La otra forma, llamada representación enlazada de G, se basa en las listas enlazadas de vecinos. Esta sección cubre la primera representación y muestra como se puede usar la matriz de adyacencia A de G para responder fácilmente ciertas cuestiones sobre conectividad de G.

Independientemente de la forma que se mantenga el grafo G en la memoria de la computadora, el grafo G normalmente se introduce en la computadora por su definición formal: un conjunto de nodos y un conjunto de aristas.

Matriz de adyacencia

Suponga que G es un grafo dirigido simple de m nodos y suponga que los nodos de G han sido ordenados y llamados v1, v2…vm .Así la matriz de adyacencia A=(ai,j) del grafo G es la matriz de m x m elementos definida como sigue:

Una matriz A así, que contiene entradas de 0y1, se llama matriz de bits o matriz booleana. La matriz de adyacencia de A del grafo G depende de la ordenación de los nodos de G; esto es, diferentes ordenaciones de los nodos pueden resultar en diferentes matrices de adyacencia. Sin embargo las matrices obtenidas por dos ordenaciones diferentes están fuertemente relacionadas en cuanto que a una puede ser obtenida de la otra simplemente cambiando filas y columnas. A menos que se indique lo contrario asumiremos que los nodos de nuestro grafo G tienen un orden fijo.

Suponga que G es un grafo no dirigido. Entonces la matriz de adyacencia de G, A será una matriz simétrica, o sea, con a(i,j)= a(j,i) para cada i y j . Esto viene del hecho de que cada arista no dirigida [u,v] corresponde a las dos aristas dirigidas (u,v),(v,u).

La anterior representación matricial de un grafo se puede extender a multigrafos.Específicamente, si G es un multigrafo, entonces la matriz de adyacencia de G es la matriz A de m x m= a (i, j) definida haciendo a (i, j) igual al numero de aristas desde vi hasta vj.

Página 11


Considere el grafo G de la figura 3, Suponga que los nodos se guardan en memoria en un array lineal Datos tal como sigue:

DATOS: X, Y, Z, W

Asumimos que el orden de los nodos de G es el siguiente v1=X, v2=Y, v3=Z y va=W. La matriz de adyacencia de A de G es la siguiente:

Observe que el número 1 en A es igual al número de aristas en G.

.Figura 3

Considere las potencias A, A (1), A (2), A (3),… de la matriz de adyacencia de A de un grafo G. Sea a1(i,j)=la entrada i j de la matriz A(M) potencia.

Observe que a1(i,j)=a(i,j) da el numero de caminos de longitud 1 desde el nodo v1 hasta el nodo v3 . Se puede demostrar que a2 (i,j) da el numero de caminos de longitud 2 desde v1,hasta v3. De hecho, en el problema 8.19 probaremos el siguiente resultado general.

Proposición 2 Sea A la matriz de adyacencia de un grafo G de la figura3. Entonces ak (i,j), la entrada ij en la matriz , ak da el número de caminos de longitud k desde v1 hasta v3.

Considere el nuevo grafo G de la figura3 cuya matriz de adyacencia A se da en el ejemplo 3. Las potencias A(2),A(3), A(4),… de la matriz A son las siguientes.

Así en particular, hay un camino de longitud 2 de v4 a v1, hay dos caminos de longitud 3 de v2 a v3 y hay 3 caminos de longitud 4 de v2 a v4 (Aquí, v1=X, v2=Y, v3=Z y v4=W)

Página 12


Suponga que ahora definimos la matriz B como sigue:

B =r A+A2 +A3 +....+Ar

Entonces la entrada ij de la matriz B, da el número de caminos de longitud r o menor, del nodo vi al vj.

Matriz de Caminos:Sea G un grafo dirigido simple con m nodos v1,v2…..vm. La matriz de caminos o matriz de alcance de G es la matriz m-cuadrada P= v(i,j) definida como sigue:

Suponga que hay un camino desde vi hasta vj. Entonces tiene que haber un camino simple desde vi hasta vj cuando vi=vj, o un ciclo de vi a vj cuando vi=vj. Como G solo tiene m nodos n un camino simple así ha de tener longitud m-1 o menor, o un ciclo así ha de tener longitud m o menor. Esto significa que existe una entrada ij no nula de la matriz Bm definida de la anterior subsección. De acuerdo con esto, tenemos la siguiente relación entre la matriz de caminos P y la matriz de adyacencia A.

Proposición 3. Sea A la matriz de adyacencia y P= pi,j, la matriz de caminos de un grafo G , Entonces pi,j =1 si y solo si hay un número positivo en la entrada ij de la matriz.

Bm=A+A2 +A3+....+Am

Considere el grafo G con m=4 nodos de la figura 3 .Sumando las matrices con las potencias A,A(2),A(3) y A(4) obtenemos la siguiente matriz B4 , remplazando las entradas positivas por 1, obtenemos la matriz de caminos P del grafo G .

Examinando la matriz P, vemos que el nodo v2 no es alcanzable por ninguno de los otros nodos. Recuerde que se dice que un dirigido G es fuertemente conexo si, para cada par de nodos u y v de G, existe tanto un camino de u a v como de v a u. Por tanto, G es fuertemente conexo si y solo si la matriz de caminos P de G no tiene entradas nulas. Así el grafo G de la figura 3 no es fuertemente conexo.

Página 13


El cierre transitivo de un grafo G se define como el grafo G’ tal que G’ tiene los mismos nodos que G y existe una arista (vi,vj) en G siempre que existe un camino de vi a vj en G.

Así la matriz de caminos P del grafo G es precisamente la matriz de adyacencia de su cierre transitivo G`. Mas aún un grafo G es fuertemente conexo si y solo si su cierre transitivo es un grafo completo.

Nota: La matriz de adyacencia A y la matriz de caminos P de un grafo G se pueden ver como matrices lógicas (booleanas), donde el 0 representa Falso y el 1 representa cierto.

Así como las operaciones lógicas de (Y) y O(V) se pueden aplicar a las entradas de A y P los valores de Y y O aparecen en la figura 8.4. Las operaciones se usarán en la siguientesección

Figura 4

BÚSQUEDA DE SOLUCIONES

Estrategias de Búsqueda

Una estrategia de búsqueda queda definida por el orden en que se expanden los nodos. Las estrategias son evaluadas por medio de las siguientes dimensiones:

Completitud: Si un algoritmo es completo tenemos la garantía de que hallará la solución, si no lo es, es posible que el algoritmo no acabe o que sea incapaz de encontrarla.

Complejidad temporal: Nos indicará el coste temporal de la búsqueda en función del tamaño del problema, generalmente a partir del factor de ramificación y la profundidad a la que se encuentra la solución (número de nodos generados)

Complejidad espacial: Espacio requerido para almacenar los nodos pendientes de explorar. También se puede tener en cuenta el espacio para almacenar los nodos ya explorados si es necesario para el algoritmo (número máximo de nodos en memoria).

Optimalidad: Si es capaz de encontrar la mejor solución según algún criterio de preferencia o coste (si existen varias).

Página 14


Las complejidades temporal y espacial se miden en términos de

b: máximo factor de ramificación (máximo número de sucesores de cualquier nodo) del árbol de búsqueda

d: profundidad de la solución de menor coste.

m: profundidad máxima del espacio de estados (puede ser ∞)

Atendiendo a estos criterios podemos clasificar los algoritmos principales en:

a) Algoritmos de búsqueda no informada

Llamadas de búsqueda ciega, porque sólo usan la información de la definición del problema. Estos algoritmos no tienen en cuenta el coste de la solución durante la búsqueda. Su funcionamiento es sistemático, siguen un orden de visitas de nodos fijo, establecido por la estructura del espacio de búsqueda. Los principales ejemplos de estos algoritmos son:

Búsqueda primero en amplitud Búsqueda de costo uniforme Búsqueda primero en profundidad Búsqueda en profundidad limitada Búsqueda por profundización iterativa Búsqueda bidireccional

b) Algoritmos de búsqueda heurística y búsqueda local:

Estos algoritmos utilizan una estimación del coste o de la calidad de la solución para guiar la búsqueda, de manera que se basan en algún criterio heurístico dependiente del problema. Estos algoritmos no son sistemáticos, de manera que el orden de exploración no lo determina la estructura del espacio de búsqueda sino el criterio heurístico. Algunos de ellos tampoco son exhaustivos y basan su menor complejidad computacional en ignorar parte del espacio de búsqueda. Existen bastantes algoritmos de este tipo con funcionamientos muy diferentes, no siempre garantizan el encontrar la solución óptima, ni tan siquiera el hallar una solución. Los principales ejemplos de estos algoritmos son A*, IDA*, Branch & Bound, Hill-climbing.

Página 15


Búsqueda No Informada

Los algoritmos de búsqueda no informada, también conocidos como algoritmos de búsqueda ciega, no dependen de información propia del problema a la hora de resolverlo. Es decir, son algoritmos generales y por lo tanto se pueden aplicar en cualquier circunstancia. El término búsqueda ciega significa que ellas no tienen información adicional acerca de los estados, más allá de la que proporciona la definición del problema. Todo lo que ellas pueden hacer es generar los sucesores y distinguir entre un estado objetivo de uno que no lo es. Estos algoritmos se basan en la estructura del espacio de estados y determinan estrategias sistemáticas para su exploración. Es decir, siguen una estrategia fija a la hora de visitar los nodos que representan los estados del problema. Se trata también de algoritmos exhaustivos, de manera que pueden acabar recorriendo todos los nodos del problema para hallar la solución. Existen básicamente dos políticas de recorrido de un espacio de búsqueda, en anchura y en profundidad. Todas las estrategias se distinguen por el orden de expansión de los nodos. Al ser algoritmos exhaustivos y sistemáticos su coste puede ser prohibitivo para la mayoría de los problemas reales, por lo tanto sólo será aplicables en problemas pequeños. Su ventaja es que no nos hace falta obtener ningún conocimiento adicional sobre el problema, por lo que siempre son aplicables.

Búsqueda Primera en Anchura ó Primera en Amplitud

La búsqueda primero en anchura intenta explorar el espacio de búsqueda haciendo un recorrido por niveles, de manera que un nodo se visita solamente cuando todos sus predecesores y sus hermanos anteriores en orden de generación ya se han visitado. Es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc. En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel. La búsqueda primero en anchura se puede implementar llamando a la Función Busqueda_General con una frontera vacía que sea una estructura Cola (primero en entrar primero en salir, FIFO), asegurando que los nodos primeros visitados serán los primeros expandidos.

Página 16


La estructura FIFO pone todos los nuevos sucesores generados al final de la cola, lo que significa que los nodos más superficiales se expanden antes que lo nodos más profundos.

En el

siguiente gráfico se muestra el progreso de la búsqueda:

Algoritmo de búsqueda en amplitud

1. Crear una lista de nodos llamada ABIERTA e “inicializarla” con un único nodo raíz, al que se le asigna el estado inicial del problema.

2. Hasta que ABIERTA esté vacía o se encuentre una meta realizar las siguientes acciones:

2.1 Extraer el primer nodo de ABIERTA y llamar a ese nodo m.

2.2 Expandir m (generar todos los sucesores). Para cada operador aplicable y cada forma de aplicación:

1) Aplicar el operador a m, obtener un nuevo estado y crear un puntero que permita saber que su predecesor es m.

Página 17


2) Si el nuevo estado generado es meta, salir del proceso iterativo iniciado en 2.2 y devolver dicho estado.

3) Incluir el nuevo estado al final de ABIERTA (una vez completado este proceso para todos los sucesores de m -cuando no se haya encontrado una meta- se continúa el proceso iterativo en el paso 2)

En este algoritmo la lista ABIERTA va a funcionar como una cola FIFO.

Los nodos que haya en ABIERTA serán aquellos que haya sido generados, pero que todavía no han sido expandidos.

Los elementos que van a ser expandidos se toman al comienzo de la lista ABIERTA.

Sus sucesores se añaden al final.

De esta forma siempre se expandirán los nodos más antiguos.

Ventajas:

Si el problema tiene una solución este procedimiento garantiza el encontrarla. Si hubiera varias soluciones se obtiene la de menor coste (la óptima), es decir, la que requiere un menor número de pasos (si consideramos un coste uniforme de aplicación de los operadores)

Desventajas:

Si el nivel de profundidad asociado a la solución es significativamente menor que el factor de ramificación se expandirían demasiados nodos inútilmente.

Por otro lado la principal desventaja de este método es el espacio de almacenamiento requerido. Esto lo hace prácticamente inviable para problemas complejos, como suelen ser los del mundo real.

Búsqueda Primero en Profundidad o Profundidad Prioritaria

Es aquél procedimiento de control en el que se centra en expandir un único camino desde la raíz.

En el caso de llegar a un callejón sin salida se retrocede hasta el nodo más cercano desde donde se puede tomar una ruta alternativa para poder seguir avanzando.

Para llevar a cabo este tipo de búsqueda debe utilizarse una estructura de tipo pila (LIFO) que vaya almacenando los nodos generados.

Suele establecerse el llamado límite de exploración, que marca la máxima longitud que puede alcanzar cualquier camino desde laraíz durante el proceso de búsqueda.

Página 18


Algoritmo de búsqueda en profundidad

1. Crear una lista de nodos llamada ABIERTA e “inicializarla” con un único nodo raíz, al que se le asigna el estado inicial del problema.

2. Hasta que ABIERTA esté vacía o se encuentre una meta realizar las siguientes acciones:

2.1 Extraer el primer nodo de ABIERTA y llamar a ese nodo m.

2.2 Si la profundidad de m es igual a lp regresar a 2.1. En caso contrario continuar.

2.3 Expandir m (generar todos los sucesores). Para cada operador aplicable y cada forma de aplicación:

1) Aplicar el operador a m, obtener un nuevo estado y crear un puntero que permita saber que su predecesor es m.

2) Si el nuevo estado generado es meta, salir del proceso iterativo iniciado en 2.1 y devolver dicho estado.

3) Incluir el nuevo estado al principio de ABIERTA en un orden arbitrario.

Si algún sucesor de m es meta, abandonar el proceso iterativo señalado en 2.1devolviendo el camino de la solución que se obtienerecorriendo los punteros de sus antepasados.

Si algún sucesor de m se encuentra en un callejón sin salidaeliminarlo de ABIERTA y continuar en 2.2

Página 19


Ventajas:

La principal ventaja de este algoritmo radica en el reducido valor de su complejidad espacial. Cuando existen múltiples soluciones posibles la eficiencia del algoritmo aumenta.

Desventajas:

La dificultad estriba en el tiempo requerido. El algoritmo puede dedicarse a recorrer un camino demasiado largo que no conduzca a ninguna solución. Es más, si no se guarda constancia de los nodos que forman el camino recorrido se podría caer en ciclos y el proceso no acabaría.

El problema por tanto es determinar cuál debe ser lp. Si éste es inferior a la longitud real del camino de la solución, ésta nunca se encontraría, y si es mucho mayor sería ineficiente. Esta es la razón por la que lp debería llamarse límite de exploración.

PROFUNDIDAD LIMITADA

Una variante de la búsqueda primero en profundidad, que trata de aliviar el problema de los árboles ilimitados (con ramas infinitas), el algoritmo de profundidad limitada. Éste impone un límite máximo de profundidad (l) que impone la longitud máxima de los caminos recorridos. Esta limitación garantiza que el algoritmo acaba, pero no garantiza la solución ya que esta puede estar a mayor profundidad que el límite impuesto. Lamentablemente se añade alguna complicación adicional si escogemos l tal que l<d. Entonces el objetivo está fuera del límite de profundidad El límite de profundidad puede estar basado en el conocimiento previo del problema: Por ejemplo, en el mapa de Rumania hay 20 ciudades, luego la solución debe ser como mucho con l=19 La estrategia se puede implementar modificando la Función Busqueda_General con una condicional del límite de la profundidad.

Página 20


Nodos Repetidos Respecto al tratamiento de nodos repetidos, podemos ver los diferentes casos en el siguiente gráfico:

Si el nodo generado actual está repetido en niveles superiores (más cerca de la raíz), su coste será peor ya que su camino desde la raíz es más largo, si está al mismo nivel, su coste será el mismo. En ambos casos podemos olvidarnos de este nodo. En el caso de que el repetido corresponda a un nodo de profundidad superior, significa que hemos llegado al mismo estado por un camino más corto, por tanto deberemos mantenerlo y continuar su exploración, ya que nos permitirá llegar a mayor profundidad que antes. Si se considera un límite de profundidad, el tratamiento de nodos repetidos no es crucial, pues los ciclos no llevarán a caminos infinitos. De este modo se mantendrá el coste espacial lineal, lo cual es una gran ventaja. El evitar tener que tratar repetidos y tener un coste espacial lineal supone una característica diferenciadora que hace muy ventajosa a la búsqueda en

Página 21


profundidad. Este algoritmo será capaz de obtener soluciones que se encuentren a gran profundidad

Búsqueda de Costo Uniforme

La búsqueda primero en anchura es óptimo cuando todos los costes son iguales, ya que expande el nodo menos profundo. La búsqueda de coste uniforme es una extensión de primero en anchura de forma que es óptimo para cualquier función de coste (estrictamente positiva). Se expande el nodo con el camino de menor coste desde el nodo raíz. Si todos los costes de cada acción son iguales, es idéntico a primero en anchura. Esta búsqueda está dirigida por los costes de los caminos más que por las profundidades. No puede haber acciones de coste 0 (CERO) que conduzcan al mismo estado, pues generaría un bucle infinito. La estructura de los nodos abiertos, se implementa mediante una cola (FIFO) prioritaria, con una inserción en orden de coste creciente.

EJERCICIOS:

Un granjero fue al mercado y compró un lobo, una cabra y una col. Para volver a su casa tenía que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras.

Si el lobo se queda solo con la cabra se la come, si la cabra se queda sola con la col se la come.

El reto del granjero era cruzar él mismo y dejar sus compras a la otra orilla del río, dejando cada compra intacta. ¿Cómo lo hizo?

Página 22


Solución:

-> (0)

-> (1)

-> Orden: Cabra, Col, Lobo, Hombre

Estado inicial = (0, 0, 0, 0)

Estado final= (1, 1, 1, 1)

NODO ACTUAL SUCESOR FRONTERA(0, 0, 0, 0)

1 (0, 0, 0, 0) (1, 0, 0,1) (1, 0, 0,1)2 (1, 0, 0,1) (1, 0, 0, 0) (1, 0, 0, 0)3 (1, 0, 0, 0) (1, 1, 0, 1) (1, 1, 0, 1)

(1, 0, 1, 1) (1, 0, 1, 1)4 (1, 1, 0, 1) (0, 1, 0, 0) (1, 0, 1, 1)

(1, 0, 0, 0) (0, 1, 0, 0)5 (1, 0, 1, 1) (0, 0, 1, 0) (0, 1, 0, 0)

(0, 0, 1, 0)6 (0, 1, 0, 0) (0, 1, 1, 1) (0, 0, 1, 0)

(0, 1, 1, 1)7 (0, 0,1,0) (0,1,1,1)8 (0, 1, 1, 1) (0, 1, 1, 0) (0, 1, 1, 0)9

(0, 1, 1, 0)

(1, 1, 1, 1) (1, 1, 1, 1)

Amazonas

Cajamarca

Huaraz

LimaTrujillo

Paijan

Guadalupe

Pacasmayo

Chepen

TumbesPiuraChiclayo

Página 23


NODO ACTUAL SUCESORES FRONTERAS

1 Chiclayo Chepén, Cajamarca, Piura

Chepén, Cajamarca, Piura

2 Chepén Pacasmayo Cajamarca, Piura, Pacasmayo

3 Cajamarca Huaraz, Amazonas Piura, Pacasmayo, Huaraz, Amazonas

4 Piura Tumbes

Pacasmayo, Huaraz, Amazonas, Tumbes

5 Pacasmayo Guadalupe

Huaraz, Amazonas, Tumbes, Guadalupe

6 Huaraz Trujillo, Lima Amazonas, Tumbes, Guadalupe, Trujillo, Lima

7 Amazonas Cuzco Tumbes, Guadalupe, Trujillo, Lima,

LimaTrujillo

Página 24


Cuzco

8 Tumbes - Guadalupe, Trujillo, Lima, Cuzco

9 Guadalupe Paijan Trujillo, Lima, Cuzco, Paijan

10 Trujillo - Lima, Cuzco, Paijan

11 Lima - Cuzco, Paijan

12 Cuzco

Primero en Profundidad

NODO ACTUAL SUCESORES FRONTERAS

1 Chiclayo Chepén, Cajamarca, Piura

Chepén, Cajamarca, Piura

2 Chepén Pacasmayo Pacasmayo, Cajamarca, Piura

3 Pacasmayo Guadalupe Guadalupe, Cajamarca, Piura

4 Guadalupe Paijan Paijan, Cajamarca, Piura

5 Paijan Trujillo Trujillo, Cajamarca, Piura

6 Trujillo Lima, Huaraz Lima, Huaraz, Cajamarca, Piura

7 Lima Cuzco Cuzco, Huaraz, Cajamarca, Piura

8 Cuzco

Página 25

trabajo final grafos

Documents