Average-case analysis of best-first search in two representative directed acyclic graphs

DOI10.1016/j.artint.2004.01.001zbMath1085.68676OpenAlexW2054543844MaRDI QIDQ814592

Amitava Bagchi, Weixiong Zhang, Anup K. Sen

Publication date: 7 February 2006

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

Full work available at URL: https://doi.org/10.1016/j.artint.2004.01.001

zbMATH Keywords

Traveling salesman\(\text{A}^*\)Average-case complexityGraph searchJob sequencing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic analysis of the complexity of A*
• Enhanced \(A^{*}\) algorithms for multiple alignments: optimal alignments for several sequences and k-opt approximate alignments for large cases
• The traveling salesman problem and its variations
• Searching for an optimal path in a tree with random costs
• Cost-error relationships in A* tree-searching
• Generalized best-first search strategies and the optimality of A*
• The Multiple Sequence Alignment Problem in Biology
• The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution
• Technical Note—On the Expected Performance of Branch-and-Bound Algorithms
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• The traveling-salesman problem and minimum spanning trees: Part II
• Performance of linear-space search algorithms
• Time complexity of iterative-deepening-\(A^{*}\)
• Algorithm for optimal winner determination in combinatorial auctions

This page was built for publication: Average-case analysis of best-first search in two representative directed acyclic graphs