文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Constraint Satisfaction Search
侵权投诉

Constraint Satisfaction Search

For the past thirty five years artificial intelligence researchers have been studying heuristic search techniques. People writing AI programs have had strong intuitions about what it means for a program to search. Intuitively they classified programs accor

Lecture Notes for 6.824, Arti cial Intelligence c 1992 David McAllester, all rights reserved

Rev. October, 1992

Constraint Satisfaction Search For the past thirty ve years arti cial intelligence researchers have been studying heuristic search techniques. People writing AI programs have had strong intuitions about what it means for a program to search. Intuitively they classi ed programs according to the kinds of search performed. Certain programs, such as matrix multiplication routines, did no search whatsoever. Other programs searched for solutions to a xed nite set of constraints. Others searched for paths in graphs, or for strategies in game trees, or for proofs in formal inference systems. The intuitive classi cation of search programs seems to roughly correspond to complexity classes. The no-search procedures correspond to the complexity class P. Constraint satisfaction search procedures correspond to the complexity class NP, graph search and game search procedures to the class PSPACE, and search in theorem proving to the class of recursively enumerable functions. This chapter discusses heuristic techniques for solving search problems of the simplest type| constraint satisfaction problems. Heuristic techniques for other forms of search are discussed in later chapters.

1 Constraint Satisfaction Problems Intuitively, a search problem involves nding an object that satis es a given speci cation. A classic example is the eight queens problem. This is the problem of placing eight queens on a chess board so that no two queens attack each other, i.e., so that no single row, column, or diagonal contains more than one queen. This problem can be solved (ine ciently) by a\generate and test" program that rst generates a list of all the possible ways eight queens can be placed a chess board and then tests each possibility to see if it is a solution to the problem. 1

Another example is the SAT problem. This is the problem of determining

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email