In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposi...In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposing an arcconsistency problem into a series of smaller ones and trying to solve them in sequence.In this way, not only the space complexity but also the time complexity can be reduced. The reason for this is that due to the ahead of time performed inconsistencypropagation (in the sense that some of them are executed before the entire inconsis-tency checking has been finished), each constraint subnetwork will be searched with agradually shrunk domain. In addition, the technique of AC-6 can be integrated intoour algorithm, leading to a further decrease in computational complexity.展开更多
文摘In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposing an arcconsistency problem into a series of smaller ones and trying to solve them in sequence.In this way, not only the space complexity but also the time complexity can be reduced. The reason for this is that due to the ahead of time performed inconsistencypropagation (in the sense that some of them are executed before the entire inconsis-tency checking has been finished), each constraint subnetwork will be searched with agradually shrunk domain. In addition, the technique of AC-6 can be integrated intoour algorithm, leading to a further decrease in computational complexity.
