Notas search methods

M´todos de b´squeda e u
Ricardo Wehbe May 21, 2010

1

Introducci´n: juegos y grafos o

En esta primera parte se introduce la idea intuitiva de grafos a trav´s de un e ejemplo y luego se dan las definiciones formales de los principale conceptos: grafos dirigidos y no dirigidos, ´rboles, ´rboles enraizados, caminos, nodos hijos, a a nodos padres, nodos hermanos, ancestros y descendientes. Elprimer ejemplo de uso de teor´ de grafos se debe posiblemente a Leonhard ıa Euler. Es el llamado problema de los puentes de K¨nigsberg.” El problema o puede plantearse como sigue: en la ciudad de K¨nigsberg hay un r´ y dos o ıo islas. Hay seis puentes que conectan las dos m´rgenes del r´ con alguna isla a ıo y un s´ptimo puente que conecta ambas islas mentre s´ Esto se muestra en e ı. la figura 1.El problema consiste en lo siguiente: ¿existe un recorrido por la
margen 1 p2 p3 p4

p1 isla 1 isla 2

p5

p6 margen 2

p7

Fig. 1: Los siete puentes de K¨nigsberg. o

ciudad que parta de alguna zona (alguna de las m´rgenes o una de las islas) y a que acabe en la misma zona luego de haber atravesado cada uno de los puentes exactamente una vez? En la ´poca de Euler se supon´ que no,ya que nadie e ıa hab´ encontrado nunca una soluci´n. Sin embargo, no exist´ ninguna prueba ıa o ıa de que esto fuese imposible. 1

El grafo que se construye a partir de este mapa es el que se muestra en la figura 2, donde los nodos representan las zonas de la ciudad (las dos m´rgenes a del r´ y las dos islas) y los arcos representan los puentes. ıo

m1 p2 p3 i1 p6 p5 m2 p7 p1 i2 p4

Fig. 2:El grafo de los siete puentes de K¨nigsberg. o

Observemos que a todos los nodos llega un n´mero impar de arcos. Cada vez u que uno pasa por un nodo que no es inicial ni el final uno “elimina” dos arcos: el de llegada y el de salida. Un nodo al que llga un n´mero impar de arcos s´lo u o puede ser el nodo inicial o el final. Al haber m´s de dos nodos terminales, el a problema no tiene soluci´n. oSeguimos con otro ejemplo simple. Se tiene el siguiente escenario: dos oponentes, A y B, est´n jugando a un juego, que es una variante del llamado juego a de Marienbad [1] y que consiste en lo siguiente: Hay una cantidad de f´sforos o sobre la mesa. El primer oponente puede sacar tantos como desee, pero debe sacar por lo menos uno y dejar por lo menos uno. Por lo tanto, en la situaci´n o inicialdebe haber por lo menos dos f´sforos. A partir de esa primera extracci´n, o o cada oponente debe, por turno, sacar por lo menos un f´sforo y como m´ximo o a el doble de f´sforos que su oponente sac´. Gana el que retira el ultimo f´sforo. o o ´ o Supongamos ahora que quedan cinco f´sforos en la mesa y luego de que B retir´ o o dos. ¿Qu´ debe hacer A? Las diferentes posibilidades se pueden mostrarcomo e un grafo. Pero es necesario primero definir c´mo se representar´n los estados del o a juego. Observe que no basta con colocar la cantidad de f´sforos que hay sobre o la mesa, ya que es necesario adem´s saber cu´ntos f´sforos pueden sacarse. El a a o grafo, asumiendo que ambos jugadores son racionales y no dejar´n pasar una a oportunidad de ganar, se muestra en la fig. 3 En este caso queda claroque en la posici´n inicial, si A comienza, B puede o forzar el triunfo o, utilizando la terminolog´ de la teor´ de juegos, B tiene ıa ıa una estrategia ganadora. Esto es porque la posici´n ganadora (0,0) se alcanza o luego de un n´mero par de saltos en todos los camonos excepto en el siguiente: u A retira un f´sforo y va de (5,4) a (4,2); B retira dos f´sforos y va de (4,2) a o o (2,2); FinalmenteA retira los dos f´sforos y gana. Pero B no est´ obligado a o a retirar dos f´sforos en la posici´n (4,2): puede retirar s´lo uno e ir a (3,2). All´ o o o ı, independientemente de lo que haga A, B queda con una posici´n ganadora. o Ya estamos en condiciones de dar las definiciones formale de grafos dirigidos 2

5,4

c
3,3

c
2,2

c
4,2

c
1,1

E

c
0,0

‰ T ©
3,2

T

s...