Can I read Average-case Analysis of Best-first Search in Two Representative Directed Acyclic Graphs on EtoBox?

Average-case Analysis of Best-first Search in Two Representative Directed Acyclic Graphs by Anup K. Sen; Amitava Bagchi; Weixiong Zhang is a Computer Science article available to read on EtoBox.

What is Average-case Analysis of Best-first Search in Two Representative Directed Acyclic Graphs about?

Many problems that arise in the real world have search spaces that are graphs rather than trees. Understanding the properties of search algorithms and analyzing their performance have been major objectives of research in AI. But most published work on the analysis of search algorithms has been focused on tree search, and comparatively little has been reported on graph search. One of the major obstacles in analyzing average-case complexity of graph search is that no single graph can serve as a suitable representative of graph search problems. In this paper we propose one possible approach to analyzing graph search. We take two problem domains for which the search graphs are directed acyclic graphs of similar structure, and determine the average case performance of the best-first search algorithm A \* on these graphs. The first domain relates to one-machine job sequencing problems in which a set of jobs must be sequenced on a machine in such a way that a penalty function is minimized. The second domain concerns the Traveling Salesman Problem. Our mathematical formulation extends a technique that has been used previously for analyzing tree search. We demonstrate the existence of a gap

Who reads Average-case Analysis of Best-first Search in Two Representative Directed Acyclic Graphs?

Author

Anup K. Sen; Amitava Bagchi; Weixiong Zhang

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0004-3702)

Published

2004

Language

EN

Field

Computer Science (Physical Sciences)