摘要:

Search is fundamental to artificial intelligence (AI) and numerous sophisticated search methods have been developed. We present a general, simple model of search processes and use it to analytically determine some typical behavior when applied to large problems. In particular, this identifies abrupt changes in overall search cost as small improvements are made in the underlying method. We also examine the robustness of this model's predictions in a range of more realistic cases. More generally, we introduce a criterion for determining when average case results reflect typical behavior which allows the method developed here to be used for investigating other large‐scale behaviors of complex AI system

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1993.tb00307.x

出版商:Blackwell Publishing Ltd    

年代:1993

数据来源: WILEY

摘要:

The basic algorithms involved in reason maintenance in the standard ATMS is known to have a computational complexity that is exponential in the worst case. Yet, also in average‐case problem solving, the ATMS often lays claim to a major part of the computational effort spent by a problem solver/ATMS system. In this paper, we argue that within the limits of the worst‐case computational complexity, it is possible to improve on the average‐case complexity of reason maintenance and query processing by eliminating computation that is of no relevance to the problem solver's performance. To this purpose, we present a set of algorithms designed to control the effort spent by the ATMS on label updating. The basic idea underlying these algorithms is that of lazy evaluation: labels are not automatically maintained on all datums but are computed only when needed (either directly or indirectly) by the problem solver. The algorithms have been implemented in theLazyRMSwith which we have experimented in the context of model‐based diagnosis; our experiments show a substantial saving in the computational effort spent on reason main

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1993.tb00308.x

出版商:Blackwell Publishing Ltd    

年代:1993

数据来源: WILEY

摘要:

We define anargument systemto be a pair consisting of a set ofinference rulesand a set ofcompleteness conditions.Inference rules are used to buildarguments.Completeness conditions are used to defineargument structures,which are sets of arguments supporting belief sets. We reformulate Reiter's default logic as special argument systems. This enables us, among other things, to apply the negation‐as‐failure rule to general default theories. We also speculate on some other potential uses of our argument syst

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1993.tb00309.x

出版商:Blackwell Publishing Ltd    

年代:1993

数据来源: WILEY

摘要:

It might be said that there are five basic tree search algorithms for the constraint satisfaction problem (csp), namely, naive backtracking (BT), backjumping (BJ), conflict‐directed backjumping (CBJ), backmarking (BM), and forward checking (FC). In broad terms, BT, BJ, and CBJ describe different styles of backward move (backtracking), whereas BT, BM, and FC describe different styles of forward move (labeling of variables). This paper presents an approach that allows base algorithms to be combined, giving us new hybrids. The base algorithms are described explicitly, in terms of a forward move and a backward move. It is then shown that the forward move of one algorithm may be combined with the backward move of another, giving a new hybrid. In total, four hybrids are presented: backmarking with backjumping (BMJ), backmarking with conflict‐directed backjumping (BM‐CBJ), forward checking with backjumping (FC‐BJ), and forward checking with conflict‐directed backjumping (FC‐CBJ). The performances of the nine algorithms (BT, BJ, CBJ, BM, BMJ, BM‐CBJ, FC, FC‐BJ, FC‐CBJ) are compared empirically, using 450 instances of the ZEBRA problem, and it is shown that FC‐CBJ is by far the best of the

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1993.tb00310.x

出版商:Blackwell Publishing Ltd    

年代:1993

数据来源: WILEY