（某些）优化问题的解-空间结构

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
数值研究了两个由计算复杂度引起的NP难优化问题：顶点覆盖问题和数划分问题的随机系综的聚类结构。我们使用分支定界型算法来获得这些问题在适度系统规模下的精确解。利用直接邻域聚类和层次聚类两种方法研究了解空间的结构。主要结果是，解的结构与问题的相图之间的对应关系不是唯一的。即，对于顶点覆盖，我们观察到解空间从单个大簇到多个嵌套簇的剧烈变化。相反，对于数划分问题，相空间看起来总是非常简单，类似于最低能量配置的随机分布。这在“容易”/可解决的阶段和“困难”/不可解决的阶段都是成立的。
---
英文标题：
《Solution-space structure of (some) optimization problems》
---
作者：
Alexander K. Hartmann, Alexander Mann, and Wolfgang Radenbach
---
最新提交年份：
2007
---
分类信息：

一级分类：Physics        物理学
二级分类：Disordered Systems and Neural Networks        无序系统与神经网络
分类描述：Glasses and spin glasses; properties of random, aperiodic and quasiperiodic systems; transport in disordered media; localization; phenomena mediated by defects and disorder; neural networks
眼镜和旋转眼镜；随机、非周期和准周期系统的性质；无序介质中的传输；本地化；由缺陷和无序介导的现象；神经网络
--
一级分类：Physics        物理学
二级分类：Statistical Mechanics        统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--

---
英文摘要：
  We study numerically the cluster structure of random ensembles of two NP-hard optimization problems originating in computational complexity, the vertex-cover problem and the number partitioning problem. We use branch-and-bound type algorithms to obtain exact solutions of these problems for moderate system sizes. Using two methods, direct neighborhood-based clustering and hierarchical clustering, we investigate the structure of the solution space. The main result is that the correspondence between solution structure and the phase diagrams of the problems is not unique. Namely, for vertex cover we observe a drastic change of the solution space from large single clusters to multiple nested levels of clusters. In contrast, for the number-partitioning problem, the phase space looks always very simple, similar to a random distribution of the lowest-energy configurations. This holds in the ``easy''/solvable phase as well as in the ``hard''/unsolvable phase.
---
PDF链接：
https://arxiv.org/pdf/711.3912

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：空间结构 Optimization Partitioning neighborhood localization cover space 了解 算法 相图