38
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

Dynamic variable ordering in graph based backjumping algorithms for csps

Pages 167-186 | Received 20 Jul 1999, Published online: 20 Mar 2007
 

Abstract

Constraint Satisfaction Problems (CSPs) belong to the class of NP-Complete problems. Backtracking algorithm is generally used for solving these problems. However, it is not very useful as the class of problems it can solve within practical resource limits is small. Researchers have developed a large number of algorithms for enhancing the performance of backtracking algorithm. The Graph Based Backjumping (GBJ) algorithm proposed by Dechter [2] improves its performance by using the knowledge extracted from the graphical representation of CSPs called the constraint graph. That is, whenever a dead-end occurs at a particular variable X, the algorithm backs up to the most recent variable connected to X in the graph. This avoids the algorithm from performing redundant consistency checks which is one of the measures of performance for CSPs. Prosser [18] has proposed the hybrids of this algorithm namely the Backmarking with GBJ (BM-GBJ) and Forward Checking with GBJ (FC-GBJ) as further improvements of GBJ. P. V. Run [ 2] has proposed a methodology for implementing the Dynamic Variable Ordering (DVO) [9,11] in tree search algorithms and have shown that it results in a significant improvements in many of them. In this paper, we have investigated the implementation of Dynamic Variable Ordering (DVO) heuristic of instantiating next the variable with the Minimum Remaining Values (MRV) in the graph based backjumping algorithms. The three new algorithms developed are GBJvar, BM-GBJvar and FC-GBJvar. The empirical performance of these algorithms with and without DVO on Zebra problem, TV-queens problems and on random CSPs are tested. Our results demonstrate that without DVO, BM-GBJ is the best algorithm than GBJ and FC-GBJ in all the problems tested. However, when DVO is implemented in them then FC-GBJvar is found to be the best algorithm to solve all the problem.

C.R. Categories:

[email protected]

[email protected]

Notes

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.