电弧一致性（AC3）和一项挑战？

2016-02-20 87 views 3 likes

在对一个约束满足问题应用弧一致性（AC3）算法时，如果一个变量的域为空，那么下一步是什么？电弧一致性（AC3）和一项挑战？

1) halt. 

2) do backtrack. 

3) start from another initial state. 

4) it depends on that we are in which step.

解决方案（4）。我认为（1）是真实的，因为这意味着我们找不到任何一致的任务并停下来。任何人都可以描述为什么（4）是真的？

来源

2016-02-20 LoveComplexity

回答

对于您正在使用的particular algorithm，如果变量的域缩小到空，那么这意味着约束问题没有解决方案。因此算法应该停止在故障状态。

来源

2016-02-23 03:04:29

但解决方案说（4）!! – LoveComplexity

您的解决方案完全错误。由于我们只从域中删除值，因为它们永远不可能成为解决方案的一部分，所以空域意味着根本不可能解决任何问题---->如此退出该分支......不会停止从其他分支开始... – user4249446

也许是停止，也许是回溯，或者从另一个分支开始，请参阅本书的第221页：https://books.google.com/books?id=ms7BbRjEwo8C&pg=PA221&lpg=PA221&dq=arc-consistency+domain+empty+backtrack+和＆源= BL＆OTS = 68AG9qCjoo＆SIG = tnxE-wIW76druM3T5sOSWUtv-M8＆HL = EN＆SA = X＆VED = 0ahUKEwj4hfqbtcTNAhWBFiwKHb_QAbc4ChDoAQhGMAc＃v = onepage＆q =圆弧一致性％20domain％20empty％20backtrack％20于是＆F =假 – user4249446

电弧一致性（AC3）和一项挑战？

回答

相关问题