当我读到AC-3 in Artificial Intelligence: A Modern Approach的伪代码时,我认为它解决了路径一致性和弧一致性问题。但书中说,路径一致性是由PC-2算法解决的。我错过了什么吗?
为什么AC-3不足以解决路径一致性问题?
下面是AC-3的代码
function AC-3(csp) returns false if an inconsistency is found and true otherwise
inputs: csp, a binary CSP with components (X, D, C)
local variables: queue, a queue of arcs, initially all the arcs in csp
while queue is not empty do
(Xi, Xj)←REMOVE-FIRST(queue)
if REVISE(csp, Xi, Xj) then
if size of Di = 0 then return false
for each Xk in Xi.NEIGHBORS - {Xj} do
add (Xk, Xi) to queue
return true
function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi
revised ← false
for each x in Di do
if no value y in Dj allows (x,y) to satisfy the constraint between Xi and Xj then
delete x from Di
revised ← true
return revised提前感谢:)
https://stackoverflow.com/questions/44450955
复制相似问题