資源描述：
《基于ac和lmaxrpc自適應約束傳播求解算法》由會員上傳分享，免費在線閱讀，更多相關內容在工程資料-天天文庫。
1、基于AC和LmaxRPC自適應約束傳播求解算法摘要：在現(xiàn)有自適應約束求解方法基礎上，提出一種新的自適應約束傳播求解算法ADAPTACLmaxRPC.該算法能根據(jù)約束的不同特性，在傳播能力強但開銷高的LmaxRPC與傳播能力弱卻開銷低的AC之間自適應地切換進行約束傳播.多個Benchmark實例類上的測試實驗數(shù)據(jù)表明，ADAPTACLmaxRPC算法有效地平衡了求解效率和算法開銷之間的矛盾，大幅度提高了約束求解的效率.關鍵詞：人工智能；約束程序；約束滿足問題；自適應約束求解；約束傳播中圖分類號：TP31文獻標識碼：AAdaptiveConstraintPropagationS
2、olvingBasedonACandLmaxRPCWANGHaiyanl,2,3,OUYANGDantongl,2,ZHANGYonggangl,2,YANGMingming1,2(1.CollegeofComputerScienceandTechnology,JilinUniv,Changchun,Jilin130012,China；2.KeyLaboratoryofSymbolicComputationandKnowledgeEngineeringforMinistryofEducation,JilinUniv,Changchun,Jilin130012,China；3
3、.CollegeofComputer,JilinNormalUniv,Siping,Jilin136000,China)Abstract:Onthebasisofthecurrentadaptiveconstraintsolvingalgorithms,thispaperproposedanewadaptiveconstraintpropagationsolvingalgorithmADAPTACLmaxRPC,whichadaptivelyswitchesbetweenenforcingastrongandexpensivelocalconsistencyLmaxRPCa
4、ndaweakbutmorecheaperoneACaccordingtotheactivityofindividualconstraints?TestdatafromseveralBenchmarkinstancesshowsthatADAPTACLmaxRPCbalancesthecontradictionbetweentheconstraintsolvingefficiencyandalgorithmcosteffectively,anditimprovestheefficiencyofconstraintsolvingsubstantially.Keywords:a
5、rtificialintelligence；constraintprogramming；constraintsatisfactionproblem；adaptiveconstraintsolving；constraintpropagation近年來，由于具有濃厚產業(yè)背景和重大商業(yè)價值，約束程序(ConstraintProgramming,CP)研究得到蓬勃發(fā)展，并已成為問題建模及求解如資源分配、調度問題、時序推理、規(guī)劃和圖著色等領域困難組合問題的典范.約束滿足問題(ConstraintSatisfactionProblem,CSP)[1]是約束程序的核心，自提出以來受到了廣
6、泛關注?國內外有很多學者致力于這方面的研究，主要的工作有約束程序理論、設計與應用的研究、約束歸納邏輯程序設計等方面，以及CSP求解研究等[2].其中，CSP的求解一直是人工智能領域研究的熱點，具有重要的理論研究和實際應用價值.CSP的主要推理技術是約束傳播，它對約束程序的成功與否起著至關重要的作用，是影響約束求解算法效率和適應性的關鍵因素?因此，多種約束傳播技術應運而生[3],包括早期的FC,廣泛使用的GAC,以及maxRPC,SAC等.雖然約束傳播技術選擇豐富，但簡單的約束求解器通常在整個搜索過程中對所有的約束都使用同一個標準方法.由于不同約束的刪除能力各不相同，同一種約
7、束傳播技術很難適用于所有約束.比如，如果為很少或不刪除值的約束選用了一種過濾能力很強的約束傳播方法，必然會導致不必要的CPU開銷.所以，考慮到時間和空間復雜性，盡量想為刪除能力強的約束選擇過濾能力強的約束傳播方法，為刪除能力弱的約束選擇過濾能力弱的約束傳播方法?因此，如何在搜索中為約束動態(tài)選擇約束傳播方法成為一個重要的研究方向.隨著約束求解方法的發(fā)展，“自適應”概念越來越受到人們關注.這一概念的出現(xiàn)使“動態(tài)”選擇約束傳播方法成為可能.越來越多研究者開始考慮從問題的結構化信息入手，從CSP求解的各個角度提出具有更強適
