Searching for an optimal path in a tree with random costs

DOI10.1016/S0004-3702(83)80006-XzbMath0507.68034OpenAlexW2084077236MaRDI QIDQ1837534

Judea Pearl, Richard M. Karp

Publication date: 1983

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0004-3702(83)80006-x

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Search theory (90B40) Applications of branching processes (60J85) Artificial intelligence (68T99)

Related Items

Search cost for a nearly optimal path in a binary tree, Downward refinement and the efficiency of hierarchical problem solving, Efficient approximation of branching random walk Gibbs measures, Real-time heuristic search, An incremental negamax algorithm, Greedy Search on the Binary Tree with Random Edge-Weights, Best-first minimax search, Bounded branching process and and/or tree evaluation, Phase transitions and the search problem, A study of complexity transitions on the asymmetric traveling salesman problem, Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems, HEURISTIC SEARCH UNDER CONTRACT, Total progeny in killed branching random walk, On look-ahead and pathology in decision tree learning, Unnamed Item, Iterative state-space reduction for flexible computation, Performance of linear-space search algorithms, Performance of linear-space search algorithms, Limit distributions for minimal displacement of branching random walks, Average-case analysis of best-first search in two representative directed acyclic graphs, Bayesian A* Tree Search with Expected O(N) Node Expansions: Applications to Road Tracking

Cites Work

• Minimal displacement of branching random walk
• The Galton-Watson process with infinite mean
• Unnamed Item
• Unnamed Item
• Unnamed Item