合取范式3可满足问题的局部搜索近似算法

《合取范式3可满足问题的局部搜索近似算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３３卷第７期计算机学报Ｖｏｌ．３３Ｎｏ．７２０１０年７月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＪｕｌｙ２０１０合取范式３可满足问题的局部搜索近似算法朱大铭马绍汉张平平（山东大学计算机科学技术学院济南２５０１０１）摘要合取范式最大可满足问题是理论计算机科学的核心问题．局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法，但未见关于局部搜索算法解答该问题性能分析的结果．文中讨论最大３可满足问题（Ｍａｘ（３）Ｓａｔ）的局部搜索算法并分析算法性能．证明Ｍａｘ（３）Ｓａｔ问题的一位跳变局部搜索算法的近似性能比为４／３；证明一位跳变局部搜索后跟有条件全体跳变算法，解

2、答Ｍａｘ（３）Ｓａｔ问题的近似性能比为５／４．设计一位跳变加全体跳变的新局部搜索算法，证明新算法解答Ｍａｘ（３）Ｓａｔ问题的近似性能比为８／７．将８／７近似局部搜索算法推广为解答Ｍａｘ（犽）Ｓａｔ问题的局部搜索算法，证明算法的近似性能比为（２犽＋２）／（２犽＋１），犽４．设计解答Ｍａｘ（犽）Ｓａｔ问题的两位跳变局部搜索算法，证明两位跳变局部搜索算法的近似性能比为１＋１／（２犽＋１＋犽（犽－１）／（狀－犽）），犽４．局部搜索算法经多次运行可进一步提高求解性能．文中结果显示，局部搜索算法在合取范式最大可满足问题求解实践中表现出高性能，有其必然性．关键词算法；复杂性；近似性能

3、比；可满足性；局部搜索中图法分类号ＴＰ３０１犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１０．０１１２７犜犺犲犔狅犮犪犾犛犲犪狉犮犺犃犾犵狅狉犻狋犺犿狊犳狅狉犕犪狓犻犿狌犿３犛犪狋犻狊犳犻犪犫犾犻犾犻狋狔犘狉狅犫犾犲犿ＺＨＵＤａＭｉｎｇＭＡＳｈａｏＨａｎＺＨＡＮＧＰｉｎｇＰｉｎｇ（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔，犛犺犪狀犱狅狀犵犝狀犻狏犲狉狊犻狋狔，犑犻狀犪狀２５０１０１）犃犫狊狋狉犪犮狋Ｍａｘｉｍｕｍｓａｔｉｓｆｉａｂｉｌｉｔｙｐｒｏｂｌｅｍｉｓｔｈｅｃｅｎｔｒａｌｐｒｏｂｌｅｍｉｎｔｈｅｏｒｅｔｉｃａｌｃｏｍｐｕｔｅｒｓｃｉｅｎｃｅ

4、．Ｍａｘｉｍｕｍ３ｓａｔｉｓｆｉａｂｉｌｉｔｙｐｒｏｂｌｅｍ（Ｍａｘ（３）Ｓａｔ）ｉｓｏｎｅｏｆｔｈｅｍｏｓｔｉｍｐｏｒｔａｎｔｓｕｂｐｒｏｂｌｅｍｏｆｔｈｅｍａｘｉｍｕｍｓａｔｉｓｆｉａｂｌｉｔｙｐｒｏｂｌｅｍ．Ｌｏｃａｌｓｅａｒｃｈｈａｓｂｅｅｎｔｅｓｔｉｆｉｅｄｔｏｂｅｖｅｒｙｅｆｆｅｃｔｉｖｅｆｏｒｓｏｌｖｉｎｇｔｈｉｓｐｒｏｂｌｅｍｂｙｍａｎｙｔｉｍｅｓｏｆｒｅａｌｃｏｍｐｕｔａｔｉｏｎ．Ｈｏｗｅｖｅｒ，ｔｈｅｒｅｉｓｎｏｒｅｌａｔｅｄｒｅｓｕｌｔｓｆｏｒａｎａｌｙｚｉｎｇｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅｌｏｃａｌｓｅａｒｃｈｍｅｔｈｏｄｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌ

5、ｅｍ．Ｔｈｉｓｐａｐｅｒａｐｐｒｏａｃｈｅｓｔｈｅｌｏｃａｌｓｅａｒｃｈｍｅｔｈｏｄｔｏｓｏｌｖｅｔｈｅｍａｘｉｍｕｍｓａｔｉｓｆｉａｂｌｉｔｙｐｒｏｂｌｅｍｓａｎｄａｎａｌｙｚｅｓｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅｍｅｔｈｏｄ．ＴｈｅｃｅｎｔｒａｌｉｓｓｕｅｏｆｔｈｅｐａｐｅｒｉｓｔｏｄｉｓｃｕｓｓｔｈｅｌｏｃａｌｓｅａｒｃｈａｌｇｏｒｉｔｈｍｔｏｓｏｌｖｅｔｈｅＭａｘ（３）Ｓａｔ．Ｔｈｅａｕｔｈｏｒｓｓｈｏｗｔｈａｔｔｈｅｏｎｅｂｉｔｆｌｉｐｌｏｃａｌｓｅａｒｃｈａｌｇｏｒｉｔｈｍｃａｎａｃｈｉｅｖｅｔｈｅｐｅｒｆｏｒｍａｎｃｅｒａｔｉｏ４／３ｆｏｒｓｏｌｖｉｎｇｔｈｅＭａ

6、ｘ（３）Ｓａｔ；ａｎｄｔｈｅａｌｇｏｒｉｔｈｍｏｆｏｎｅｂｉｔｆｌｉｐｌｏｃａｌｓｅａｒｃｈｆｏｌｌｏｗｉｎｇｔｈｅｃｏｎｄｉｔｉｏｎａｌｌｙａｌｌｂｉｔｓｆｌｉｐｃａｎａｃｈｉｅｖｅｔｈｅｐｅｒｆｏｒｍａｎｃｅｒａｔｉｏ５／４ｆｏｒｓｏｌｖｉｎｇＭａｘ（３）Ｓａｔ．ＡｎｄｔｈｅａｕｔｈｏｒｓｄｅｓｉｇｎａｎｅｗｌｏｃａｌｓｅａｒｃｈａｌｇｏｒｉｔｈｍｔｏｓｏｌｖｅｔｈｅＭａｘ（３）Ｓａｔｐｒｏｂｌｅｍｕｓｉｎｇｔｈｅｏｎｅｂｉｔｆｌｉｐｌｏｃａｌｓｅａｒｃｈｆｏｌｌｏｗｉｎｇｔｈｅａｌｌｂｉｔｓｆｌｉｐ，ａｎｄｓｈｏｗｔｈｅｎｅｗａｌｇｏｒｉｔｈｍｈａｖｅｔｈ

7、ｅｐｅｒｆｏｒｍａｎｃｅｒａｔｉｏ８／７．Ｔｈｅ８／７ａｐｐｒｏｘｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍｃａｎｂｅｅｘｔｅｎｄｅｄｔｏｓｏｌｖｅｔｈｅＭａｘ（犽）Ｓａｔｐｒｏｂｌｅｍｗｉｔｈｐｅｒｆｏｒｍａｎｃｅｒａｔｉｏ（２犽＋２）／（２犽＋１）ｆｏｒ犽４．ＦｉｎａｌｌｙｔｈｅａｕｔｈｏｒｓｇｉｖｅｔｈｅｔｗｏｂｉｔｓｆｌｉｐｌｏｃａｌｓｅａｒｃｈａｌｇｏｒｉｔｈｍｔｏｓｏｌｖｅｔｈｅＭａｘ（犽）