SYNTHESIZING CONSTRAINT EXPRESSIONS

被引：205

作者：

FREUDER, EC

机构：

[1] Department of Mathematics and Computer Science, University of New Hampshire, Durham

来源：

COMMUNICATIONS OF THE ACM | 1978年 / 21卷 / 11期

关键词：

backtrack; combinatorial algorithms; constraint networks; constraint satisfaction; graph coloring; network consistency; relaxation; scene labeling; search;

D O I：

10.1145/359642.359654

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A constraint network representation is presented for a combinatorial search problem: finding values for a set of variables subject to a set of constraints. A theory of consistency levels in such networks is formulated, which is related to problems of backtrack tree search efficiency. An algorithm is developed that can achieve any level of consistency desired, in order to preprocess the problem for subsequent backtrack search, or to function as an alternative to backtrack search by explicitly determining all solutions. © 1978, ACM. All rights reserved.

引用

页码：958 / 966

页数：9

共 24 条

[1]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[2]

BARROW H, 1976, 121 STANF RES I AI C

[3]

Bobrow D. G., 1974, Computing Surveys, V6, P153, DOI 10.1145/356631.356632

[4] SEEING THINGS [J].

CLOWES, MB .

ARTIFICIAL INTELLIGENCE, 1971, 2 (01) :79-116

[5] REF-ARF - SYSTEM FOR SOLVING PROBLEMS STATED AS PROCEDURES [J].

FIKES, RE .

ARTIFICIAL INTELLIGENCE, 1970, 1 (1-2) :27-120

[6]

FREUDER EC, 1976, AI370 AI LAB MEM

[7]

GROSSMAN RW, 1976, TR158 MIT LAB COMP S

[8]

Horn BK., 1974, COMPUT GRAPH IMAGE P, V3, P277, DOI DOI 10.1016/0146-664X(74)90022-7

[9]

Huffman D. A., 1971, Machine Intelligence Volume 6, P295

[10] CONSISTENCY IN NETWORKS OF RELATIONS [J].

MACKWORTH, AK .

ARTIFICIAL INTELLIGENCE, 1977, 8 (01) :99-118

← 1 2 3 →