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 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:
Search Problem Abstraction Questions
Chapter S:II II. Search Space Representation
Systematic Search Types of Problems
Systematic Search Types of Problems
Systematic Search Optimization Problems
Remarks:
Remarks (continued) :
Systematic Search Search Building Blocks
Systematic Search Search Building Blocks
Systematic Search Search Building Blocks
Encoding of Problems Solution Bases
Encoding of Problems Solution Bases
Remarks:
Remarks (continued) :
Remarks (continued) :
Encoding of Problems Solution Bases
Remarks:
Encoding of Problems Example: 8-Queens Problem
Encoding of Problems Example: 8-Puzzle Problem
Encoding of Problems Example: 8-Puzzle Problem
Remarks:
State-Space Representation The Concept of a State
State-Space Representation The Concept of a State
Remarks:
State-Space Representation Search Building Blocks
Remarks:
State-Space Representation Search Building Blocks
State-Space Representation Search Building Blocks
State-Space Representation Solution Path
Remarks:
State-Space Representation Example: 8-Queens Problem
State-Space Representation Example: 8-Puzzle Problem
Remarks:
State-Space Representation Example: TSP
State-Space Representation Example: TSP
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:II II. Basic Search Algorithms
Systematic Search Types of Problems
Systematic Search Types of Problems
Remarks:
Systematic Search Search Building Blocks
Systematic Search Definition 1 (Systematic Control Strategy)
Remarks:
Systematic Search Definition 2 (State Transition System)
Systematic Search Modeling as Reachability Problem for STS
Systematic Search Modeling as Reachability Problem for STS
Systematic Search Modeling as Reachability Problem for STS
Remarks:
Graph Search Basics Definition 3 (Directed Graph)
Graph Search Basics Definition 3 (Directed Graph)
Remarks:
Graph Search Basics Definition 4 (Path, Node Types, Outdegree)
Graph Search Basics Definition 4 (Path, Node Types, Outdegree)
Remarks:
Graph Search Basics Definition 5 (Directed Tree, Uniform Tree)
Remarks:
Graph Search Basics Modeling as Path-Seeking Problem
Graph Search Basics Modeling as Path-Seeking Problem
Remarks:
Graph Search Basics Modeling as Path-Seeking Problem
Remarks:
Graph Search Basics Illustration of Solution Paths and Solution Bases
Best-First Search for State-Space Graphs Illustration of Solution Paths and Solution Bases
Best-First Search for State-Space Graphs Illustration of Solution Paths and Solution Bases
Solution base for s : s
Graph Search Basics Graph Representation
S:II-31
Remarks:
Graph Search Basics Definition 8 (Node Generation)
Graph Search Basics Node Generation as Basic Step
Graph Search Basics Node Expansion as Basic Step
Remarks:
Graph Search Basics Explicit Parts of State-Space Subgraphs
Graph Search Basics Requirements for an Algorithmization of State-Space Search
Remarks:
Remarkss (continued) :
Graph Search Basics Algorithm:
Remarks:
Graph Search Basics Efficient Storage of Solution Bases
Remarks:
Graph Search Basics Efficient Storage of Solution Bases
Graph Search Basics Efficient Storage of Solution Bases
Graph Search Basics Efficient Storage of Solution Bases
Graph Search Basics Efficient Storage of Solution Bases
Graph Search Basics Schema for Search Algorithms
Remarks:
Graph Search Basics Searching a Search Space Graph
Graph Search Basics Searching a Search Space Graph
Graph Search Basics Searching a Search Space Graph
Remarks:
Graph Search Basics Algorithm:
Remarks:
Graph Search Basics Searching a Search Space Graph
Graph Search Basics Uninformed Systematic Search
Graph Search Basics Uninformed Systematic Search
Remarks:
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 Non-Monotone Backtracking: 8-Queens Problem
Backtracking Non-Monotone Backtracking: 8-Queens Problem
Backtracking Non-Monotone Backtracking: 8-Queens Problem
Backtracking Non-Monotone Backtracking: 8-Queens Problem
Backtracking Non-Monotone Backtracking: 8-Queens Problem
Backtracking Non-Monotone Backtracking: Generic
Remarks:
Backtracking Simple Cost Concepts
Backtracking Backtracking for Optimization: Generic
Backtracking Backtracking for Optimization: Example
Backtracking Backtracking for Optimization: Example
Backtracking Backtracking for Optimization: Example
Chapter S:II
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
Remarks:
Uniform-Cost Search Uniform-Cost Search for Optimization: Generic
Uniform-Cost Search Uniform-Cost Search for Optimization: Example
Uniform-Cost Search Uniform-Cost Search for Optimization: Example
Chapter S:IV IV. 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
Best-First Search Schema for Best-First Algorithms
Remarks:
Best-First Search for State-Space Graphs Illustration of Solution Paths and Solution Bases
Best-First Search for State-Space Graphs Illustration of Solution Paths and Solution Bases
Best-First Search for State-Space Graphs Illustration of Solution Paths and Solution Bases
Best-First Search for State-Space Graphs Definition 11 (Solution Base in a State-Space Graph)
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
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 Definition 12 (Solution Base in a Problem-Reduction Graph)
Remarks:
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, ⊥, ?, f1 , f2 )
Best-First Search for AND-OR Graphs GBF(s, successors, ⊥, ?, f1 , f2 )
Best-First Search for AND-OR Graphs GBF(s, successors, ⊥, ?, f1 , f2 )
Best-First Search for AND-OR Graphs GBF(s, successors, ⊥, ?, 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:IV IV. Informed Search
Cost Functions Overview
Remarks:
Cost Functions Overview
Cost Functions Overview
Cost Functions Overview
Cost Functions Overview
Cost Functions Overview
Cost Functions Overview
Cost Functions If solution graphs are known, the solution cost for a solution graph can be
Cost Functions If solution graphs are known, the solution cost for a solution graph can be
Remarks:
Cost Functions If the entire search space graph rooted at a node s is known, the optimum solution
Cost Functions If the entire search space graph rooted at a node s is known, the optimum solution
Remarks:
Cost Functions If the entire search space graph rooted at a node s is known, the optimum solution
Cost Functions If the entire search space graph rooted at a node s is known, the optimum solution
Cost Functions If the search space graph rooted at a node s is known partially, the optimum
Cost Functions If the search space graph rooted at a node s is known partially, the optimum
Cost Functions If the search space graph rooted at a node s is known partially, the optimum
Remarks:
Cost Functions If the search space graph rooted at a node s is known partially, the optimum
Cost Functions If the search space graph rooted at a node s is known partially, the optimum
Cost Functions If the search space graph rooted at a node s is known partially, the optimum
Cost Functions Recursive Cost Functions
Cost Functions Recursive Cost Functions
Cost Functions Recursive Cost Functions
Remarks:
Cost Functions Illustration of CH for AND-OR Graphs
Cost Functions Illustration of CH for AND-OR Graphs
Cost Functions Illustration of CH for AND-OR Graphs
Cost Functions Illustration of CH for AND-OR Graphs
Cost Functions Illustration of CH for AND-OR Graphs
Cost Functions Illustration of CH for AND-OR Graphs
Cost Functions Illustration of CH for AND-OR Graphs
Remarks:
Cost Functions Recursive Cost Functions
Remarks:
Cost Functions Recursive Cost Functions
Cost Functions 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 ∞. (h(n) = ∞
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 a recursive cost function. Hence, the determination of a most promising solution base
Evaluation of AND-OR Graphs Taxonomy of Best-First Algorithms
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
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* Breadth-first search is a special case of A*, where h = 0 and c(n, n0) = 1 for all
Algorithm A* Breadth-first search is a special case of A*, where h = 0 and c(n, n0) = 1 for all
Algorithm A* Breadth-first search is a special case of A*, where h = 0 and c(n, n0) = 1 for all
Algorithm A* Breadth-first search is a special case of A*, where h = 0 and c(n, n0) = 1 for all
Algorithm A* Uniform-cost search is a special case of A*, where h = 0.
Algorithm A* Depth-first search is a special case of Z*, where f (n0) = f (n) − 1, f (s) = 0, for all
Algorithm A* Depth-first search is a special case of Z*, where f (n0) = f (n) − 1, f (s) = 0, for all
Algorithm A* Depth-first search is a special case of Z*, where f (n0) = f (n) − 1, f (s) = 0, for all
Algorithm A* Depth-first search is a special case of Z*, where f (n0) = f (n) − 1, f (s) = 0, for all
Algorithm A* Exponential Runtime Example
Algorithm A* Exponential Runtime Example
Algorithm A* Exponential Runtime Example
Algorithm A* Exponential Runtime Example
Relation to Dynamic Programming Optimum Solution Cost and Bellman’s Principle of Optimality
Relation to Dynamic Programming Optimum Solution Cost and Bellman’s Principle of Optimality
Relation to Dynamic Programming Optimum Solution Cost and Bellman’s Principle of Optimality
Remarks:
Relation to Dynamic Programming Optimum Solution Cost and Bellman’s Principle of Optimality
Relation to Dynamic Programming Optimum Solution Cost and Bellman’s Principle of Optimality
Relation to Dynamic Programming Partially Explored State Spaces
Relation to Dynamic Programming Partially Explored State Spaces
Relation to Dynamic Programming Partially Explored State Spaces
Relation to Dynamic Programming Partially Explored State Spaces
Chapter S:IV IV. Informed Search
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: Best-First Beam Search
Remarks:
Hybrid Strategies Strategy 7: Staged Search
Remarks:
Chapter S:V V. Formal Properties of A*
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 Non-Existence of 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 pointer-paths that are used in Point 4 are cycle-free.
Completeness of A* Shallowest OPEN Node
Completeness of A* Shallowest OPEN Node
Admissibility of A* Illustration of Shallowest OPEN Node
Admissibility of A* Illustration of Shallowest OPEN Node
Admissibility of A* Illustration of Shallowest OPEN Node
Admissibility 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. Formal Properties of A*
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 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 Non-Decreasing f -Values
Monotone Heuristic Functions 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 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 66 (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*
ε-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 Verwendung einer nicht-zulässigen Schätzfunktion
Remarks:
Using Information about Uncertainty of h Illustration von unter- und überschätzenden Schätzfunktionen
Using Information about Uncertainty of h Beispiel: Suche in “zufälligem” Graphen
Using Information about Uncertainty of h Beispiel: Suche in “zufälligem” Graphen
Using Information about Uncertainty of h Beschreibung der Schätzunsicherheit durch Dichtefunktionen
Using Information about Uncertainty of h Beschreibung der Schätzunsicherheit durch Dichtefunktionen
Remarks:
Using Information about Uncertainty of h Beschreibung der Schätzunsicherheit durch Dichtefunktionen
Using Information about Uncertainty of h Beschreibung der Schätzunsicherheit durch Dichtefunktionen
Remarks: (a) Falls sich die Dichtefunktionen nicht überlappen, würde derjenige Knoten gewählt, für den
Risk Measures Idee zur Berechnung der Evaluierungsreihenfolge:
Risk Measures Prinzip des Algorithmus R*δ
Bemerkungen und Fragen:
Risk Measures Verbesserungspotenzial einer aktuellen Lösung
Remarks:
Risk Measures Risikoschwelle und Risikokosten
Remarks:
Risk Measures Definition 75 (δ-Risikozulässigkeit)
Remarks:
Risk Measures Ausgangspunkt sind Dichtefunktionen für die Zufallsvariable fn+ eines Knoten n in
Risk Measures Risk Measures mit der Struktur R(C) = %[C − f +]
Remarks:
Risk Measures Beispiel
Risk Measures Beispiel
Risk Measures Beispiel
Risk Measures Beispiel
Risk Measures Beispiel
Risk Measures Beispiel
Risk Measures Theorem 77 (δ-Risikozulässigkeit von 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