Search Algorithms Benno Stein
Contents I. Introduction
Objectives
Literature Books on Heuristic Search
Literature Further Reading
Literature Further Reading
Literature Further Reading
Literature Further Reading
Literature Further Reading
Literature Further Reading
Chapter S:I I. Introduction
Examples for Search Problems 8-Queens Problem: Local Search
Examples for Search Problems 8-Queens Problem: Local Search
Examples for Search Problems 8-Queens Problem: Local Search
Examples for Search Problems 8-Queens Problem: Local Search
Examples for Search Problems 8-Queens Problem: Local Search
Remarks:
Examples for Search Problems 8-Queens Problem: Local Search
Examples for Search Problems 8-Queens Problem: Solution Construction
Examples for Search Problems 8-Queens Problem: Solution Construction
Examples for Search Problems 8-Queens Problem: Solution Construction
Examples for Search Problems 8-Queens Problem: Solution Construction
Examples for Search Problems 8-Queens Problem: Solution Construction
Remarks:
Examples for Search Problems 8-Queens Problem: Solution Construction
Examples for Search Problems 8-Queens Problem
Examples for Search Problems 8-Queens Problem: Solution Construction
Remarks:
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
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
Remarks:
Examples for Search Problems Traveling Salesman Problem
Remarks:
Examples for Search Problems Minimum Spanning Tree Problem
Examples for Search Problems Minimum Spanning Tree
Remarks:
Examples for Search Problems MaxSAT Problem
Examples for Search Problems MaxSAT Problem
Examples for Search Problems MaxSAT Problem
Remarks:
Examples for Search Problems MaxSAT Problem
Examples for Search Problems MaxSAT Problem
Examples for Search Problems Road-Map Problem
Examples for Search Problems Road-Map Problem
Examples for Search Problems Road-Map 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 Blocks-World Planning
Examples for Search Problems Blocks-World Planning
Examples for Search Problems Blocks-World Planning
Remarks:
Chapter S:I I. Introduction
Search-Problem Abstraction Local Search Approach
Search Problem Abstraction Local Search Approach
Remarks:
Search Problem Abstraction Solution Construction
Search Problem Abstraction Solution Construction
Remarks:
Remarks:
Search Problem Abstraction Solution Construction: Abstract Problem Setting
Search Problem Abstraction Questions in Problem Solving as Search
Chapter S:I I. Introduction
Examples for AND-OR Search Problems The Counterfeit Coin Problem
Examples for AND-OR Search Problems The Counterfeit Coin Problem
Remarks:
Examples for AND-OR Search Problems The Counterfeit Coin Problem
Remarks:
Examples for AND-OR Search Problems The Counterfeit Coin Problem
Examples for AND-OR Search Problems The Counterfeit Coin Problem
Examples for AND-OR Search Problems Tic-Tac-Toe Game
Examples for AND-OR Search Problems Tic-Tac-Toe Game
Examples for AND-OR Search Problems Tic-Tac-Toe Game
Examples for AND-OR Search Problems Tic-Tac-Toe Game
Examples for AND-OR Search Problems Tic-Tac-Toe Game
Examples for AND-OR Search Problems UNSAT Problem
Examples for AND-OR Search Problems UNSAT Problem
Remarks:
Examples for AND-OR Search Problems UNSAT Problem
Search Problem Abstraction Recap: Questions in Problem Solving as Search
Chapter S:II II. Basic Search Algorithms
Systematic Search Types of Problems
Systematic Search Types of Problems
Remarks:
Systematic Search Modeling Search as Problem Solving
Systematic Search Abstract Framework for Search as Problem Solving
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:
Chapter S:II II. Basic Search Algorithms
Graph Theory Basics Definition 2 (Directed Graph)
Graph Theory Basics Definition 2 (Directed Graph)
Remarks:
Graph Theory Basics Definition 3 (Path, Vertex Types, Outdegree, Local Finiteness)
Graph Theory Basics Definition 3 (Path, Vertex Types, Outdegree, Local Finiteness)
Remarks:
Graph Theory Basics Definition 4 (Directed Tree, Uniform Tree)
Remarks:
Chapter S:II II. Basic Search Algorithms
State Space Search Modeling Problem Solving as Path-Finding Problem
State Space Search Modeling Problem Solving as Path-Finding Problem
Remarks:
State Space Search Modeling Problem Solving as Path-Finding 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 Graph Representation
State Space Search Graph Representation
Remarks:
State Space Search Graph Algorithms and Back-pointer Structures
State Space Search Graph Algorithms and Back-pointer Structures
State Space Search Graph Algorithms and Back-pointer Structures
State Space Search Illustration of Back-pointer Usage
State Space Search Illustration of Back-pointer Usage
State Space Search Illustration of Back-pointer Usage
State Space Search Illustration of Back-pointer Usage
State Space Search Illustration of Back-pointer Usage
Remarks:
State Space Search Definition 7 (Node Generation, Node Expansion)
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 Algorithm:
Remarks:
Remarks: (continued)
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 Important Properties of Search Algorithms
Remarks:
State Space Search Lemma 10 (Termination of Basic-OR for Finite Graphs without Cycles)
State Space Search Lemma 11 (Completeness of Basic-OR for Finite Graphs without Cycles)
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 Basic-Opt-OR(s, successors, ?, cost)
Remarks:
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 II. Basic Search Algorithms
Depth-First Search (DFS) Depth-first search is an uninformed (systematic) search strategy.
Remarks:
Depth-First Search Specification of DFS Algorithm Family
Depth-First Search Core Version of DFS
Remarks:
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:
Depth-First Search Discussion
Depth-First Search Depth-limited DFS
Remarks:
Depth-First Search Iterative Deepening Framework using DL-DFS
Depth-First Search DFS with Pruning
Remarks:
Depth-First Search Discussion
Remarks:
Depth-First Search Example: DFS for Optimization (see Basic-OR for Optimization)
Depth-First Search Example: DFS for Optimization (see Basic-OR for Optimization)
Depth-First Search Example: DFS for Optimization (see Basic-OR for Optimization)
Chapter S:II II. Basic Search Algorithms
Backtracking (BT) Backtracking is a variant of depth-first search.
Remarks:
Backtracking Algorithm:
Backtracking Discussion
Backtracking Discussion
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:
Chapter S:II II. Basic Search Algorithms
Breadth-First Search (BFS) Breadth-first search is an uninformed, systematic search strategy.
Remarks:
Breadth-First Search Specification of BFS Algorithm Family
Breadth-First Search Core Version of BFS
Breadth-First Search Example: 4-Queens Problem
Breadth-First Search Example: 4-Queens Problem
Breadth-First Search Discussion
Breadth-First Search Discussion
Breadth-First Search BFS with Pruning
Breadth-First Search Depth-limited BFS
Breadth-First Search Corollary 13 (Termiantion of Basic-BFS for Finite Graphs without Cycles)
Breadth-First Search Example: BFS for Optimization (see Basic-OR and DFS for Optimization)
Breadth-First Search Example: BFS for Optimization (see Basic-OR and DFS for Optimization)
Chapter S:II II. Basic Search Algorithms
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:
Chapter S:II II. Basic Search Algorithms
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 Solved Labeling Using DFS
Depth-First Search of AND-OR Graphs Solved Labeling Using DFS
Depth-First Search of AND-OR Graphs Solved Labeling Using 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:
Chapter S:II II. Basic Search Algorithms
AND-OR Graph Search Basics Solution-Tree Bases in AND-OR Graphs
AND-OR Graph Search Basics Requirements for an Algorithmization of AND-OR Graph Search
Remarks:
AND-OR Graph Search Basics Generic Schema for AND-OR-Graph Tree Search Algorithms
AND-OR Graph Search Basics Algorithm:
AND-OR Graph Basics Generic_AND-OR_Tree(s, successors, ?) [Generic_OR]
Remarks:
Chapter S:II II. Basic Search Algorithms
AND-OR Graph Search Efficient Storage of Solution-Tree Bases
AND-OR Graph Search Efficient Storage of Solution-Tree Bases
AND-OR Graph Search Efficient Storage of Solution-Tree Bases
AND-OR Graph Search Identifying Solution Trees and Solution-Tree Bases
AND-OR Graph Search Algorithm:
AND-OR Graph Search Basic_AND-OR_Tree(s, successors, is_solved) [Basic_OR]
AND-OR Graph Search Illustration of Basic_AND-OR
AND-OR Graph Search Illustration of Basic_AND-OR_Tree
AND-OR Graph Search Illustration of Basic_AND-OR_Tree
AND-OR Graph Search Illustration of Basic_AND-OR_Tree
AND-OR Graph Search Illustration of Basic_AND-OR_Tree
AND-OR Graph Search Illustration of Basic_AND-OR_Tree
AND-OR Graph Search Illustration of Basic_AND-OR_Tree
AND-OR Graph Search Illustration of Basic_AND-OR_Tree
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 Illustration of Solution Graphs and Solution Bases
AND-OR Graph Search Illustration of Solution Graphs and Solution Bases
AND-OR Graph Search Illustration of Solution Graphs and Solution Bases
AND-OR Graph Search Illustration of Solution Graphs and Solution Bases
AND-OR Graph Search Illustration of Solution Graphs and Solution Bases
AND-OR Graph Search Illustration of Solution Graphs and Solution Bases
AND-OR Graph Search Generic Schema for AND-OR-Graph Search Algorithms
AND-OR Graph Search Algorithm:
AND-OR Graph Search Generic_AND-OR(s, successors, ?) [Generic_AND-OR_Tree] [Generic_OR]
Remarks:
AND-OR Graph Search Efficient Storage of Solution Bases
AND-OR Graph Search Efficient Storage of Solution Bases
AND-OR Graph Search Efficient Storage of Solution Bases
AND-OR Graph Search Efficient Storage of Solution Bases
AND-OR Graph Search Foundation of Basic AND-OR Graph Search
AND-OR Graph Search Foundation of AND-OR Graph Search
Remarks:
AND-OR Graph Search Algorithm:
AND-OR Graph Search Basic_AND-OR(s, successors, is_solved) [Basic_OR]
Remarks:
AND-OR Graph Search Illustration of Basic_AND-OR
AND-OR Graph Search Illustration of Basic_AND-OR
AND-OR Graph Search Illustration of Basic_AND-OR
AND-OR Graph Search Illustration of Basic_AND-OR
AND-OR Graph Search Illustration of Basic_AND-OR
AND-OR Graph Search Illustration of Basic_AND-OR
AND-OR Graph Search Illustration of Basic_AND-OR
AND-OR Graph Search Illustration of Basic_AND-OR
Chapter S:III III. Informed Search
Best-First Search Basics “To enhance the performance of AI’s programs, knowledge [about the problem
Best-First Search “To enhance the performance of AI’s programs, knowledge [about the problem
Best-First Search “To enhance the performance of AI’s programs, knowledge [about the problem
Best-First Search Basics “To enhance the performance of AI’s programs, knowledge [about the problem
Best-First Search Basics “The promise of a node is estimated numerically by a heuristic evaluation
Best-First Search Basics “The promise of a node is estimated numerically by a heuristic evaluation
Remarks:
Best-First Search Basics Generic Schema for Best-First Algorithms
Remarks:
Chapter S:III III. Informed Search
Best-First Search Algorithms Notation for Evaluation Functions
Best-First Search Algorithms Notation for Evaluation Functions
Best-First Search Algorithms Basic Principles for an Algorithmization of Best-First Search
Remarks:
Best-First Search Algorithms (Compare ::::::
Remarks:
Best-First Search Algorithms Uniform-Cost Search (UCS) as Variant of Basic-BF
Remarks:
Best-First Search Algorithms Example: Uniform-Cost Search for Optimization
Best-First Search Algorithms Example: Uniform-Cost Search for Optimization
Best-First Search Algorithms Uniform-Cost Search is an uninformed (systematic) search strategy.
Best-First Search Algorithms Delayed Termination: Basic-BF for Optimization
Best-First Search Algorithms (Compare BF∗ .)
Remarks:
Best-First Search Algorithms Space Efficiency of Basic-BF and Basic-BF*
Best-First Search Algorithms Implementing Path Discarding in Basic-BF
Remarks:
Remarks:
Best-First Search Algorithms Path Discarding for a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Remarks:
Best-First Search Algorithms Re-evaluation of a Node n0
Best-First Search Algorithms Re-evaluation of a Node n0
Remarks:
Best-First Search Algorithms BF∗ (s, successors, ?, f )
Best-First Search Algorithms Definition 21 (Cycle-Averse Evaluation Function)
Remarks:
Best-First Search Algorithms Irrevocable Path Discarding in BF
Best-First Search Algorithms Irrevocable Path Discarding in BF
Best-First Search Algorithms Definition 22 (Order-preserving Evaluation Function)
Best-First Search Algorithms Definition 23 (Optimistic Evaluation Function)
Remarks:
Best-First Search Algorithms Advanced Principles for an Algorithmization of Best-First Search for Optimization
State Space Search Important Properties of Search Algorithms
State Space Search Lemma 25 (Admissibility of BF* for Finite Graphs)
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 For a known solution path, the solution cost must be determined.
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
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 used 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
Chapter S:III III. Informed Search
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:
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 Examples of simple path cost functions based on non-negative edge cost values
Evaluation of State-Space Graphs Taxonomy of Best-First Algorithms
Chapter S:III III. Informed Search
Algorithm A* ∗
Algorithm A* A∗ (s, successors, ?, c, h) // A special case of :::::
Remarks:
Algorithm A* Example: Knight Moves Search a shortest sequence of knight moves leading from s to X.
Algorithm A* Example: Knight Moves Search a shortest sequence of knight moves leading from s to X.
Algorithm A* Example: Knight Moves
Algorithm A* Example: Knight Moves
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* 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 A*, where h = 0 and
BF* Variants For trees G: Depth-first search is a special case of A*, where h = 0 and
BF* Variants For trees G: Depth-first search is a special case of A*, where h = 0 and
BF* Variants For trees G: Depth-first search is a special case of A*, where h = 0 and
Remarks:
BF* Variants Greedy best-first search is a special case of BF*, where f (n) = h(n), for all nodes n.
BF* Variants Greedy best-first search is a special case of BF*, where f (n) = h(n), for all nodes n.
BF* Variants Greedy best-first search is a special case of BF*, where f (n) = h(n), for all nodes n.
BF* Variants Greedy best-first search is a special case of BF*, where f (n) = h(n), for all nodes n.
BF* Variants OPEN List Size Restriction:: Hill-Climbing (HC)
Remarks:
BF* Variants OPEN List Size Restriction: Best-First Beam Search [Rich & Knight 1991]
BF* Variants Algorithm:
Remarks:
Remarks:
Chapter S:III III. 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
Remarks:
Hybrid Strategies Strategy 3: Extended Expansion
Hybrid Strategies Strategy 3: Extended Expansion
Remarks:
Hybrid Strategies Strategy 4: Focal Search [Ibaraki 1978]
Remarks:
Hybrid Strategies Strategy 5: Staged Search [Nilson 1971]
Remarks:
Hybrid Strategies Strategy 6: Iterative Deepening A* – IDA* [Korf 1985]
Hybrid Strategies f -value-limited DFS
Hybrid Strategies Algorithm:
Remarks:
Chapter S:III III. Informed Search
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: IF ( ⊥ (n0 )
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*
Chapter S:III III. Informed Search
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
Chapter S:III III. Informed Search
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:
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:
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:
Chapter S:IV IV. Search Space Representation
Systematic Search Search Building Blocks
Systematic Search Search Building Blocks
Systematic Search Definition 1 (Systematic Control Strategy, Systematic Search)
Remarks:
Systematic Search Categorization of Heuristic [Problem Solving] Methods
Systematic Search Categorization of Heuristic [Problem Solving] Methods
Chapter S:IV IV. Search Space Representation
Search Space Encoding Encoding of Solution Candidates
Search Space Encoding Encoding of Solution Candidates
Remarks:
Search Space Encoding Applicable Heuristic Problem Solving Methods
Search Space Encoding OPEN List Restriction: Hill-Climbing (HC)
Search Space Encoding Hill-Climbing
Search Space Encoding Hill-Climbing
Search Space Encoding Hill-Climbing: Discussion
Search Space Encoding Hill-Climbing: Discussion
Search Space Encoding Hill-Climbing: Discussion
Remarks:
Search Space Encoding Encoding of Solution Candidates
Search Space Encoding Encoding of Solution Candidates
Remarks:
Remarks: (continued)
Search Space Encoding Encoding of Solution Candidates
Remarks:
Search Space Encoding Subset Encoding for the 8-Queens Problem
Search Space Encoding Subset Encoding for the 8-Queens Problem
Search Space Encoding Subset Encoding for the 8-Puzzle Problem
Search Space Encoding Subset Encoding for the 8-Puzzle Problem
Remarks:
Chapter S:IV IV. Search Space Representation
State-Space Representation Subset Encoding in Search
State-Space Representation Subset Encoding in Search
Remarks:
State-Space Representation Subset Encoding in Search
State-Space Representation Subset Encoding in Search
Remarks:
State-Space Representation Traveling Salesman Problem
State-Space Representation Traveling Salesman Problem
State-Space Representation Summary: Solving Search Problems by State Space Search
Remarks:
State-Space Representation 8-Queens Problem
State-Space Representation 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:IV IV. Search Space Representation
Problem-Reduction Representation Problem Solving: Constructing Solutions
Problem-Reduction Representation Disadvantage of State-Space Search
Problem-Reduction Representation Applicable Heuristic Problem Solving Methods
Problem-Reduction Representation Problem Solving: Solution Steps
Problem-Reduction Representation Problem Solving Steps as Different Link Types
Remarks:
Problem-Reduction Representation Counterfeit Problem
Problem-Reduction Representation Counterfeit Problem
Remarks:
Problem-Reduction Representation The Different Node types
Remarks:
Problem-Reduction Representation Search Building Blocks [State-Space]
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 Hypergraphs
Chapter S:IV IV. Search Space Representation
Choosing a Representation Problem-Reduction Graphs with Alternating Node Types
Remarks:
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
Remarks:
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 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:IV IV. Search Space Representation
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
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:V V. Formal Properties of A*
Remarks (outline) :
Properties of Search Space Graphs Properties for Node Expansion
Properties of Search Space Graphs Additional Required Properties
Properties of Search Space Graphs Additional Required Properties
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 PropA∗ (G): Required Properties of G for A* Search
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
Chapter S:V V. Formal Properties of A*
Auxiliary Concepts Search Space Graph versus Traversal Tree
Remarks:
Auxiliary Concepts Illustration of Traversal Trees
Remarks:
Auxiliary Concepts Definition 56 (Specific Paths and Functions)
Remarks:
Auxiliary Concepts Definition 56 (Specific Paths and Functions
Remarks:
Auxiliary Concepts Definition 56 (Specific Paths and Functions
Remarks:
Auxiliary Concepts Definition 56 (Specific Paths and Functions
Auxiliary Concepts Definition 56 (Specific Paths and Functions
Remarks:
Auxiliary Concepts Definition 56 (Specific Paths and Functions
Remarks:
Auxiliary Concepts Lemma 57 (Basic Observations)
Remarks:
Chapter S:V V. Formal Properties of A*
Roadmap Important Lemmas and Theorems
Chapter S:V V. Formal Properties of A*
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. Since G has PropA∗ (G), the evaluation function f is cycle-avers. Therefore, we only have to
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 61 (Completeness for Finite Graph)
Completeness of A* Lemma 61 (Completeness for Finite Graph)
Remarks:
Completeness of A* Lemma 62 (Shallowest OPEN Node on Path)?
Completeness of A* Lemma 62 (Shallowest OPEN Node on Path)?
Completeness of A* Theorem 63 (Completeness)
Completeness of A* Theorem 63 (Completeness)
Remarks:
Chapter S:V V. Formal Properties of A*
Admissibility of A* Lemma 64 (Node Cost on Optimum Path)
Admissibility of A* Lemma 64 (Node Cost on Optimum Path)
Remarks:
Admissibility of A* Corollary 65 (Implications of Lemma 64)
Admissibility of A* Definition 66 (Admissibility of h)
Admissibility of A* Corollary 67 (Shallowest OPEN Node on Optimum Path [Lemma 62])?
Admissibility of A* Corollary 67 (Shallowest OPEN Node on Optimum Path [Lemma 62])?
Remarks: ? The Lemma states that nodes on optimum paths are reached by A* with optimum cost when
Admissibility of A* Lemma 68 (C ∗-Bounded OPEN Node)
Admissibility of A* Lemma 68 (C ∗-Bounded OPEN Node)
Remarks:
Admissibility of A* Theorem 69 (Admissibility [Hart, Nilsson, Raphael 1968,1972])
Admissibility of A* Theorem 69 (Admissibility [Hart, Nilsson, Raphael 1968,1972])
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 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:
Chapter S:V V. Formal Properties of A*
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 79 (Consistency Condition)
Monotone Heuristic Functions Definition 79 (Consistency Condition)
Remarks:
Monotone Heuristic Functions Theorem 81 (Consistency Equivalent to Monotonicity)
Monotone Heuristic Functions Theorem 81 (Consistency Equivalent to Monotonicity)
Monotone Heuristic Functions Illustration of a Monotone h
Monotone Heuristic Functions Illustration of a Monotone h
Monotone Heuristic Functions Theorem 82 (Monotone Heuristic Functions)
Monotone Heuristic Functions Theorem 82 (Monotone Heuristic Functions)
Remarks:
Monotone Heuristic Functions Theorem 83 (No Reopening)
Monotone Heuristic Functions Theorem 83 (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 84 (Non-Decreasing f -Values)
Monotone Heuristic Functions Theorem 84 (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 86 (Largely Dominating Algorithms)
Monotone Heuristic Functions Definition 86 (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:
Chapter S:VI VI. Relaxed Models
ε-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 92 (WA* and DWA* are variants of A*ε)
ε-Admissible Speedup Versions of A* Lemma 92 (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
Chapter S:VI VI. Relaxed Models
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 96 (Risk Measure)
Remarks:
Risk Measures Definition 98 (δ-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
S:VI-73
Risk Measures Example
S:VI-75
Risk Measures Example
Risk Measures Example
Risk Measures Example
Risk Measures δ-Risk-Admissibility
Risk Measures δ-Risk-Admissibility
Risk Measures δ-Risk-Admissibility
Remarks:
Kapitel 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
Kapitel S:VI VI. Relaxed Models
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 Systematisches Relaxieren von Suchproblemen
Automatische Generierung von Heuristiken Einfache Probleme: kompositionale Probleme
Automatische Generierung von Heuristiken Einfache Probleme: semikompositionale Probleme
Kapitel S:VI VI. Relaxed Models
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 103 (Game Tree)
Remarks:
Game Playing Introduction Illustration:
Game Playing Introduction Illustration:
Game Playing Introduction Definition 104 (Status Labeling Procedure)
Remarks:
Game Playing Introduction Definition 105 (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:
Chapter S:VII VII. Game Playing
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 Handling Huge or Even Infinite Game Trees
Evaluation Functions for Game Trees Definition 107 (Minimax Rule)
Remarks:
Chapter S:VII VII. Game Playing
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 Intuition of α-Bounds
Remarks:
Propagation Algorithms for Game Trees Intuition of β-Bounds
Remarks:
Propagation Algorithms for Game Trees The α-β-pruning scheme:
Remarks:
Propagation Algorithms for Game Trees Algorithm:
Propagation Algorithms for Game Trees
Remarks:
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA
Propagation Algorithms for Game Trees Example: Propagating evaluations with ALPHA-BETA