Actions for A Graph Based Backtracking Algorithm for Solving General CSPs

Email RIS file
Bookmark
Report an Issue

A Graph Based Backtracking Algorithm for Solving General CSPs

Author
Pang, Wanlin
Published
[2003].
Physical Description
1 electronic document
Additional Creators
Goodwin, Scott D.
Online Version

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Unclassified, Unlimited, Publicly available.
Free-to-read Unrestricted online access
Summary
Many AI tasks can be formalized as constraint satisfaction problems (CSPs), which involve finding values for variables subject to constraints. While solving a CSP is an NP-complete task in general, tractable classes of CSPs have been identified based on the structure of the underlying constraint graphs. Much effort has been spent on exploiting structural properties of the constraint graph to improve the efficiency of finding a solution. These efforts contributed to development of a class of CSP solving algorithms called decomposition algorithms. The strength of CSP decomposition is that its worst-case complexity depends on the structural properties of the constraint graph and is usually better than the worst-case complexity of search methods. Its practical application is limited, however, since it cannot be applied if the CSP is not decomposable. In this paper, we propose a graph based backtracking algorithm called omega-CDBT, which shares merits and overcomes the weaknesses of both decomposition and search approaches.
Other Subject(s)
Collection
NASA Technical Reports Server (NTRS) Collection.
Note
Document ID: 20060018392.
CAI '03 16th Canadian Conference on AI; 11-13 Jun. 2003; Nova Scotia; Canada.
Terms of Use and Reproduction
Copyright, Distribution as joint owner in the copyright.
View MARC record | catkey: 16003603