资源描述:
《Assumption-based Pruning in Conditional》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、Assumption-basedPruninginConditionalCSPFelixGellerandMichaelVekslerOutlineConditionalCSP(MittalandFalkenhainer)ConditionalCSPsolutionmethodsActivityCSPformulationMAC-basedalgorithmforACSPActivitydisjunctionandimplicationQuestions2DescribesCSPwherenot
2、allvariablesarerequiredtoparticipateinasolution(V,VI,D,CC,CA)ConditionalCSP(MittalandFalkenhainer)TheassignedvariablesareactivevariablesAcompatibilityconstraintisrelevantifallitsvariablesareactiveActivityofavariableisdeterminedbyactivityconstraintGiv
3、enanassignmentofvaluestoAnactivityconstraint:isrelevantifCisrelevantAnactivityconstraintissatisfiedifvisactiveorCisnotsatisfiedInasolutionallrelevantconstraintshavetobesatisfiedMinimalityrequirement3ExistingapproachestosolvingConditionalCSPsReformula
4、tionWorkingdirectlyonConditionalCSPrepresentationMainidea:maintainlistofactivevariablesandcheck/propagateconstraintsaftertheirvariablesbecomeactive[Mittal,Falkenhainer]:Backtracksearchwithconflictsrecording[Gelle,Faltings]:Atfirstdeterminevariableact
5、ivitystatus;forfixedvariableactivitystatusCondCSPturnsintoCSP.[Sabin,Freuder,Wallace],[Gelle,Sabin]:invokeconsistencytechniques(CondFC,CondMAC)directlyonConditionalCSPrepresentationPropagateconstraintsoncetheirvariablesareactiveCondMACprovedtobesuper
6、ioroverCondBTandCondFCThelimitation:constraintpropagationhastowaituntilvariablesbecomeactive4ActivityCSPformulation(V,VI,VA,D,C,A)VariableisactiveifeitheroristrueConstraintisrelevantifallitsvariablesareactiveAnassignmentisasolutionifallrelevantconstr
7、aintsaresatisfiedA-activationconditions:EachvariableisdominatedbysomeExplicitactivityvariablesGivenanassignmentofvaluesto5Earlyconflictdetection:ey=trueD(x)=D(y)={0,…,4}ez=trueD(x)=D(z)={5,…,9}D(y)∩D(z)=Øeyez=falseInformationflowfromconditionalv
8、ariablestounconditionalvariables:ey=trueD(x)=D(y)={0,…,4}ez=trueD(x)=D(z)={5,…,9}eyezD(X)={0…9}AnACSPproblem{true,false}ey{true,false}ez{0,…,4}y{5,…,9}z{0,…,100}x==V6EnablingearlyconstraintpropagationAllowconstraintpropagationtomodifyvariabledoma