最小曼哈顿网络问题的解决途径

发布网友发布时间：2022-04-28 20:59

共1个回答

热心网友时间：2022-06-23 04:32

设计出具有更优近似度的近似算法
近似算法的设计方法主要包括：局部搜索，线性规划方法，原始对偶（primal-al）方法等。本问题已知的近似算法可以分为两类：一类方法是将全局最优网络问题规约为局部最优网络问题，再通过局部网络的组合达到全局的较优解，如M. Benkert 等人提出的3-近似算法。在这一方法的使用中，郭泽宇已取得了国际领先的成果。另一类则基于线性规划方法，如V. Chepoi等人在文献提出的2-近似算法。
在第一阶段的研究中，一方面在已知的最好近似算法基础上，对问题的性质进行更细致地分析以尝试改进；另一方面对近似算法的设计进行系统的学习，探索其他的算法设计思路。
研究问题所属的复杂性类
尽管在过去的近十年里，最小曼哈顿网络问题受到许多西方计算机科学家的重视，但是到目前为止，人们还不清楚这一问题是否存在多项式时间算法。人们猜想这一问题是NP-完全的，但到目前为止还没有人给出有效的证明。
一般来讲，证明一个问题是NP-完全的基本方式是将一已知的NP完全问题归约到所研究的问题上。这方面，已知的NP-完全的计算几何和组合最优化问题的归约过程将具有很*价值。例如V. Chepoi在论文中提到的与最小曼哈顿网络问题相当类似的RSA问题，已经由W.Shi 和C. Su给出了从Planar-3-SAT问题到该问题的归约，从而证明了该问题为NP-完全的。因此，郭泽宇通过阅读更多的计算几何学NP-完全问题规约的文章，掌握各种复杂的技巧。试图给出最小曼哈顿网络问题的类似的归约方式，从而证明这一问题是NP-完全的。