grafos - departamento de lenguajes y ciencias de la...

Grafos y espacios de estados

Ingeniería Informática

Ingeniería Técnica en Informática

Departamento de Lenguajes y

Ciencias de la Computación

Universidad de Málaga

Grafos y espacios de estados 2

Contenido

1. Grafos

2. Espacios de estados

Grafos


Grafos

Definición: Un grafo GGGG es un par (NNNN, AAAA) donde NNNN es un conjunto finito y AAAA es una relación binaria sobre NNNN

AAAA ⊆⊆⊆⊆ NNNN ×××× NNNN

Los elementos de NNNN se llaman nodos, los de AAAA, arcos.

Definición: Si la relación AAAA es simétrica:

∀∀∀∀ x, y. (x, y) ∈∈∈∈ AAAA ⇒⇒⇒⇒ (y, x) ∈∈∈∈ AAAA

se dice que GGGG es un grafo no dirigido, de lo contrario GGGG es un grafo dirigido

Los pares (x,y) y (y,x) componen una arista.


Representación de grafos dirigidos (I)

Ejemplo: NNNN = {a,b,c}, AAAA = {(a,b), (b,c), (c,a)}

Las representaciones más comunes son:

listas de adyacencia

matriz de adyacencia

¿Cuál es la forma más adecuada de representar un grafo en Prolog?

a b

c


Representación de grafos dirigidos (y II)

AAAA es una relación entre objetos (nodos), lo más simple es representarla con un predicado arco/2:

arco(a,b).

arco(b,c).

arco(c,a).

El dominio de los nodos se define extensionalmente es_nodo/1:es_nodo(a).

es_nodo(b).

es_nodo(c).

o bien intensionalmente, a partir de arco/2:

es_nodo(X):-arco(X,_).

es_nodo(X):-arco(_,X).


¿Y si hay más de un grafo en mi programa?

Basta añadir un identificador único para cada grafo.

Ejemplo: grafos G1 y A-92

% arco(+ident,?nodo,?nodo)

arco(g1,a,b). arco(a92,malaga,sevilla).

arco(g1,b,c). arco(a92,malaga,granada).

arco(g1,c,a). arco(a92,granada,almeria).

Este identificador también se emplea en la definición de nodos:

es_nodo(Id,X):-arco(Id,X,_).

es_nodo(Id,X):-arco(Id,_,X).


Representación de grafos no dirigidos (I)

Una posibilidad es definir dos hechos por cada arista:

arista(a,b).

arista(b,a).

arista(b,c).

arista(c,b).

arista(c,a).

arista(a,c).

¿Puedes pensar una solución mejor?...

a b

c


Cierre o clausura de una relación binaria

Definición: Dada una relación AAAA, llamamos cierre o clausura de AAAAa una relación AAAA’ tal que AAAA ⊆⊆⊆⊆ AAAA’

AAAA’ se obtiene añadiendo tuplas a AAAA

Cerramos AAAA añadiendo el número mínimo de tuplas tal que AAAA’satisfaga cierta propiedad (reflexiva, simétrica,…)

Ejemplo: cierre simétrico

AAAA’ = AAAA ∪∪∪∪ { (y,x) / (x,y) ∈∈∈∈ AAAA }

AAAA AAAA AAAA’


Representación de grafos no dirigidos (y II)

La relación arista/2 es el cierre simétrico de arco/2:

arco(a,b).

arco(b,c).

arco(c,a).

AAAA’ = AAAA ∪∪∪∪ { (y,x) / (x,y) ∈∈∈∈ AAAA }

arista(X,Y) :- arco(X,Y).

arista(Y,X) :- arco(X,Y).

La representación de los nodos es la misma que en los grafos dirigidos.

a b

c


Conectividad en grafos (I)

conectados(?X,?Y) – hay un camino que une X e Y

conectados(X,X) :-

es_nodo(X).

conectados(X,Y) :-

arco(X,Z),

conectados(Z,Y).

La relación conectados/2 es el cierre reflexivo y transitivo de la relación arco/2.

Si el grafo es no dirigido, basta reemplazar arco/2 por arista/2.

Problema: ¿Y si el grafo es cíclico?


Conectividad en grafos (II)

:- conectados(a,b).

:- arco(a,Z1),conectados(Z1,b).

Z1/b

:- conectados(b,b).

:- es_nodo(b). :- arco(b,Z2),conectados(Z2,b).

Z2/c

:- conectados(c,b).

:- arco(c,Z3),conectados(Z3,b).

Z3/a

a b

c


Conectividad en grafos (y III)

Podemos añadir una lista con los nodos visitados:

conectados(X,Y) :-

conectados(X,Y,[X]).

% conectados(?X,?Y,+Visitados)

conectados(X,X,_) :-

es_nodo(X).

conectados(X,Y,Visitados) :-

arco(X,Z),

no_esta(Z,Visitados),

conectados(Z,Y,[Z|Visitados]).

Visitados está siempre instanciada (modo +)¿Cómo modificarlo para obtener el camino de X a Y?


Caminos en un grafo (I)

camino(?X,?Y,?Cs) – Cs es un camino de X a Y

camino(X,Y,Cs) :-

camino(X,Y,[X],Cs).

% camino(?X,?Y,+Visitados,?Camino)

camino(X,X,Visitados,Cs) :-

inversa(Visitados,Cs).

camino(X,Y,Visitados,Cs) :-

arco(X,Z),


camino(Z,Y,[Z|Visitados],Cs).

¿Cómo es posible evitar la llamada a inversa/2?


Caminos en un grafo (y II)


camino(X,Y,[X|Cs]) :-

camino(X,Y,[X],Cs).


camino(X,X,_,[]).

camino(X,Y,Visitados,[Z|Cs]) :-

arco(X,Z),



Visitados está siempre instanciada (modo +)Cs se construye (o comprueba) de la cabeza a la cola


Grafos etiquetados

Definición: Un grafo etiquetado GGGG es una terna (NNNN, TTTT, AAAA) donde NNNNes un conjunto finito de nodos, TTTT es un conjunto finito de etiquetas y AAAA es una relación ternaria

AAAA ⊆⊆⊆⊆ TTTT ×××× NNNN ×××× NNNN

Los elementos de AAAA se llaman arcos etiquetados.

Definición: Un multigrafo es un grafo etiquetado donde las etiquetas permiten que haya más de un arco entre un par de nodos.

Definición: Un grafo con peso es un grafo etiquetado donde las etiquetas denotan el peso o coste asociado al arco.


Aplicación: autómatas finitos

Codificaremos un autómata finito (AF) en Prolog

Un AF es un quíntupla 〈Q〈Q〈Q〈Q,QQQQoooo,FFFF,AAAA,δδδδ〉〉〉〉 donde:

QQQQ es un conjunto de estados

QQQQ es un estado inicial (QQQQ ∈∈∈∈ QQQQ)

FFFF es un conjunto de estados finales (FFFF ⊆⊆⊆⊆ QQQQ)

AAAA es un alfabeto

δδδδ es una función de transición δδδδ:QQQQ ×××× AAAA →→→→ QQQQ

La función de transición es un grafo dirigido etiquetado

Un AF reconoce cadenas de un lenguaje regular


Un ejemplo de autómata finito

El autómata finito de la figura reconoce el lenguaje a*bc (d* | e*)f

q0 q1

q2

q3

q4

a

b

c

c

e

d

f

f


Objetos del AF

En la definición del AF, identificamos el alfabeto y los estados

alfabeto átomos a,b,c,d,e,f,$

estados átomos q0,q1,q2,q3,q4

Además, el AF recibirá una cadena de entrada en una cinta

cadena functor cinta/2

Cadena::= cinta(átomo,Cadena)

| $

La cadena “abcdf” se representa por el término

cinta(a,cinta(b,cinta(c,(cinta(d,(cinta(f,$)))))))


Relaciones del AF

Función de transición δδδδ

definimos el procedimiento delta/3

por cada transición δδδδ(qi,s) = qjintroducimos un hecho delta(qi,s,qj).

Estado inicial QQQQoooo

definimos el procedimiento inicial/1

mediante el único hecho inicial(q0).

Estados finales FFFF

definimos el procedimiento final/1

mediante el hecho final(q4).


Reconocimiento de la cadena

El reconocimiento es una relación entre una cadena y un estado

reconoce(Q,S) - “El AF reconoce la cadena S desde el estado Q”

El procedimiento reconoce/2 se define recursivamente:

% reconoce(+Estado,+Cadena)

reconoce(Q,'$') :-

final(Q).

reconoce(Q,cinta(C,Resto)) :-

delta(Q,C,QN),

reconoce(QN,Resto).


El programa Prolog completo

% delta/3

delta(q0,a,q0).

delta(q0,b,q1).

delta(q1,c,q2).

delta(q1,c,q3).

delta(q2,d,q2).

delta(q2,f,q4).

delta(q3,e,q3).

delta(q3,f,q4).

% inicial/1

inicial(q0).

% final/1

final(q4).

% reconoce/2

reconoce(Q,cinta(C,Resto)) :-

delta(Q,C,QN),

reconoce(QN,Resto).

reconoce(Q,'$') :-

final(Q).

% automata/1

automata(Cadena) :-

inicial(Q0),

reconoce(Q0,Cadena),

write_ln('cadena aceptada').


Caminos especiales

Definición: un camino euleriano es un camino que va desde un nodo X hasta un nodo Y pasando exactamente una vez por cada arco(arista) del grafo

Definición: un ciclo euleriano es un camino euleriano que empieza y acaba en el mismo nodo

Definición: un camino hamiltoniano es un camino que va desde un nodo X hasta un nodo Y pasando exactamente una vez por cada nodo del grafo

Definición: un ciclo hamiltoniano es un camino hamiltoniano que empieza y acaba en el mismo nodo


El salto del caballo (I)

Dado un tablero de ajedrez de NxN, se trata de recorrer el tablero completo con un caballo, visitando cada escaque exactamente una vez

XX

XX

XX

XX


El salto del caballo (II)

Podemos enfocar este problema como un camino hamiltoniano:

los nodos son los escaques del tablero (i,j): 1�� i,j �� N

los arcos son los movimientos del caballo

(i,j)

(i-2,j-1) (i-2,j+1)

(i-1,j-2)

(i+1,j-2)

(i+2,j-1) (i+2,j+1)

(i-1,j+2)

(i+1,j+2)


El salto del caballo (III)

No resulta adecuado representar el grafo de forma explícita:

% es_nodo/1

nodo(1,1). nodo(1,2) ... nodo(1,N).

nodo(2,1). nodo(2,2) ... nodo(2,N).

...

nodo(N,1). nodo(N,2) ... nodo(N,N).

% arco/2

arco((1,1),(2,3)). arco((1,1),(3,2)).

...

¿Cómo podemos representar los nodos y arcos de forma genérica?


El salto del caballo (IV)

arcos: hasta 8 vecinos legales

direccion(-2,+1). direccion(-2,-1).

direccion(+2,+1). direccion(+2,-1).

direccion(-1,+2). direccion(-1,-2).

direccion(+1,+2). direccion(+1,-2).

% arco(+Origen,?Destino,+Tamaño)

arco((X,Y),(NX,NY),N) :-

direccion(Dx,Dy),

NX is X + Dx,

NY is Y + Dy,

NX > 0, NX =< N, % dentro del tablero

NY > 0, NY =< N.


El salto del caballo (V)


camino(X,Y,[X|Cs]) :-

camino(X,Y,[X],Cs).


camino(X,X,_,[]).

camino(X,Y,Visitados,[Z|Cs]) :-

arco(X,Z),



El predicado camino/3 cuida que no se repitan nodos¿Cómo aseguramos que hemos visitado todos los nodos?


El salto del caballo (y VI)

salta((X,Y),N,[(X,Y)|Rec]) :-

K is N*N-1,

salta((X,Y),N,K,[(X,Y)],Rec).

% salta(?Ei,+N,+Pasos_por_dar,+Visitados,?Camino)

salta(_,_,0,_,[]).

salta((X,Y),N,K,Visitados,[(NX,NY)|Rec]) :-

K > 0,

arco((X,Y),N,(NX,NY)),

no_esta((NX,NY),Visitados),

K1 is K-1,

salta((NX,NY),N,K1,[(NX,NY)|Visitados],Rec).


Ejercicios

1. Escribe predicados Prolog para obtener caminos y ciclos eulerianos y hamiltonianos de un grafo dado.

2. Escribe un predicado Prolog que dado un grafo con pesos encuentre todos los caminos que no superen un coste dado.

3. Escribe un programa Prolog que pinte un sobre como el de la figura sin levantar el lápiz del papel (es decir, recorre el grafo pasando exactamente una vez por cada arco)

c

b

a

d

e

Espacios de estados


Espacios de estados y búsquedas (I)

Formalismo para representar y resolver problemas en IA

Un espacio de estados es un grafo dirigido donde:

los nodos representan estados del problema, y

los arcos son posibles transiciones de estados (movimientos)

Un problema se plantea facilitando un estado inicial, un estadofinal que se desea alcanzar, y un conjunto de reglas de transición

Un problema se resuelve encontrando un camino en el grafo dirigido que nos lleve desde el estado inicial al estado final

Ejemplos: mundos de bloques, tres en raya, ajedrez, etc.


Espacios de estados y búsquedas (II)

c

a

b

1 2 3

c

a

b

1 2 3

cab

1 2 3

c

a

b

1 2 3

Estado inicial

Estado final

Ciclo

Solución


Espacios de estados y búsquedas (III)

El estado inicial es único

El estado final no tiene por qué ser único

El conjunto de reglas de transición o movimientos es finito

El espacio de estados puede ser cíclico

El espacio de estados puede ser muy grande o incluso infinito

El espacio de estados se genera incrementalmente, aplicando reglas de transición al estado actual.


Espacios de estados y búsquedas (IV)

Existen diferentes técnicas de búsqueda para encontrar un camino en un espacio de estados:

búsqueda en profundidad

búsqueda en anchura

búsqueda por profundización progresiva

búsqueda heurística (por ejemplo, A*)


Espacios de estados y búsquedas (y V)

En Prolog es muy fácil codificar la búsqueda en profundidad aprovechando el mecanismo de retroceso (backtracking)

Para resolver un problema hay que:

representar los estados mediante términos Prolog

especificar el estado inicial

estado_inicial(Eini).

caracterizar los estados finales

estado_final(Efin):- condiciones…

definir transiciones entre estados como cláusulas Prolog

mover(Ei,Ej) :- condiciones…

Utilizaremos esta técnica para resolver algunos problemas clásicos


Un mundo de bloques (I)

Tenemos una mesa con tres posiciones (1,2,3) sobre las que se pueden apilar libremente tres bloques (a,b,c)

Representación del estado:

% estado/3

estado(sobre(a,sobre(b,mesa)), mesa, sobre(c,mesa))

c

a

b

1 2 3


Un mundo de bloques (II)

Es posible pasar de un estado inicial:

a otro estado final:

si y sólo si hay una secuencia de movimientos válidos

c

a

b

1 2 3

c

a

b

1 2 3


Un mundo de bloques (III)

Podemos transferir un bloque de la cima de una pila a la cima de otra pila

Representación de los movimientos:

% de la pila 1 a la 2 o 3

mover(estado(sobre(A,X),Y,Z),estado(X,sobre(A,Y),Z)).

mover(estado(sobre(A,X),Y,Z),estado(X,Y,sobre(A,Z))).


mover(estado(X,sobre(A,Y),Z),estado(sobre(A,X),Y,Z)).

mover(estado(X,sobre(A,Y),Z),estado(X,Y,sobre(A,Z))).


mover(estado(X,Y,sobre(A,Z)),estado(sobre(A,X),Y,Z)).

mover(estado(X,Y,sobre(A,Z)),estado(X,sobre(A,Y),Z)).


Un mundo de bloques (y IV)

Podemos aplicar una búsqueda en profundidad sobre grafos dirigidos con ciclos:

% resolver(?Plan)

resolver([Eini|Plan]) :-

estado_inicial(Eini),

resolver(Eini,[Eini],Plan).

% resolver(+Estado,+Visitados,?Plan)

resolver(Efin,_,[]):-

estado_final(Efin).

resolver(Ei,Visitados,[Ej|Plan]) :-

mover(Ei,Ej), % arco de Ei a Ej

no_esta(Ej,Visitados),

resolver(Ej,[Ej|Visitados],Plan).


Patrón de la búsqueda en profundidad

Podemos parametrizar la búsqueda en profundidad:

resolver(Problema,[Eo|Solucion]) :-

estado_inicial(Problema,Eo),

resolver(Problema,Eo,[Eo],Solucion).

resolver(Problema,En,_,[]) :-

estado_final(Problema,En).

resolver(Problema,Ei,Visitados,[En|Es]) :-

mover(Problema,Ei,En),

no_esta(En,Visitados),

resolver(Problema,En,[En|Visitados],Es).


El problema de los cántaros (I)

Se dispone de dos cántaros X e Y de capacidades MX y MY litros, respectivamente; así como de una fuente ilimitada.

Las operaciones disponibles son las siguientes:

llenar completamente cualquiera de los dos cántaros en la fuente

vaciar completamente cualquiera de los cántaros

verter el contenido de un cántaro en otro hasta que el primero quede vacío o el segundo quede lleno (no puede rebosar)

Partiendo de ambos cántaros vacíos, ¿es posible aislar en uno de ellos K litros, donde 1 �� K �� max(MX,MY)?


El problema de los cántaros (II)

Estados: (X,Y), donde 0 �� X �� MX y 0 �� Y �� MY

Movimientos: suponemos un par de hechos que definen las capacidades máximas, MX y MY

max_cap_x(5). % MX

max_cap_y(8). % MY

mover((_,Y),(0,Y)). % vaciar X

mover((X,_),(X,0)). % vaciar Y

mover((_,Y),(MX,Y)):- % llenar X

max_cap_x(MX).

mover((X,_),(X,MY)):- % llenar Y

max_cap_y(MY).


El problema de los cántaros (III)

Movimientos:

% verter X en Y (entero)

mover((X,Y),(0,NY)) :-

max_cap_y(MY),

NY is Y+X,

NY =< MY.

verter Y en X entero es simétrico


El problema de los cántaros (y IV)

Movimientos:

% verter X en Y (parcialmente)

mover((X,Y),(NX,MY)) :-

max_cap_y(MY),

NX is X-(MY-Y),

NX > 0.

verter Y en X parcialmente es simétrico

Para resolver el problema, basta aplicar la anterior búsqueda en profundidad.


Ejercicios (I)

1. Un granjero, un lobo, una cabra y una col desean cruzar un río con la ayuda de una barca con capacidad para cualesquiera dos deellos, y en la que sólo puede remar el granjero. Escribe un programa Prolog que genere un plan para cruzar el río, teniendo en cuenta que si el lobo queda a solas con la cabra, la devorará, y si la cabra queda a solas con la col, se la comerá.

2. Tres misioneros y tres caníbales se disponen a cruzar un río con una canoa con capacidad para dos personas. Escribe un programa que genere un plan para cruzar el río, teniendo en cuenta que nunca puede haber menos misioneros que caníbales en alguna de las márgenes del río, pues serían devorados.


Ejercicios (y II)

3. Un sabio dispone de dos relojes de arena con capacidad para medir 7 y 11 minutos respectivamente. Los relojes se ponen en marcha simultáneamente y cuando uno se acaba se puede:

- dejar acabar al otro- volver los dos relojes- volver uno solo de los relojes.

Escribir un programa Prolog que genere una secuencia de movimientos de los relojes que permita medir una cantidad N de minutos.

4. Cinco matrimonios se encuentran aislados por una inundación. Para huir, cuentan con un bote con capacidad para tres personas.Los maridos son tan celosos que en ningún caso permitirían que sus esposas se encontraran en compañía de otros hombres sin estar ellos mismos presentes. Escribe un programa Prolog que genere un plan para salvar a estos matrimonios.

grafos - departamento de lenguajes y ciencias de la...

Documents