Search Algorithms Benno Stein
Contents I. Introduction
Objectives
Literature
Chapter S:I I. Introduction
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Remarks:
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem
Remarks:
Examples for Search Problems SAT Problem
Examples for Search Problems SAT Problem
Remarks:
Examples for Search Problems SAT Problem
Examples for Search Problems SAT Problem
Examples for Search Problems Road Map Problem
Examples for Search Problems Road Map Problem
Examples for Search Problems Road Map Problem
Examples for Search Problems Road Map Problem
Examples for Search Problems Road Map Problem
Examples for Search Problems Road Map Problem
Examples for Search Problems Road Map Problem
Examples for Search Problems 8-Puzzle Problem
Examples for Search Problems 8-Puzzle Problem
Examples for Search Problems 8-Puzzle Problem
Examples for Search Problems 8-Puzzle Problem
Remarks:
Examples for Search Problems 8-Puzzle Problem
Examples for Search Problems 8-Puzzle Problem
Remarks:
Examples for Search Problems Traveling Salesman Problem (TSP)
Examples for Search Problems Traveling Salesman Problem
Examples for Search Problems Traveling Salesman Problem
Examples for Search Problems Traveling Salesman Problem
Examples for Search Problems Traveling Salesman Problem
Remarks:
Examples for Search Problems Traveling Salesman Problem
Examples for Search Problems Traveling Salesman Problem
Remarks:
Examples for Search Problems Blocks World Planning
Examples for Search Problems Blocks World Planning
Examples for Search Problems Blocks World Planning
Examples for Search Problems Blocks World Planning
Remarks:
Examples for Search Problems Problem Abstraction: State Transition System
Examples for Search Problems Problem Abstraction: State Transition System
Remarks:
Examples for Search Problems The Counterfeit Coin Problem
Examples for Search Problems The Counterfeit Coin Problem
Remarks:
Examples for Search Problems The Counterfeit Coin Problem
Remarks:
Examples for Search Problems The Counterfeit Coin Problem
Examples for Search Problems The Counterfeit Coin Problem
Examples for Search Problems Tic-Tac-Toe Game
Examples for Search Problems Tic-Tac-Toe Game
Examples for Search Problems Tic-Tac-Toe Game
Examples for Search Problems Tic-Tac-Toe Game
Examples for Search Problems Tic-Tac-Toe Game
Search Problem Abstraction Questions
Chapter S:II II. Basic Search Algorithms
Systematic Search Types of Problems
Systematic Search Types of Problems
Remarks:
Systematic Search Generic Framework for Modeling Search Problems
Remarks:
Systematic Search Modeling Problem Solving as Reachability Problem for STS
Systematic Search Modeling Problem Solving as Reachability Problem for STS
Systematic Search Modeling Problem Solving as Reachability Problem for STS
Remarks:
Graph Theory Basics Definition 2 (Directed Graph)
Graph Theory Basics Definition 2 (Directed Graph)
Remarks:
Graph Theory Basics Definition 3 (Path, Node Types, Outdegree)
Graph Theory Basics Definition 3 (Path, Node Types, Outdegree)
Remarks:
Graph Theory Basics Definition 4 (Directed Tree, Uniform Tree)
Remarks:
State Space Search Modeling Problem Solving as Path-Seeking Problem
State Space Search Modeling Problem Solving as Path-Seeking Problem
Remarks:
State Space Search Modeling Problem Solving as Path-Seeking Problem
Remarks:
State Space Search Illustration of Solution Paths and Solution Bases
State Space Search Illustration of Solution Paths and Solution Bases
State Space Search Illustration of Solution Paths and Solution Bases
State Space Search Interpretation of Solution Bases
State Space Search Graph Representation
State Space Search Graph Representation
Remarks:
State Space Search Definition 7 (Node Generation)
State Space Search Node Generation as a Basic Step
State Space Search Node Expansion as a Basic Step
Remarks:
State Space Search Explicit Parts of State-Space Subgraphs
State Space Search Requirements for an Algorithmization of State-Space Search
Remarks:
Remarks (continued) :
State Space Search Generic Schema for OR-Graph Search Algorithms
State Space Search
Remarks:
State Space Search Efficient Storage of Solution Bases
Remarks:
State Space Search Efficient Storage of Solution Bases
State Space Search Efficient Storage of Solution Bases
Remarks:
State Space Search Efficient Storage of Solution Bases
State Space Search Efficient Storage of Solution Bases
State Space Search Schema for Search Algorithms
Remarks:
State Space Search Searching a Search Space Graph
State Space Search Searching a Search Space Graph
State Space Search Searching a Search Space Graph
Remarks:
State Space Search Algorithm:
Remarks:
State Space Search Searching a Search Space Graph
State Space Search Uninformed Systematic Search
State Space Search Uninformed Systematic Search
Remarks:
State Space Search Basic_OR_Search for Optimization
State Space Search Optimization Problem Example
State Space Search Optimization Problem Example
State Space Search Optimization Problem Example
State Space Search Optimization Problem Example
Chapter S:II
Depth-First Search (DFS) Depth-first search is an uninformed (systematic) search strategy.
Remarks:
Depth-First Search Algorithm:
Depth-First Search
Remarks:
Depth-First Search
Remarks:
Depth-First Search
Remarks:
Depth-First Search Discussion
Depth-First Search Discussion
Depth-First Search Example: 4-Queens Problem
Depth-First Search Example: 4-Queens Problem
Depth-First Search Example: 4-Queens Problem
Depth-First Search Example: 4-Queens Problem
Depth-First Search Search Depth
Remarks:
Remarks (continued) :
Backtracking (BT) Backtracking is a variant of depth-first search.
Remarks:
Backtracking Algorithm:
Backtracking
Backtracking Discussion
Backtracking Discussion
Backtracking Monotone Backtracking: 8-Queens Problem
Backtracking Monotone Backtracking: 8-Queens Problem
Backtracking Monotone Backtracking: 8-Queens Problem
Backtracking Monotone Backtracking: 8-Queens Problem
Backtracking Non-Monotone Backtracking: 8-Queens Problem
Backtracking Non-Monotone Backtracking: Generic
Remarks:
Backtracking Example: Backtracking for Optimization (see Basic_OR_Search for Optimization)
Backtracking Example: Backtracking for Optimization (see Basic_OR_Search for Optimization)
Backtracking Example: Backtracking for Optimization (see Basic_OR_Search for Optimization)
Breadth-First Search (BFS)
Remarks:
Breadth-First Search Algorithm:
Breadth-First Search BFS(s, successors, ?, ⊥)
Breadth-First Search BFS(s, successors, ?, ⊥)
Breadth-First Search Discussion
Breadth-First Search Discussion
Breadth-First Search Example: 4-Queens Problem
Breadth-First Search Example: 4-Queens Problem
Uniform-Cost Search Uniform-Cost Search for Optimization (see Basic_OR_Search for Optimization)
Remarks:
Uniform-Cost Search Uniform-Cost Search for Optimization: Example
Uniform-Cost Search Uniform-Cost Search for Optimization: Example
Uniform-Cost Search
Remarks:
Chapter S:II
AND-OR Graph Basics Problem Reduction: A Powerful Tool in Problem Solving
AND-OR Graph Basics Building Blocks of Problem Reduction
AND-OR Graph Basics Graph Representations of Problem Reduction
Remarks:
AND-OR Graph Basics Problem Reduction: Integration into State-Space Graphs
AND-OR Graph Basics Canonical Representation of AND-OR Graphs
Remarks:
AND-OR Graph Basics AND-OR Graph Properties
AND-OR Graph Basics Solutions in AND-OR Graphs
AND-OR Graph Basics Solution Trees: A Generalisation of Solution Paths
AND-OR Graph Basics Solution Trees in AND-OR Graphs
Remarks:
AND-OR Graph Basics Solution Trees in AND-OR Graphs
AND-OR Graph Basics Requirements for an Algorithmization of AND-OR Graph Search
Remarks:
AND-OR Graph Basics Generic Schema for AND-OR-Graph Tree Search Algorithms
AND-OR Graph Basics Algorithm:
AND-OR Graph Basics
Remarks:
AND-OR Graph Basics Efficient Storage of Solution-Tree Bases
AND-OR Graph Basics Example: Sharing initial subtree in solution trees for AND-OR graphs
Depth-First Search of AND-OR Graphs Differences to OR Graphs Search
Depth-First Search of AND-OR Graphs Differences to OR Graphs Search
Depth-First Search of AND-OR Graphs Solved Labeling
Depth-First Search of AND-OR Graphs Adaption of DFS
Depth-First Search of AND-OR Graphs Adaption of DFS
Depth-First Search of AND-OR Graphs Adaption of DFS
Remarks:
Depth-First Search of AND-OR Graphs Example: Solved Labeling Using DFS
Depth-First Search of AND-OR Graphs Example: Solved Labeling Using DFS
Depth-First Search of AND-OR Graphs Example: Solved Labeling Using DFS
Depth-First Search of AND-OR Graphs Example: Solved Labeling Using DFS
Depth-First Search of AND-OR Graphs Example: Solved Labeling Using DFS
Remarks:
Depth-First Search of AND-OR Graphs Solution Tree Labeling
Depth-First Search of AND-OR Graphs Example: Solution Labeling Using DFS
Depth-First Search of AND-OR Graphs Example: Solution Labeling Using DFS
Depth-First Search of AND-OR Graphs Example: Solution Labeling Using DFS
Depth-First Search of AND-OR Graphs Example: Solution Labeling Using DFS
Remarks:
Depth-First Search of AND-OR Graphs Redundant Problem Solving
Depth-First Search of AND-OR Graphs Redundant Problem Solving
Remarks:
Depth-First Search of AND-OR Graphs Dealing with Cycles (1)
Depth-First Search of AND-OR Graphs Dealing with Cycles (1)
Depth-First Search of AND-OR Graphs Dealing with Cycles (2)
Depth-First Search of AND-OR Graphs Dealing with Cycles (2)
Depth-First Search of AND-OR Graphs Dealing with Cycles (2)
Depth-First Search of AND-OR Graphs Dealing with Cycles (2)
Remarks:
AND-OR Graph Search Enfolding of Solution Trees: Compact Representation as AND-OR Graph
AND-OR Graph Search Enfolding of Solution Trees
AND-OR Graph Search Enfolding of Solution Trees
AND-OR Graph Search Enfolding of Solution Trees
AND-OR Graph Search Enfolding of Solution Trees
AND-OR Graph Search Enfolding of Solution Trees
AND-OR Graph Search Enfolding of Solution Trees
AND-OR Graph Search Solution Graphs in AND-OR Graphs
Remarks:
Remarks:
AND-OR Graph Search Solution Graphs in AND-OR Graphs
Remarks:
AND-OR Graph Search Generic Schema for AND-OR-Graph Search Algorithms
AND-OR Graph Search Algorithm:
AND-OR Graph Search
Remarks:
AND-OR Graph Search Efficient Storage of Solution Graphs
AND-OR Graph Search Solution Graphs and Backpointers: Sharing Initial Parts
AND-OR Graph Search Solution Graphs and Backpointers: Sharing Initial Parts
AND-OR Graph Search Solution Graphs and Backpointers: Sharing Solution Graphs
AND-OR Graph Search Solution Graphs and Backpointers: Sharing Solution Graphs
AND-OR Graph Search Efficient Storage of Solution Bases
AND-OR Graph Search Efficient Storage of Solution Bases
AND-OR Graph Search Foundation of AND-OR Graph Search
AND-OR Graph Search Algorithm:
AND-OR Graph Search
Remarks:
Remarks (continued):
Chapter S:III III. Informed Search
Best-First Search “To enhance the performance of AI’s programs, knowledge [about the
Best-First Search “To enhance the performance of AI’s programs, knowledge [about the
Best-First Search “To enhance the performance of AI’s programs, knowledge [about the
Best-First Search “To enhance the performance of AI’s programs, knowledge [about the
Best-First Search “The promise of a node is estimated numerically by a heuristic
Best-First Search “The promise of a node is estimated numerically by a heuristic
Remarks:
Best-First Search Schema for Best-First Algorithms
Remarks:
Best-First Search for State-Space Graphs Principles of Algorithm BF
Best-First Search for State-Space Graphs Principles of Algorithm BF
Best-First Search for State-Space Graphs Principles of Algorithm BF
Best-First Search for State-Space Graphs Principles of Algorithm BF
Best-First Search for State-Space Graphs Principles of Algorithm BF
Best-First Search for State-Space Graphs Principles of Algorithm BF
Remarks:
Best-First Search for State-Space Graphs Algorithm:
Best-First Search for State-Space Graphs BF(s, successors, ?, f )
Best-First Search for State-Space Graphs BF(s, successors, ?, f )
Best-First Search for State-Space Graphs BF(s, successors, ?, f )
Best-First Search for State-Space Graphs BF(s, successors, ?, f )
Best-First Search for State-Space Graphs
Remarks:
Best-First Search for State-Space Graphs Path Discarding for a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Remarks:
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Best-First Search for State-Space Graphs Re-evaluation of a Node n0
Remarks:
Best-First Search for State-Space Graphs Optimality of Algorithm BF
Best-First Search for State-Space Graphs Optimality of Algorithm BF
Best-First Search for State-Space Graphs
Best-First Search for State-Space Graphs Irrevocable Path Discarding in Algorithm BF
Best-First Search for State-Space Graphs Irrevocable Path Discarding in Algorithm BF
Chapter S:III III. Informed Search
Cost Functions for State-Space Graphs Overview
Cost Functions for State-Space Graphs Overview
Cost Functions for State-Space Graphs Overview
Cost Functions for State-Space Graphs Overview
Cost Functions for State-Space Graphs Overview
Cost Functions for State-Space Graphs Overview
Cost Functions for State-Space Graphs Overview
Cost Functions for State-Space Graphs If solution paths are known, the solution cost for a solution path can be
Remarks:
Cost Functions for State-Space Graphs If the entire search space graph rooted at a node s is known, the optimum solution
Cost Functions for State-Space Graphs If the entire search space graph rooted at a node s is known, the optimum solution
Remarks:
Cost Functions for State-Space Graphs If the entire search space graph rooted at a node s is known, the optimum solution
Remarks:
Cost Functions for State-Space Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for State-Space Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for State-Space Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for State-Space Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for State-Space Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for State-Space Graphs Cost Concept in Uniform-Cost Search
Cost Functions for State-Space Graphs Recursive Cost Functions
Remarks:
Cost Functions for State-Space Graphs Recursive Cost Functions
Remarks:
Cost Functions for State-Space Graphs Recursive Cost Functions
Evaluation of State-Space Graphs Recursive Cost Functions and Efficiency
Evaluation of State-Space Graphs Recursive Cost Functions and Efficiency
Evaluation of State-Space Graphs Recursive Cost Functions and Efficiency
Cost Functions for State-Space Graphs Recursive Cost Functions and Efficiency
Remarks: b
Evaluation of State-Space Graphs b
Evaluation of State-Space Graphs b
Evaluation of State-Space Graphs Additive Cost Measures
Evaluation of State-Space Graphs Additive Cost Measures
Remarks:
Evaluation of State-Space Graphs Relation to the Algorithm BF
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Remarks:
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Optimum Solution Cost and Order Preservation
Evaluation of State-Space Graphs Taxonomy of Best-First Algorithms
Algorithm A* Algorithm:
Algorithm A*
Remarks:
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
Algorithm A* Exponential Runtime Example
Algorithm A* Exponential Runtime Example
Algorithm A* Exponential Runtime Example
Algorithm A* Exponential Runtime Example
Chapter S:III III. Informed Search
BF* Variants For trees G: Breadth-first search is a special case of A*, where h = 0 and
BF* Variants For trees G: Breadth-first search is a special case of A*, where h = 0 and
BF* Variants For trees G: Breadth-first search is a special case of A*, where h = 0 and
BF* Variants For trees G: Breadth-first search is a special case of A*, where h = 0 and
BF* Variants For trees G: Uniform-cost search is a special case of A*, where h = 0.
BF* Variants For trees G: Depth-first search is a special case of Z*, where f (n0) = f (n) − 1,
BF* Variants For trees G: Depth-first search is a special case of Z*, where f (n0) = f (n) − 1,
BF* Variants For trees G: Depth-first search is a special case of Z*, where f (n0) = f (n) − 1,
BF* Variants For trees G: Depth-first search is a special case of Z*, where f (n0) = f (n) − 1,
BF* Variants OPEN List Restriction: Hill-Climbing (HC)
BF* Variants Algorithm:
BF* Variants
BF* Variants HC Discussion
BF* Variants HC Discussion
BF* Variants HC Discussion
Remarks:
BF* Variants OPEN List Restriction: Best-First Beam Search
Remarks:
Hybrid Strategies Spectrum of Search Strategies
Hybrid Strategies Spectrum of Search Strategies
Hybrid Strategies Spectrum of Search Strategies
Hybrid Strategies Spectrum of Search Strategies
Hybrid Strategies Spectrum of Search Strategies
Remarks:
Hybrid Strategies Strategy 1: BF at Top
Hybrid Strategies Strategy 2: BF at Bottom
Remarks:
Hybrid Strategies Strategy 3: Extended Expansion
Hybrid Strategies Strategy 3: Extended Expansion
Remarks:
Hybrid Strategies Strategy 4: IDA*
Remarks:
Hybrid Strategies Strategy 5: Focal Search
Remarks:
Hybrid Strategies Strategy 6: Staged Search
Remarks:
Chapter S:III III. Informed Search
Best-First Search for AND-OR Graphs Illustration of Solution Graphs and Solution Bases
Best-First Search for AND-OR Graphs Illustration of Solution Graphs and Solution Bases
Best-First Search for AND-OR Graphs Illustration of Solution Graphs and Solution Bases
Best-First Search for AND-OR Graphs Illustration of Solution Graphs and Solution Bases
Best-First Search for AND-OR Graphs Illustration of Solution Graphs and Solution Bases
Best-First Search for AND-OR Graphs Illustration of Solution Graphs and Solution Bases
Best-First Search for AND-OR Graphs Principles of Algorithm GBF
Best-First Search for AND-OR Graphs Principles of Algorithm GBF
Best-First Search for AND-OR Graphs Principles of Algorithm GBF
Best-First Search for AND-OR Graphs Principles of Algorithm GBF
Best-First Search for AND-OR Graphs Principles of Algorithm GBF
Remarks:
Best-First Search for AND-OR Graphs Algorithm:
Best-First Search for AND-OR Graphs GBF(s, successors, is_solved, f1 , f2 )
Best-First Search for AND-OR Graphs GBF(s, successors, is_solved, f1 , f2 )
Best-First Search for AND-OR Graphs GBF(s, successors, is_solved, f1 , f2 )
Best-First Search for AND-OR Graphs
Remarks:
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Remarks:
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Illustration of GBF
Best-First Search for AND-OR Graphs Multiple Accounting of a Node
Best-First Search for AND-OR Graphs Multiple Accounting of a Node
Best-First Search for AND-OR Graphs Multiple Accounting of a Node
Best-First Search for AND-OR Graphs Multiple Accounting of a Node
Remarks:
Best-First Search for AND-OR Graphs Optimality of Algorithm GBF
Best-First Search for AND-OR Graphs Optimality of Algorithm GBF
Best-First Search for AND-OR Graphs
Best-First Search for AND-OR Graphs Illustration of GBF*
Best-First Search for AND-OR Graphs Illustration of GBF*
Best-First Search for AND-OR Graphs Illustration of GBF*
Best-First Search for AND-OR Graphs Illustration of GBF*
Best-First Search for AND-OR Graphs Illustration of GBF*
Relation between GBF and BF Algorithm GBF applied to a state-space graph will simulate Algorithm BF.
Relation between GBF and BF Algorithm GBF applied to a state-space graph will simulate Algorithm BF.
Relation between GBF and BF Algorithm GBF applied to a state-space graph will simulate Algorithm BF.
Relation between GBF and BF Algorithm GBF applied to a state-space graph will simulate Algorithm BF.
Relation between GBF and BF Algorithm GBF applied to a state-space graph will simulate Algorithm BF.
Remarks:
Relation between GBF and BF Irrevocability is not Amenable to Problem Reduction Graphs
Remarks:
Chapter S:III III. Informed Search
Cost Functions for AND-OR Graphs Overview
Remarks:
Cost Functions for AND-OR Graphs Overview
Cost Functions for AND-OR Graphs Overview
Cost Functions for AND-OR Graphs If solution graphs are known, the solution cost for a solution graph can be
Remarks:
Cost Functions for AND-OR Graphs If the entire search space graph rooted at a node s is known, the optimum solution
Cost Functions for AND-OR Graphs If the entire search space graph rooted at a node s is known, the optimum solution
Remarks:
Cost Functions for AND-OR Graphs If the entire search space graph rooted at a node s is known, the optimum solution
Remarks:
Cost Functions for AND-OR Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for AND-OR Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for AND-OR Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for AND-OR Graphs If the search space graph rooted at a node s is known partially, the optimum
Cost Functions for AND-OR Graphs Recursive Cost Functions
Cost Functions for AND-OR Graphs Recursive Cost Functions
Remarks:
Cost Functions for AND-OR Graphs Illustration of CH
Cost Functions for AND-OR Graphs Illustration of CH
Cost Functions for AND-OR Graphs Illustration of CH
Cost Functions for AND-OR Graphs Illustration of CH
Cost Functions for AND-OR Graphs Illustration of CH
Cost Functions for AND-OR Graphs Illustration of CH
Remarks:
Cost Functions for AND-OR Graphs Recursive Cost Functions
Cost Functions for AND-OR Graphs Recursive Cost Functions
Evaluation of AND-OR Graphs Recursive Cost Functions and Efficiency
Evaluation of AND-OR Graphs Recursive Cost Functions and Efficiency
Evaluation of AND-OR Graphs Illustration of C ∗
Evaluation of AND-OR Graphs Illustration of C ∗
Evaluation of AND-OR Graphs Illustration of C ∗
Evaluation of AND-OR Graphs Illustration of C ∗
Remarks:
Evaluation of AND-OR Graphs Recursive Cost Functions and Efficiency
Remarks: b requires a useful handling regarding the value ∞
Evaluation of AND-OR Graphs b
Evaluation of AND-OR Graphs Relation to the Algorithm GBF
Evaluation of AND-OR Graphs Relation to the Algorithm GBF
Evaluation of AND-OR Graphs Relation to the Algorithm GBF
Remarks: b is based on a recursive cost function involving a monotone cost measure, the
Evaluation of AND-OR Graphs Taxonomy of Best-First Algorithms
Chapter S:IV IV. Search Space Representation
Problem Solving Problem Characterization
Remarks:
Problem Solving Problem Characterization
Remarks:
Problem Solving Problem Characterization
Problem Solving Decision Problem: Abstract Definition
Remarks:
Problem Solving Search Problem: Abstract Definition
Remarks:
Remarks ( (continued)):
Problem Solving Optimization Problem: Abstract Definition
Remarks:
Systematic Search Search Building Blocks
Systematic Search Search Building Blocks
Systematic Search Definition 1 (Systematic Control Strategy)
Remarks:
Systematic Search Categorization of 'Heuristic [Problem Solving] Methods'
Search Space Encoding Encoding of Solution Candidates
Remarks:
Search Space Encoding Applicable Heuristic Problem Solving Methods
Search Space Encoding Encoding of Solution Candidates (
Remarks:
Remarks (continued) :
Search Space Encoding Encoding of Solution Candidates
Remarks:
Search Space Encoding Example: Subset Encoding for the 8-Queens Problem
Search Space Encoding Example: Subset Encoding for the 8-Puzzle Problem
Remarks:
State-Space Representation Using Subset Encoding in Search
Remarks:
State-Space Representation Subset Encoding in Search
Remarks:
State-Space Representation Example: TSP
State-Space Representation Example: TSP
State-Space Representation Summary: Solving Search Problems by State Space Search
Remarks:
State-Space Representation Example: 8-Queens Problem
State-Space Representation Example: 8-Puzzle Problem
Remarks:
Search Space Encoding Applicable Heuristic Problem Solving Methods
State-Space Representation Search Problem: Constraint-Satisfaction or Optimization
State-Space Representation Search Problem: Constraint-Satisfaction or Optimization
Remarks:
Chapter S:II II. Search Space Representation
Problem-Reduction Representation The Counterfeit Coin Problem
Problem-Reduction Representation The Counterfeit Coin Problem
Remarks:
Problem-Reduction Representation The Different Link Types
Remarks:
Problem-Reduction Representation Counterfeit Problem
Problem-Reduction Representation Counterfeit Problem
Remarks:
Problem-Reduction Representation The Different Node types
Problem-Reduction Representation Canonical Representation of AND-OR Graphs
Remarks:
Problem-Reduction Representation Search Building Blocks
Problem-Reduction Representation Solution Graph
Problem-Reduction Representation Solution Graph
Remarks:
Remarks (continued) :
Problem-Reduction Representation Solution Graph
Problem-Reduction Representation Solution Graph
Problem-Reduction Representation Solution Graph
Problem-Reduction Representation Solution Graph
Remarks:
Problem-Reduction Representation Algorithm:
Problem-Reduction Representation Algorithm:
Problem-Reduction Representation Algorithm:
Problem-Reduction Representation Algorithm:
Problem-Reduction Representation Algorithm:
Problem-Reduction Representation Solution Graphs with Cycles (1)
Problem-Reduction Representation Solution Graphs with Cycles (1)
Problem-Reduction Representation Solution Graphs with Cycles (1)
Remarks:
Problem-Reduction Representation Solution Graphs with Cycles (2)
Problem-Reduction Representation Solution Graphs with Cycles (2)
Problem-Reduction Representation Hypergraphs
Remarks:
Choosing a Representation Problem-Reduction Graphs with Alternating Node Types
Choosing a Representation Problem-Reduction Graphs with Alternating Node Types
Choosing a Representation Transforming Problem-Reduction into State-Space Graphs
Choosing a Representation Transforming Problem-Reduction into State-Space Graphs
Choosing a Representation Transforming Problem-Reduction into State-Space Graphs
Choosing a Representation Transforming Problem-Reduction into State-Space Graphs
Choosing a Representation Transformed Counterfeit Problem
Choosing a Representation State-Space versus Problem-Reduction Representation
Choosing a Representation State-Space versus Problem-Reduction Representation
Remarks:
Choosing a Representation Tower of Hanoi Problem
Choosing a Representation Tower of Hanoi Problem
Choosing a Representation Tower of Hanoi Problem
Choosing a Representation Tower of Hanoi Problem
Choosing a Representation Means-End Analysis
Choosing a Representation Means-End Analysis
Remarks:
Chapter S:V V. Search Theory
Formal Properties of A* Task: Find a cheapest path from s to some node γ ∈ Γ.
Properties of Search Space Graphs Non-Existence of Optimum Solution Paths
Properties of Search Space Graphs Problems in the Search for Optimum Solution Paths
Properties of Search Space Graphs Prop(G): Required Properties of G
Remarks:
Properties of Search Space Graphs Existence of Optimum Solution Path
Properties of Search Space Graphs Existence of Optimum Solution Path
Properties of Search Space Graphs Existence of Optimum Solution Path
Auxiliary Concepts Search Space Graph versus Traversal Tree
Remarks:
Auxiliary Concepts Illustration of Traversal Trees
Remarks:
Auxiliary Concepts Definition 34 (Specific Paths and Functions)
Remarks:
Auxiliary Concepts Definition 34 (Specific Paths and Functions
Remarks:
Auxiliary Concepts Definition 34 (Specific Paths and Functions
Remarks:
Auxiliary Concepts Definition 34 (Specific Paths and Functions
Auxiliary Concepts Definition 34 (Specific Paths and Functions
Remarks:
Auxiliary Concepts Definition 34 (Specific Paths and Functions
Remarks:
Auxiliary Concepts Lemma 35 (Basic Observations)
Remarks:
Roadmap Important Lemmas and Theorems
Completeness of A* Two important concepts for algorithms with regard to the returned solutions are
Remarks:
Completeness of A* Termination
Completeness of A* Termination
Remarks: 1. Obviously, the new backpointer paths that are used in Point 4 are cycle-free.
Completeness of A* Shallowest OPEN Node
Completeness of A* Shallowest OPEN Node
Completeness of A* Illustration of Shallowest OPEN Node
Completeness of A* Illustration of Shallowest OPEN Node
Completeness of A* Illustration of Shallowest OPEN Node
Completeness of A* Illustration of Shallowest OPEN Node
Completeness of A* Shallowest OPEN Node
Completeness of A* Shallowest OPEN Node
Remarks:
Completeness of A* Lemma 40 (Completeness for Finite Graph)
Completeness of A* Lemma 40 (Completeness for Finite Graph)
Remarks:
Completeness of A* Lemma 41 (Shallowest OPEN Node on Path) ?
Completeness of A* Lemma 41 (Shallowest OPEN Node on Path) ?
Completeness of A* Theorem 42 (Completeness)
Completeness of A* Theorem 42 (Completeness)
Remarks:
Admissibility of A* Lemma 43 (Node Cost on Optimum Path)
Admissibility of A* Lemma 43 (Node Cost on Optimum Path)
Remarks:
Admissibility of A* Corollary 44 (Implications of Lemma 43)
Admissibility of A* Definition 45 (Admissibility of h)
Admissibility of A* Corollary 46 (Shallowest OPEN Node on Optimum Path
Admissibility of A* Corollary 46 (Shallowest OPEN Node on Optimum Path
Remarks: ? The Lemma states that nodes on optimum paths are reached by A* with optimum cost when
Admissibility of A* Lemma 47 (C ∗-Bounded OPEN Node)
Admissibility of A* Lemma 47 (C ∗-Bounded OPEN Node)
Remarks:
Admissibility of A* Theorem 48 (Admissibility
Admissibility of A* Theorem 48 (Admissibility
Remarks:
Chapter S:V V. Search Theory
Efficiency of A* Efficiency of Search Algorithms
Efficiency of A* Efficiency of Search Algorithms
Remarks:
Efficiency of A* Efficiency of Search Algorithms
Efficiency of A* Conditions for Node Expansion I
Efficiency of A* Conditions for Node Expansion I
Remarks:
Efficiency of A* Conditions for Node Expansion I
Efficiency of A* Conditions for Node Expansion I
Remarks:
Efficiency of A* Conditions for Node Expansion I
Efficiency of A* Conditions for Node Expansion I
Efficiency of A* Conditions for Node Expansion II
Efficiency of A* Conditions for Node Expansion II
Efficiency of A* Conditions for Node Expansion II
Efficiency of A* Conditions for Node Expansion II
Efficiency of A* Conditions for Node Expansion II
Efficiency of A* Conditions for Node Expansion II
Remarks:
Efficiency of A* Conditions for Node Expansion II
Efficiency of A* Informedness and Dominance
Efficiency of A* Informedness and Dominance
Efficiency of A* Informedness and Dominance
Remarks:
Efficiency of A* Informedness and Dominance: Discussion
Remarks:
Monotone Heuristic Functions Motivation
Monotone Heuristic Functions Motivation
Monotone Heuristic Functions Motivation
Monotone Heuristic Functions Motivation
Monotone Heuristic Functions Illustration of the Global Triangle Inequality
Monotone Heuristic Functions Illustration of the Local Triangle Inequality
Monotone Heuristic Functions Definition 58 (Consistency Condition)
Monotone Heuristic Functions Definition 58 (Consistency Condition)
Remarks:
Monotone Heuristic Functions Theorem 60 (Consistency Equivalent to Monotonicity)
Monotone Heuristic Functions Theorem 60 (Consistency Equivalent to Monotonicity)
Monotone Heuristic Functions Illustration of a Monotone h
Monotone Heuristic Functions Illustration of a Monotone h
Monotone Heuristic Functions Theorem 61 (Monotone Heuristic Functions)
Monotone Heuristic Functions Theorem 61 (Monotone Heuristic Functions)
Remarks:
Monotone Heuristic Functions Theorem 62 (No Reopening)
Monotone Heuristic Functions Theorem 62 (No Reopening)
Remarks:
Monotone Heuristic Functions Illustration of a Non-Monotone h
Monotone Heuristic Functions Illustration of a Non-Monotone h
Monotone Heuristic Functions Illustration of a Non-Monotone h
Monotone Heuristic Functions Illustration of a Non-Monotone h
Monotone Heuristic Functions Illustration of a Non-Monotone h
Monotone Heuristic Functions Theorem 63 (Non-Decreasing f -Values)
Monotone Heuristic Functions Theorem 63 (Non-Decreasing f -Values)
Remarks:
Monotone Heuristic Functions Illustration of Non-Decreasing f -Values
Monotone Heuristic Functions Illustration of Non-Decreasing f -Values
Monotone Heuristic Functions Example: Knight Moves (revisited)
Monotone Heuristic Functions Example: Knight Moves (revisited)
Monotone Heuristic Functions Example: Knight Moves (revisited)
Monotone Heuristic Functions Coping with non-monotonicity
Monotone Heuristic Functions Coping with non-monotonicity
Remarks:
Monotone Heuristic Functions Conditions for Node Expansion III
Monotone Heuristic Functions Conditions for Node Expansion III
Monotone Heuristic Functions Conditions for Node Expansion III
Remarks:
Monotone Heuristic Functions Definition 65 (Largely Dominating Algorithms)
Monotone Heuristic Functions Definition 65 (Largely Dominating Algorithms)
Remarks:
Chapter S:VI VI. Relaxed Models
Motivation
Motivation Basic Questions from Search Theory
Remarks:
Motivation Examination of g and h
Motivation Examination of g and h
Remarks:
ε-Admissible Speedup Versions of A* Bounded Decrease in Solution Quality
ε-Admissible Speedup Versions of A* Bounded Decrease in Solution Quality
ε-Admissible Speedup Versions of A* Static Weighting A* Search: WA*
ε-Admissible Speedup Versions of A* Static Weighting A* Search: WA*
ε-Admissible Speedup Versions of A* Static Weighting A* Search: WA*
Remarks:
ε-Admissible Speedup Versions of A* Static Weighting A* Search: WA*
ε-Admissible Speedup Versions of A* Static Weighting A* Search: WA*
ε-Admissible Speedup Versions of A* Dynamic Weighting A* Search: DWA*
Remarks:
ε-Admissible Speedup Versions of A* Dynamic Weighting A* Search: DWA*
ε-Admissible Speedup Versions of A* Dynamic Weighting A* Search: DWA*
ε-Admissible Speedup Versions of A* Node Selection by hF (n): A*ε
Remarks:
ε-Admissible Speedup Versions of A* Node Selection by hF (n): A*ε
ε-Admissible Speedup Versions of A* Node Selection by hF (n): A*ε
Remarks:
ε-Admissible Speedup Versions of A* Comparison of DWA* and A*ε
ε-Admissible Speedup Versions of A* Comparison of DWA* and A*ε
ε-Admissible Speedup Versions of A* Comparison of DWA* and A*ε
ε-Admissible Speedup Versions of A* Comparison of DWA* and A*ε
Remarks:
ε-Admissible Speedup Versions of A* Unifying View: WA* and DWA* as variants of A*ε
Remarks:
ε-Admissible Speedup Versions of A* Lemma 71 (WA* and DWA* are variants of A*ε)
ε-Admissible Speedup Versions of A* Lemma 71 (WA* and DWA* are variants of A*ε)
ε-Admissible Speedup Versions of A* Pruning Power of h for A*ε
Remarks:
ε-Admissible Speedup Versions of A* Using Monotone Heuristic Functions h in A*ε
ε-Admissible Speedup Versions of A* Using Monotone Heuristic Functions h in A*ε
ε-Admissible Speedup Versions of A* Example: Monotone Heuristic Function h in A*ε
ε-Admissible Speedup Versions of A* Using Monotone Heuristic Functions h in A*ε
ε-Admissible Speedup Versions of A* Using Monotone Heuristic Functions h in A*ε
ε-Admissible Speedup Versions of A* Example: Monotone heuristic function h in NRA*ε
ε-Admissible Speedup Versions of A* Using Monotone Heuristic Functions h in NRA*ε
ε-Admissible Speedup Versions of A* Using Monotone Heuristic Functions h in NRA*ε
Chapter S:VI VI. Relaxed Models
Using Information about Uncertainty of h Using a non-admissible heuristic function
Remarks:
Using Information about Uncertainty of h Illustration of Underestimating and Overestimating Estimation Functions
Using Information about Uncertainty of h Example: Search in “Random” Graphs
Using Information about Uncertainty of h Example: Search in “Random” Graphs
Using Information about Uncertainty of h Describing the Estimation Uncertainty using Density Functions
Using Information about Uncertainty of h Describing the Estimation Uncertainty using Density Functions
Remarks:
Using Information about Uncertainty of h Describing the Estimation Uncertainty using Density Functions
Using Information about Uncertainty of h Describing the Estimation Uncertainty using Density Functions
Remarks: (a) If the density functions do not overlap, the node for which the corresponding density function
Risk Measures Defining the Order of Node Evaluations
Risk Measures Principle of the Algorithm R*δ
Remarks:
Risk Measures Potential for Improvement to a Current Solution
Remarks:
Risk Measures Risk Threshold and Cost Treshold
Risk Measures Definition 75 (Risk Measure)
Remarks:
Risk Measures Definition 77 (δ-Risk-Admissibility)
Remarks:
Risk Measures Risk Measures of Type R(C) = %[C − f +]
Risk Measures Risk Measures of Type R(C) = %[C − f +]
Remarks:
Risk Measures Example
Risk Measures Example
Risk Measures Example
Risk Measures Example
Risk Measures Example
Risk Measures Example
Risk Measures Theorem 79 (δ-Risk-Admissibility of R*δ )
Risk Measures Theorem 79 (δ-Risk-Admissibility of R*δ )
Remarks:
Chapter S:VI VI. Relaxed Models
Heuristiken aus Modellvereinfachungen Beispiel: Modellvereinfachung für das 8-Puzzle
Heuristiken aus Modellvereinfachungen Beispiel: Modellvereinfachung für das 8-Puzzle
Heuristiken aus Modellvereinfachungen Beispiel: Modellvereinfachung für TSP
Heuristiken aus Modellvereinfachungen Beispiel: Modellvereinfachung für TSP
Heuristiken aus Modellvereinfachungen Relaxation
Heuristiken aus Modellvereinfachungen Relaxation
Heuristiken aus Modellvereinfachungen Zulässigkeit, Konsistenz und Monotonie
Heuristiken aus Modellvereinfachungen Over-Constraining
Automatische Generierung von Heuristiken Systematisches Relaxieren von Suchproblemen
Automatische Generierung von Heuristiken Beispiel: 8er-Puzzle
Automatische Generierung von Heuristiken Beispiel: 8er-Puzzle
Automatische Generierung von Heuristiken Problem:
Automatische Generierung von Heuristiken Einfache Probleme: kompositionale Probleme
Automatische Generierung von Heuristiken Einfache Probleme: semikompositionale Probleme
Probabilistische Heuristiken Probabilistisch definierte Probleme
Probabilistische Heuristiken Probabilistisch definierte Probleme
Probabilistische Heuristiken Probabilistisch definierte Probleme
Bemerkungen:
Probabilistische Heuristiken Asymptotische Verteilung von C(N, p)
Probabilistische Heuristiken Asymptotische Verteilung von C(N, p)
Probabilistische Heuristiken Asymptotische Verteilung von C(N, p)
Probabilistische Heuristiken Heuristiken aus der Analyse von Stichproben
Probabilistische Heuristiken Heuristiken aus der Analyse von Stichproben
Chapter S:VII VII. Game Playing
Game Playing Introduction The game tree search here focuses on two-player, perfect-information games.
Game Playing Introduction The game tree search here focuses on two-player, perfect-information games.
Game Playing Introduction Definition 80 (Game Tree)
Remarks:
Game Playing Introduction Illustration
Game Playing Introduction Illustration
Game Playing Introduction Definition 81 (Status Labeling Procedure)
Game Playing Introduction Definition 81 (Status Labeling Procedure)
Remarks:
Game Playing Introduction Definition 82 (Game Strategy, Solution Tree, Winning Strategy)
Game Playing Introduction Illustration
Game Playing Introduction Two strategies T +, T −, of Max and Min respectively, share at each level either one
Game Playing Introduction Strategy considerations for two-player, perfect-information games:
Game Playing Introduction Strategy considerations for two-player, perfect-information games:
Game Playing Introduction Strategy considerations for two-player, perfect-information games:
Game Playing Introduction Strategy considerations for two-player, perfect-information games:
Game Playing Introduction Strategy considerations for two-player, perfect-information games:
Remarks:
Game Playing Introduction The labeling of game trees is possible without distinguishing between Max and
Remarks:
Evaluation Functions for Game Trees Status labeling requires the generation of nearly the complete game tree. The
Evaluation Functions for Game Trees Status labeling requires the generation of nearly the complete game tree. The
Remarks:
Evaluation Functions for Game Trees Definition 84 (Minimax Rule)
Remarks:
Propagation Algorithms for Game Trees
Remarks:
Propagation Algorithms for Game Trees
Propagation Algorithms for Game Trees The pruning rationale used by the algorithm SOLVE is not restricted to two-valued
Propagation Algorithms for Game Trees Game tree with propagated minimax values:
Propagation Algorithms for Game Trees Game tree with propagated minimax values:
Remarks:
Propagation Algorithms for Game Trees Definition 85 (α-Bound)
Remarks:
Propagation Algorithms for Game Trees Definition 86 (β-Bound)
Remarks:
Propagation Algorithms for Game Trees The α-β-pruning scheme:
Remarks:
Propagation Algorithms for Game Trees Algorithm:
Propagation Algorithms for Game Trees