Practica Busquedas
4.3
a. SearchNode.java es la clase que define la estructura de datos que corresponde a un nodo en el espacio de búsqueda. Verifica qué atributos contiene dicha clase y qué significa cada uno de ellos. Verifica también qué métodos se han definido y qué hace cada uno.
Atributos:
String label: representa el nombre del nodo
Object state: define el espacio de estados posibles que puede tener el nodo
Object oper: operador que se usa para generar un nodo
Vector links: las aristas del nodo
Int depth: profundidad del arbol
Boolean expanded: bandera para indicar si ya pasaste por el nodo o no y has pasado por sus hijos
Boolean tested: bandera para indicar si ya pasaste por un nodo.
Float cost: costo para llegar de un nodo a otro
Metodos:
Constructor SearchNode(String label, Object state)
Metodo constructor de la clase, inicializa los atributos.
Void Addlink(SearchNode Node):
Enlaza un nodo a otro
Void Addlinks(SearchNode n1, SearchNode n2)
Enlaza 2 nodos a otro
Void Addlinks(SearchNode n1, SearchNode n2, SearchNode n3)
Enlaza 3 nodos a otro
Void Addlinks(SearchNode n1, SearchNode n2, SearchNode n3, SearchNode n4)
Enlaza 4 nodos a otro
Void Addlinks(Vector nodes)
Enlaza muchos nodos (no definido) a otro
Boolean leaf()
Te indica si hay nodos enlazados a un nodo
Void setdepth(int depth)
Indica la profundidad del arbol
Void setoperator(obj operator)
Asigna un valor al atributo operator
Void setexpanded()
Define que el nodo esta expandido.
Void setExpanded(boolean state)
Se asigna el valor del parametro estado al atributo expanded del nodo para definir si está expandido o no
Void setTested(boolean state)
Se asigna el valor del parametro estado al atributo tested del nodo para definir si ya se paso por ahi o no
Void setDisplay(TextArea textArea)
Se inicializa el area en el que se representara el programa
Void reset()
Se reinicia el nodo, con sus atributos para volver a hacer una busqueda
Void trace()
Se escribe el trayecto que se ha cursado de un nodo a otro, se utiliza identacion para indicar la profundidad
Void expand(vector queue, int position)
Llama al metodo setExpand (ver setExpand para más información)
b. SearchGraph.java es la clase que define un Grafo de Búsqueda como un objeto de tipo Hash Table (¿Por qué un Hash Table?). Verifica los atributos y los métodos que se han definido en esta clase y cómo se utiliza cada uno de ellos.
String name: es tu cadena que buscarás
Constructor SearchGraph(String name) Metodo constructor de la clase, inicializa los atributos.
Void reset(): hace un reset a las banderas de tested y expanded y le da el valor de 0 a la profundidad
Void put(SearchNode node): mete un nodo a la hash table
SearchNode depthFirstSearch(SearchNode initialNode, Object goalState): hace la busqueda en el grafo utlizando el algortimo de depth-first
SearchNode breathFirstSearch(SearchNode initialNode, Object goalState): hace la busqueda en el grafo utilizando breath-first
SearchNode depthLimitedSearch(SearchNode initialNode, Object goalState, int maxDepth): hace la busqueda en el grafo utilizando el algoritmo depth en el cual se detiene en una profundidad predeterminada
SearchNode iterDeepSearch(SearchNode initialNode, Object goalState): hace la busqueda en el grafo
SearchNode bestFirstSearch(SearchNode initialNode, Object goalState): hace la busqueda en el grafo utlizando el algoritmo de best-first en el cual se toma el cuenta el costo
c. SearchApplet.java es la clase que define un applet que demuestra el uso de 4 métodos de búsqueda (En amplitud, en profundidad, profundidad iterativa y Mejor Primero). La clase define objetos AWT para formar la GUI. Verifica de qué forma se crea el espacio de búsqueda a partir de esta clase.
El espacio de búsqueda se define cuando elegimos la ciudad origen y destino dependiendo del método de búsqueda que se elija
d. Cuando intentes probar el funcionamiento del algoritmo “Mejor Primero” vas a notar una peculiaridad de la implementación: ¿Cuál es?
La peculiaridad es que siempre va a Rochester como ciudad destino.
4.4
1. AbstractGraphSearch.java es una clase abstracta que define los atributos y los métodos para construir un grafo y luego realizar la búsqueda de una ruta en él. ¿Qué atributos define y qué significa cada uno? ¿Qué métodos define y para qué sirve cada uno de ellos? ¿Por qué esta clase es abstracta?
void addNode(String name, int x, int y) agrega nodos y les asigna nombre y posición
int getNumNodes() te regresa el número de nodos
int getNumLinks() te regresa el número de aristas que lo unen
String getNodeName(int index) obtienes el nombre del nodo que está en el índice
int getNodeX(int index) te regresa la posición X del nodo
int getNodeY(int index) te regresa la posición Y del nodo
int getLink1(int index) te regresa su primera unión
int getLink2(int index) te regresa su senda unión
void addLink(int node1, int node2) unes dos nodos
void addLink(String name1, String name2) unes dos nodos a partir de su nombre
abstract int[] findPath(int start_node, int goal_node) te regresa los nodos que recorrió desde el estado inicial al objetivo
int getNodeIndex(String name) Regresa el índice de todos los nodos
2. DepthFirstSearch.java y BreadthFirstSearch.java son dos clases que heredan de la clase abstracta anterior. ¿Qué atributos y qué métodos definen? ¿Por qué son subclases de la clase abstracta?
DepthFirstSearch.java:
int[] findPath(int start_node, int goal_node)
int[] findPathHelper(int [] path, int num_path, int goal_node)
int[] connected_nodes(int [] path, int num_path)
BreathFirstSearch.java
int[] findPath(int start_node, int goal_node)
IntQueue(int num)
IntQueue()
void addToBackOfQueue(int n)
int removeFromQueue()
boolean isEmpty()
int peekAtFrontOfQueue()
int[] connected_nodes(int node)
3. Finalmente GraphDepthFirstSearch.java y GraphBreadthFirstSearch.java son las clases que implementan el algoritmo para un nodo dado. ¿Qué atributos y qué métodos son definidos en cada uno y para qué sirven?
void jbInit() throws Exception Crea la ventana gráfica donde se desplegará la búsqueda
void paintNode(Graphics g, String name, int x, int y) Coloca los nodos en una posición y los identifica en la aplicación gráfica
void paint(Graphics g) Es la que dibuja el grafo
