Thumbnail
Access Restriction
Subscribed

Author Bagchi, A. ♦ Mahanti, A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1985
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Three different approaches to heuristic search in networks are analyzed. In the first approach, as formulated initially by Hart, Nilsson, and Raphael, and later modified by Martelli, the basic idea is to choose for expansion that node for which the evaluation function has a minimum value. A second approach has recently been suggested by Nilsson. In this method, in contrast to the earlier one, a node that is expanded once is not expanded again; instead, a “propagation” of values takes place. The third approach is an adaptation for networks of an AND/OR graph “marking” algorithm, originally due to Martelli and Montanari.Five algorithms are presented. Algorithms A and C illustrate the first approach; PropA and PropC, the second one; and MarkA, the third one. The performances of these algorithms are compared for both admissible and inadmissible heuristics using the following two criteria: (i) cost of the solution found; (ii) time of execution in the worst case, as measured by the number of node expansions (A, C), or node “selections” (PropA, PropC), or arc “markings” (MarkA).The relative merits and demerits of the algorithms are summarized and indications are given regarding which algorithm to use in different situations.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1985-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 32
Issue Number 1
Page Count 27
Starting Page 1
Ending Page 27


Open content in new tab

   Open content in new tab
Source: ACM Digital Library