Uso de graph searching PDF

Preview

Summary

Explicacion de como usar la herramienta Graph Searching...

Description

´ FACULTADE DE INFORMATICA Grao en Enxe˜ nar´ıa Inform´ atica Sistemas Intelixentes Tutorial sobre la herramienta Graph Searching. Ejercicios de b´ usqueda

1

La herramienta Graph Searching

Graph Searching es una aplicaci´ on Java que permite modelar, editar y resolver problemas de b´ usqueda. 1. Descarga la herramienta. Ve a http://www.aispace.org y haz click en Downloads. De entre las diferentes herramientas disponibles, ve a la u ´ ltima versi´ on de Graph Searching y selecciona el tipo de descarga preferido (se recomienda el .jar download). 2. Ejecuta la herramienta. 3. Abre un problema de ejemplo. Ve a File | Load Sample Problem. Selecciona Bicycle Courier Problem (acyclic). 4. Configura el aspecto de la interfaz. Se recomienda: • Cambiar el tama˜ no de la letra. Ir a View | Font Size. • Mostrar el coste de las ramas. Ir a View | Show Edge Costs. 5. Realiza una breve toma de contacto con la herramienta. El panel principal se divide en dos pesta˜ nas, una para editar el ´arbol o grafo y otra para resolver el problema: • Create. Con el rat´ on, prueba a crear, editar y conectar nodos. • Solve. Realiza alguna b´ usqueda paso a paso. Una vez que est´es familiarizado con c´ omo la herramienta representa gr´aficamente los problemas, pasa a los ejercicios que se describen a continuaci´ on.

2

Ejercicios de b´ usqueda

Realiza los siguientes ejercicios con la herramienta. Comenta los resultados con el profesor si tienes dudas; no hay que entregar nada. 1. Abre otro problema de ejemplo. Ve a File | Load Sample Problem. Selecciona Delivery Robot (acyclic). 2. Ve a Search Options | Search Algorithms y aseg´ urate de que est´ a seleccionada la b´ usqueda en profundidad (Depth First). 3. Ve a Search Options | Neighbor Ordering Strategies y selecciona Alphabetical. ¿Qu´e significa esto? ¿Cu´al es la diferencia entre Alphabetical y Left to Right? Haz pruebas si quieres, pero aseg´ urate de que al final queda seleccionada Alphabetical. Al cambiar una opci´ on de b´ usqueda, reinicia siempre la b´ usqueda haciendo clic en Reset Search. 4. Ejecuta paso a paso el algoritmo de b´ usqueda en profundidad (con ordenaci´ on de vecinos alfab´etica) hasta llegar a la meta. • ¿Por qu´e visita los nodos en ese orden? 1

• Ve a Edit | View Text Representation. ¿Qu´e significan estos datos? • Convierte el nodo mail en una meta m´as y ejecuta la b´ usqueda. ¿Por qu´e nunca llega a mail?

5. Cambia el algoritmo a b´ usqueda en anchura (Breadth First). Aseg´ urate de que sigues teniendo dos metas y ordenaci´on de vecinos alfab´etica. 6. Ejecuta paso a paso el algoritmo de b´ usqueda en anchura hasta llegar a la meta. • ¿Por qu´e expande tantos nodos s´ olo para al final llegar a mail? • Por qu´e ahora termina en mail en vez de en r123? • Cambia a ordenaci´on de vecinos de izquierda a derecha y reinicia la b´ usqueda. ¿Qu´e sucede ahora? • ¿Qu´e algoritmo es mejor, el de b´ usqueda en anchura o el de b´ usqueda en profundidad? 7. Cambia a ordenaci´ on alfab´etica de vecinos, reinicia la b´ usqueda en anchura y vete paso a paso, fij´andote bien en c´ omo se construye la frontera. ¿Por qu´e van quedando ordenados de esa manera los nodos de la frontera? 8. Vuelve a cambiar a b´ usqueda en profundidad y f´ıjate bien en c´omo se construye la frontera. ¿En qu´e se diferencia el modo de construcci´on de la frontera en ambos algoritmos? 9. Cambia al algoritmo Lowest Cost First. ¿Qu´e lo diferencia de los anteriores? 10. Crea los nodos Node 0 y Node 1. Crea una rama desde el nodo o103 a Node 0 con coste 1. Crea una rama desde Node 0 a Node 1 con coste 16. Ejecuta el algoritmo Lowest Cost First. ¿Qu´e sucede?

2...