返回上一页 发布人:patent
我要发布信息
| 组合搜索 从算法到系统 | 发布于:2015/01/25 | |
| 组合搜索算法关注于解决NP难题，而一直以来NP难题总体上被看作是无法解决的，但实际中一些NP难问题是可以通过逻辑语言计算或推理得到有效解决的。组合搜索算法通过减少搜索空间的可行域和使用启发式搜索方法搜索大的解空间进行NP难题的求解。目前已经有很多相关的数学模型，用以表达和解决组合优化问题，如约束满足性问题（CSP， the Constraint Satisfaction Problem）和命题可满足性问题（SAT， the Propositional Satisfiability problem）。本书详细地对能够显著提高约束求解器性能的组合搜索、产生与探究有意义的信息进行了阐释，即冗余约束、启发式提示、性能测量及搜索过程等，对信息共享及性能共享两种情况结合实例进行了详实地介绍。 全书由8章组成：1.导论。本章介绍了组合搜索的发展情况，解释了几个组合搜索算法中的相关术语，给出了本书的整体结构，提出了知识共享与性能共享概念；2.增强分布式约束网络。本章详细地阐释了组合风险中的随机风险选择问题，介绍了分布式CSP算法与知识共享的竞争、合作对于提高现有的分布式搜索技术的影响，讨论了该方法的实现原理及过程；3.可满足性并行树搜索。介绍了组合搜索在并行命题可满足性问题中的重要应用，详细地阐述了ManySAT算法原理，介绍了其知识共享概念，及分布式CSP算法基础上建立的并行组合搜索算法；4.可满足性并行局部搜索。本章讨论了SAT中的并行局部搜索算法，概述了有效地局部搜索算法原理及特点，最后提出了几个能够提高局部搜索算法性能的聚类策略；5.学习变量间依赖关系。讨论了变量功能依赖关系中弱依赖关系的简化形式，介绍了依赖关系的原理性知识及相关工作，并给出了实例进行详细地分析；6.连续搜索。本章首先提出了连续搜索方法，随后介绍了其两种工作模式：开发模式和探索模式，阐述了两种模式的工作原理及应用，最后阐释了连续搜索方法能够自主地搜索系统性能并分析其性能以逐渐纠正其搜索策略；7.自主搜索。本章介绍了利用知识共享机制，构建了一个统一的自主搜索框架，给出了其搜索过程，提出了一种基于计算特性的分类的搜索过程及其准则；8.结论与展望。 本书适合从事计算机科学、计算机工程和组合搜索及优化等专业的研究生阅读和学习，亦可以作为对组合优化、约束问题及NP难问题研究感兴趣的其他专业学生的参考书。对于在组合优化及组合搜索研究领域的很多专业人士和研究人员，本书也将提供较大的帮助。 （中国科学院空间科学与应用研究中心）作者：张进兴 来源：国外科技新书评介 |
||
