Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
A solution to the GHI problem for best-first search
Autore:
Breuker, DM; van den Herik, HJ; Uiterwijk, JWHM; Allis, LV;
Indirizzi:
Univ Maastricht, Dept Comp Sci, NL-6200 MD Maastricht, Netherlands Univ Maastricht Maastricht Netherlands NL-6200 MD aastricht, Netherlands Quintiq BV, NL-5213 AV Shertogenbosch, Netherlands Quintiq BV Shertogenbosch Netherlands NL-5213 AV togenbosch, Netherlands
Titolo Testata:
THEORETICAL COMPUTER SCIENCE
fascicolo: 1-2, volume: 252, anno: 2001,
pagine: 121 - 149
SICI:
0304-3975(20010206)252:1-2<121:ASTTGP>2.0.ZU;2-Z
Fonte:
ISI
Lingua:
ENG
Soggetto:
MINIMAX;
Keywords:
graph-history interaction (GHI) problem; best-first search; base-twin algorithm (BTA);
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
20
Recensione:
Indirizzi per estratti:
Indirizzo: Uiterwijk, JWHM Univ Maastricht, Dept Comp Sci, POB 616, NL-6200 MD Maastricht, Netherlands Univ Maastricht POB 616 Maastricht Netherlands NL-6200 MD
Citazione:
D.M. Breuker et al., "A solution to the GHI problem for best-first search", THEOR COMP, 252(1-2), 2001, pp. 121-149

Abstract

Best-first search algorithms usually amalgamate identical nodes for optimization reasons, meanwhile transforming the search tree into a search graph. However, identical nodes may represent different search states, e.g., due to a difference of history. So, in a search graph a node's value may be dependent on the path leading to it. This implies that different paths may result in different values. Therefore, it is difficult to determine the value of any node unambiguously. The problem is known as the graph-history-interaction (GHI) problem. This paper provides a solution for best-first search. First, we give a precise formulation of the problem. Then, for best-first search and for other searches, we review earlier proposals to overcome the problem. Next, our solution is given in detail. Here we introduce the notionof twin nodes, enabling a distinction of nodes according to their history. The implementation, called base-twin algorithm (BTA), is performed for pn search, a best-first search algorithm. It is generally applicable to other best-first search algorithms. Experimental results in the field of computerchess confirm the claim that the GHI problem has been solved for best-first search. (C) 2001 Elsevier Science B.V. All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 10/08/20 alle ore 08:23:41