社交网络论文翻译

《社交网络论文翻译》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分块解决:迭代搜索策略组合优化问题摘要：分支定界和分支切割使用搜索树来确定组合优化问题的最优解。在本文中，我们介绍一种迭代搜索策略，我们称这种方法为分块解决的最优性以及终止证明。这是一种不同于传统的没有分支的搜索树的搜索方法。在每个节点的搜索路径中，一个容易解决的问题和一个稀疏的问题将被解决，并且会向易解决的问题附加一个约束条件。会向稀疏的问题提供一个现有的解决方案。当约束条件变得十分的紧凑，那么它解决问题的价值就不如现有的解决方案。在这一点上，现有的解决方法是最优的。使用这种策略很容易在一个任意时间算法内，发现搜索树节点上的最优的解决方法。分块解决

2、方法有两个比较好的优势。因为没有分支，所以在搜索树之中不会出现错误的分支树，这种错误的分支树会在进行搜索时，使得搜索路径丢失，找不到正确的解决方法。因为这些原因，所以这种方法可以用来很好的解决使用深度优先算法和最优算法无法解决的难题。在本文中，我们证明了分块解决方法对于解决非对称旅行问题与策略推销员问题（ATSP）是可行的。我们的最优算法，在用于解决ATSP问题时，优于国家最先进的分析仪器。这个没有经过优化的算法对于解决一些还没有被解决的难题有十分好的效果，就像ASTP问题中的“七桥问题”这类问题延展出的五类实际问题。对于现在存在的四个类似的问题，使

3、用分块解决方法是十分有可能解决的。我们的代码都已经发布到我们的网站上了。关键字：搜索策略；分支定界；分支切割；任意时间算法；线性规划；旅行商问题。1.简介生活之中充满了优化问题。我们正在不断的寻找最优秀的算法来降低成本，时间，能量，或一些其他有价值的资源，或最大限度地提高性能，利润，生产，或其他一些理想的目标，同时满足在解决这些问题是需要考虑的约束条件。优化问题是很有趣的，经常有一个非常大的可行的解决方案，可以满足带有许多约束条件的问题；挑战在于通过搜索这个庞大的解决方案空间，确定一个最优解。当解的数目非常大的时候，这两个搜索策略，分支定界[4]和分

4、支切割[28]，已被证明是非常有用的。分枝定界使用搜索树来确定一个最佳的解决方案。（注意：可能有一个以上的优化解。）如果整个树的生成，每一个可行的解决方案，将由至少一个叶节点代表。对于搜索树的遍历和随意的变化，原来的问题是在每个节点进行解决的。由现在的解决方案，可以推导出其子问题的解决方法。其他发现这种类型的解决方案，既需要进行更新，始终保持最佳的可行的解决方案。当搜索树对于解决较小问题表现的不是很好时，现在的解决方案可以被认为是最优的解决方法。如果解决方案的数目太大，允许显式地进行对比，然而搜索树太大是要进行全面的探讨。分支定界的力量来自它的剪枝规

5、则，它允许修剪不必要的分支树以保证整个子树的最优性。如果搜索树被修剪到一个足够小的尺寸，就会显现出来问题解决方案的最优性。分支切割提高分支定界修剪的概率。在一些或所有的节点，为切割面[28]添加收紧或松弛子问题。对于松弛子问题，这些切割平面会删除一组解决方案。但是，为了确保最优解，这些切割平面在进行设计时，不排除任何可行的解决当前收紧问题的方法。当切割面可大幅度减少花费在每一个节点上的时间时，这些减少的时间可能会大大减少搜索树的大小，这已经被用来解决大量以前难于解决的问题。因为分支定界和分支切割对于线性空间的要求以及其他有利特征的要求，所以通常用深度

6、优先的算法实现这种解决方案[49]。然而，深度优先搜索可能遇到的问题是，对于探讨的问题不存在最优解，即不存在最优子树，这将会导致在进行搜索时，花费较大的搜索成本。在进行子树选择时，如果选择了一个错误的子树，那么在进行早期的探索过程中，用深度优先算法是很难发现这个错误的，因此不可能较早的及时的对问题进行纠正。而对于这一缺点，现在的人工智能领域已经投入了巨大的精力寻求解决这一问题的办法。分枝技术[4]，启发式算法研究[42]，和搜索技术，像有限的差异[24]和随机并重新启动[19]一直在努力解决这种持续性发展问题。在本文中，我们介绍一种迭代搜索策略，克服

7、了用深度优先算法解决分支定界问题时容易选择错误的分支树的问题，并且对于要求的存储保存也会满足。我们称这种搜索策略为分块解决，并展示它的整数线性规划。作为一个迭代策略，它没有复杂的搜索树，只存在一条搜索路径。换句话说，在每个节点只有一个孩子，所以没有必要选择哪个孩子节点，用来对以后的结果进行预测。在每个节点的搜索路径中，两个相对简单的子问题都解决了。首先，一个松弛问题得到了解决。然后通过求解稀疏问题，对于每一个含有庞大数量的解空间，寻找每一个可能的解决方案，而不是寻找一个最佳的解决方案。现有的解决方案是在发现的第一个节点之后，对后续发现的节点进行持续的

8、更新。当搜索终止后，当前的解决方法可以保证得到的是最佳的解决方案。在本文中，我们证明了最优性和终止的分块解决