北大公開課-人工智能基礎(chǔ) 36 約束滿足問題之約束傳播


對于常規(guī)搜索,只能進行搜素功能
而對于CSP類型問題,除了搜索功能之外,還能進行約束傳播

可以理解約束傳播是一類特殊的約束滿足問題
一種局部的約束滿足搜索情況

考慮到局部的約束搜索情況
只包括:節(jié)點一致性、弧一致性、路徑一致性、k值一致性(都可以看成局部的節(jié)點、弧、路徑和k值的一致性)

局部節(jié)點一致性(線性約束滿足,或者可以稱為一元約束滿足,單一條件下的約束滿足)

局部弧一致性(曲線/函數(shù)約束滿足,或者叫二元一致滿足,雙重條件下的約束滿足)

局部弧一致性的約束滿足算法

局部路徑一致滿足(定義兩個變量中間點的約束滿足條件)

k值一致滿足,泛化的局部約束滿足情況

用局部約束滿足算法,來解決n維的數(shù)獨問題




標簽: