约束满足问题解析学习教案

1、会计学1约束满足约束满足(mnz)问题解析问题解析第一页，共80页。第1页/共80页第二页，共80页。第2页/共80页第三页，共80页。第3页/共80页第四页，共80页。第4页/共80页第五页，共80页。第5页/共80页第六页，共80页。第6页/共80页第七页，共80页。第7页/共80页第八页，共80页。第8页/共80页第九页，共80页。第9页/共80页第十页，共80页。第10页/共80页第十一页，共80页。S E N D M O R EM O N E Y变量(binling)：D,E,M,N,O,R,S,Y域：0,1,2,3,4,5,6,7,8,9约束M 0，S 0，单元约束Y = D E

2、或Y = D E 10D E，D M，D N 等第11页/共80页第十二页，共80页。第12页/共80页第十三页，共80页。第13页/共80页第十四页，共80页。样本(yngbn)状态：(V1=G,V2=B,V3=?,V4=?,V5=?,V6=?)第14页/共80页第十五页，共80页。V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V5V6BB?V1V2V3V4V5V6?坏值值次序(cx)：(B,R,G)第15页/共80页第十六页，共80页。V1V2V3V4V5V6B?V1V2V3V4V5V6R?V1V2V3V4V5V6G?V1V2V3V4V

3、5V6BB?V1V2V3V4V5V6?值次序(cx)：(B,R,G)第16页/共80页第十七页，共80页。第17页/共80页第十八页，共80页。第18页/共80页第十九页，共80页。V1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V5V6BRRBG?值次序(cx)：(B,R,G)第19页/共80页第二十页，共80页。V1V2V3V4V5V6B?V1V2V3V4V5V6BR?V1V2V3V4V5V6BRRB?V1V2V3V4V5V6BB?V1V2V3V4V5V6?V1V2V3V4V

4、5V6BRRBG?值次序(cx)：(B,R,G)不考虑该树枝，因为(yn wi)V2=B与目前已赋值相关的约束不符。回溯到前一个状态，因为不能给V6赋合法的值。第20页/共80页第二十一页，共80页。第21页/共80页第二十二页，共80页。第22页/共80页第二十三页，共80页。V1V2V3V4V5V6R?B?G?值次序(cx)：(R,B,G)第23页/共80页第二十四页，共80页。V1V2V3V4V5V6ROX?XX?B?G?第24页/共80页第二十五页，共80页。V1V2V3V4V5V6RO?XX?BOX?X?G?第25页/共80页第二十六页，共80页。V1V2V3V4V5V6ROOXXX

5、BO?X?G?第26页/共80页第二十七页，共80页。V1V2V3V4V5V6ROOXXBOOXXG?第27页/共80页第二十八页，共80页。V1V2V3V4V5V6ROOXBOOXGOX无合法(hf)值能赋给V6，因此需要回溯第28页/共80页第二十九页，共80页。V1V2V3V4V5V6ROOXXBOOXXG?在该处已可看出，此路径(ljng)不通向解，因为域中剩余值在赋给V5与V6后不能保持一致性。第29页/共80页第三十页，共80页。第30页/共80页第三十一页，共80页。第31页/共80页第三十二页，共80页。V1V2V3V4V5V6ROX?XX?B?G?在传播(chunb)(V1,

6、R)后：第32页/共80页第三十三页，共80页。V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在传播(chunb)(V2,B)后：传播(chunb)次序：23546365354第33页/共80页第三十四页，共80页。V1V2V3V4V5V6ROXXX?BOX?XXG?X?X在传播(chunb)(V2,B)后：第34页/共80页第三十五页，共80页。n添加所有(Vk,Vi)对到A中，其中Vk (kj) 是Vi的一个近邻第35页/共80页第三十六页，共80页。第36页/共80页第三十七页，共80页。第37页/共80页第三十八页，共80页。第38页/共80页第三十九页，共80页。V1V2

7、V3V4V5V6V7R?第39页/共80页第四十页，共80页。V1V2V3V4V5V6V7R?变量(binling)V5影响5个变量(binling)。变量(binling)V2、V3或V4只影响较少的变量(binling)。第40页/共80页第四十一页，共80页。V1V2V3V4V5V6V7ROXXX?OBO?X?G?第41页/共80页第四十二页，共80页。V1V2V3V4V5V6V7ROXXX?OBO?X?G?变量V5是最受约束的变量，并且(bngqi)最可能用来剪枝搜索树。第42页/共80页第四十三页，共80页。V1V2V3V4V5V6GR?四种(s zhn)颜色：D=R,G,B,Y第4

8、3页/共80页第四十四页，共80页。V1V2V3V4V5V6GR?四种颜色(yns)：D=R,G,B,Y要给V3赋哪个值？第44页/共80页第四十五页，共80页。凹边凹边凸边凸边(t bin)?第45页/共80页第四十六页，共80页。特殊(tsh)观察点一般观察点不允许的边第46页/共80页第四十七页，共80页。第47页/共80页第四十八页，共80页。TVYW第48页/共80页第四十九页，共80页。1+2-3-4-5-第49页/共80页第五十页，共80页。1+2-3-4-5-第50页/共80页第五十一页，共80页。第51页/共80页第五十二页，共80页。第52页/共80页第五十三页，共80页。

9、+-+-+-+VYTW第53页/共80页第五十四页，共80页。+-+-+BA+-+CCBDA+-D(B,A)第54页/共80页第五十五页，共80页。+-+-+BA+-+CCBDA+-D(C,B)第55页/共80页第五十六页，共80页。+-+-+BA+-+CCBDA+-D(D,C)第56页/共80页第五十七页，共80页。+-+-+BA+-+CCBDA+-D(A,D)第57页/共80页第五十八页，共80页。+-+-+BA+-+CCBDA+-D(B,A)第58页/共80页第五十九页，共80页。+-+-+BA+-+CCBDA+-D+-第59页/共80页第六十页，共80页。第60页/共80页第六十一页，

10、共80页。第61页/共80页第六十二页，共80页。第62页/共80页第六十三页，共80页。交付(jiof)约束：S13+T13tS22+T22tS33+T33t.第63页/共80页第六十四页，共80页。第64页/共80页第六十五页，共80页。第65页/共80页第六十六页，共80页。第66页/共80页第六十七页，共80页。第67页/共80页第六十八页，共80页。根第68页/共80页第六十九页，共80页。第69页/共80页第七十页，共80页。第70页/共80页第七十一页，共80页。G第71页/共80页第七十二页，共80页。G第72页/共80页第七十三页，共80页。第73页/共80页第七十四页，共80页。第74页/共80页第七十五页，共80页。SAT：ABCACDBDECDEACEN个皇后个皇后(hunghu)第75页/共80页第七十六页，共80页。V1V2V3V4V5V6abcdefV1V2V3V4V5V6abcdef第76页/共80页第七十七页，共80页。第77页/共80页第七十八页，共8