Busqueda binaria

Prácticas de Búsqueda
Resolución en Java

Prácticas de Búsqueda en Java
• Monitor: Alvaro Masó • amaso@gsi.dit.upm.es • Librería Aima-java

Aima-java: Descripción general
• Incluida en ellibro: Artificial Inteligence: A Modern Approach de Stuart Russell y Peter Norvig • Más información en www.cs.berkeley.edu/~russell/

Aima-java: Descripción general
• Librería de carácter general
–Agentes – Aprendizaje – Lógica – Búsqueda

Aima-java: aima.search
• Interfaces
– SearchMethod – State
• public boolean isGoal() • public Enumeration successors()

– Heuristic
• public floath()

– Traversable

Aima-java: Métodos de Búsqueda
• Extienden SearchMethod • GeneralQueueSearch • Implementación del algoritmo de busqueda mediante una cola • El algoritmo queda definido por laforma de inserción y extracción de elementos de la cola

Aima-java: Métodos de Búsqueda
• AStarSearch
o AStarPredicate

• • • •

BreadthFirstSearch DepthBoundedSearch DepthFirstSearchGreedySearch
o GreedyPredicate

• IteratedDeepeningSearch • UniformCostSearch • UniformCostPredicate

Aima-java: Nodos
• SearchNode
– protected – protected – protected – protected – protected Statestate; SearchNode parent; String appliedOp; int depth; float pathCost;

• HeuristicSearchNode

Aima-java: Otros
• Successor • TraversableState

Aima-java: Auxiliar
• aima.cs.util • InterfazGeneralQueue
o FifoQueue o NoRepeatQueue o LifoQueue o PriorityQueue

• Interfaz BinaryPredicate

Aima-java: Resolución de problemas
• 1º Definición de estado
– Implementando aima.search.State yaima.search.Heuristic
• public boolean isGoal() • public Enumeration successors() • public float h()

Aima-java: Resolución de problemas
• 1º Definición de estado
– Extendiendo TraversableState eimplementando aima.search.Heuristic
• public State applyOperator(String op) • public float costOf(String op) • public Enumeration validOperators() • public boolean isGoal() • public float h()...