最大割问题求解方法、装置、存储介质和电子设备与流程

1.本公开涉及半经典量子技术领域，可以应用于超大规模集成电路设计、统计物理等场景下，具体地，涉及一种最大割问题求解方法、装置、存储介质和电子设备。


背景技术：

2.最大割问题(max-cut problem)包括对给定的有权无向图求取一个最大分割，使横跨两个割集的所有边上的权值之和最大，是图论中一个典型的np难组合优化问题。
3.最大割问题在超大规模集成电路设计、统计物理学等技术领域有着广泛的应用。例如在超大规模集成电路设计领域，最大割问题可以用于求解过孔数量最小化问题，在统计物理学领域，最大割问题可以用于求解自旋玻璃系统基态能量。虽然理论上最大割问题的解可以由枚举法找到，但是在实践过程中往往不可能实现。因为运行时间随着问题规模会呈现指数增长，随着规模的增大，问题的搜索空间也急剧增大，求解效率较低。因此，如何高效实现最大割问题的求解至关重要，对于解决相关技术领域的问题有着重要意义。


技术实现要素：

4.本公开的目的是提供一种最大割问题求解方法、装置、存储介质和电子设备，以提高对最大割问题的求解效率，进而有利于解决超大规模集成电路设计等技术领域的相关问题。
5.本公开实施例的第一方面，提供一种最大割问题求解方法，所述方法包括：获取待求解的最大割问题对应的有权无向图；计算所述有权无向图的初始的割权；确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半，得到更新后的割权；在所述目标边的权重为负数时，对所述有权无向图中的所述目标边进行常规式边收缩，在所述目标边的权重为正数时，对所述有权无向图中的所述目标边进行差分式边收缩，得到更新后的有权无向图；在所述更新后的有权无向图中存在边未被收缩时，返回执行所述确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半的步骤；在所述更新后的有权无向图中所有边均被收缩时，基于每一所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，并输出最后更新后的割权。
6.可选地，所述对所述有权无向图中的所述目标边进行常规式边收缩，包括：确定与所述目标边邻接的目标顶点和待合并顶点；针对所述待合并顶点的待合并邻接边，若不存在对应于所述待合并邻接边的目标邻接边，则创建权重为0的该目标邻接边，所述目标邻接边为所述目标顶点与所述待合并顶点的其它邻接顶点的连接边；
将所述待合并顶点合并至所述目标顶点；将所述待合并顶点的待合并邻接边合并至所述目标顶点的对应目标邻接边；将所述目标邻接边的权重加上所述待合并邻接边的权重，作为合并后的所述目标邻接边的权重；从所述有权无向图中删除所述目标边。
7.可选地，所述对所述有权无向图中的所述目标边进行差分式边收缩，包括：确定与所述目标边邻接的目标顶点和待合并顶点；针对所述待合并顶点的待合并邻接边，若不存在对应于所述待合并邻接边的目标邻接边，则创建权重为0的该目标邻接边，所述目标邻接边为所述目标顶点与所述待合并顶点的其它邻接顶点的连接边；将所述待合并顶点合并至所述目标顶点；将所述待合并顶点的待合并邻接边合并至所述目标顶点的对应目标邻接边；将所述目标邻接边的权重减去所述待合并邻接边的权重，作为合并后的所述目标邻接边的权重；从所述有权无向图中删除所述目标边。
8.可选地，所述计算所述有权无向图的初始的割权，包括：将所述有权无向图的所有边的权重相加之和的一半作为所述有权无向图的初始的割权。
9.可选地，在所述目标边的权重为负数时，所述方法还包括：设置一正号的标记符号，以标记所述目标边；在所述目标边的权重为正数时，所述方法还包括：设置一负号的标记符号，以标记所述目标边；所述基于每一所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，包括：在所述标记符号为正号时，确定所述目标边的两个邻接顶点属于同一集合，在所述标记符号为负号时，确定所述目标边的两个邻接顶点属于不同集合，以将所述有权无向图中的顶点划分为两个集合。
10.本公开实施例的第二方面，提供一种最大割问题求解装置，所述装置包括：获取模块，用于获取待求解的最大割问题对应的有权无向图；计算模块，用于计算所述有权无向图的初始的割权；确定模块，用于确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半，得到更新后的割权；边收缩模块，用于在所述目标边的权重为负数时，对所述有权无向图中的所述目标边进行常规式边收缩，在所述目标边的权重为正数时，对所述有权无向图中的所述目标边进行差分式边收缩，得到更新后的有权无向图；返回模块，用于在所述更新后的有权无向图中存在边未被收缩时，返回执行所述确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半的步骤；划分输出模块，用于在所述更新后的有权无向图中所有边均被收缩时，基于每一
所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，并输出最后更新后的割权。
11.本公开的第三方面，提供一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述第一方面中任一项所述方法的步骤。
12.本公开的第四方面，提供一种电子设备，包括：存储器，其上存储有计算机程序；处理器，用于执行所述存储器中的所述计算机程序，以实现上述第一方面中任一项所述方法的步骤。
13.通过上述技术方案，获取待求解的最大割问题对应的有权无向图，计算其初始的割权后，根据目标边的权重的正负情况，分别进行常规式边收缩以及差分式边收缩，以将劣汰型算法和优胜型算法结合，直至有权无向图的所有边被收缩后，根据目标边的权重的正负情况，将有权无向图中的顶点划分为两个集合，并输出最后更新后的割权，以完成对于最大割问题的求解。通过结合利用两种边收缩的优势，在可接受时间内完成对最大割问题的求解，提高了对于最大割问题求解的效率，有利于解决超大规模集成电路设计等技术领域的相关问题。
14.本公开的其他特征和优点将在随后的具体实施方式部分予以详细说明。
附图说明
15.附图是用来提供对本公开的进一步理解，并且构成说明书的一部分，与下面的具体实施方式一起用于解释本公开，但并不构成对本公开的限制。在附图中：
16.图1是根据一示例性实施例示出的一种最大割问题求解方法的流程图。
17.图2是根据一示例性实施例示出的一个有权无向图。
18.图3是根据一示例性实施例示出的确定图2中有权无向图的目标边的示意图。
19.图4是根据一示例性实施例示出的对图3中有权无向图边收缩后的示意图。
20.图5是根据一示例性实施例示出的确定图4中有权无向图的目标边的示意图。
21.图6是根据一示例性实施例示出的对图5中有权无向图边收缩后的示意图。
22.图7是根据一示例性实施例示出的确定图6中有权无向图的目标边的示意图。
23.图8是根据一示例性实施例示出的对图7中有权无向图边收缩后的示意图。
24.图9是根据一示例性实施例示出的对图8中有权无向图边收缩后的示意图。
25.图10是根据一示例性实施例示出的一种最大割问题求解装置的框图。
26.图11是根据一示例性实施例示出的一种电子设备的框图。
具体实施方式
27.以下结合附图对本公开的具体实施方式进行详细说明。应当理解的是，此处所描述的具体实施方式仅用于说明和解释本公开，并不用于限制本公开。
28.当前量子计算正处于所谓含噪中等规模（nisq）时代，还需要一段时间才能最终实现通用容错计算。在这一时期，量子硬件的性能还不足以保证许多复杂量子算法的顺利执行，从而在一定程度上限制了量子计算的实用。在这一背景下，对介于经典和量子之间的各种半经典算法进行开发是大有益处的：从经典的角度来看，它表现为量子启发式算法，可以
在经典算力上实现，并在一定程度上对经典算法有所改善和补充；从量子的角度看，它可以作为预处理步骤，为进一步的量子计算奠定基础。本公开所述的最大割问题求解方法即表现为一种量子启发式的半经典量子算法，以下先对一些基本概念进行解释。
29.组合优化问题（combinatorial optimization problem，cop）指的是从有限的一组对象中找到“最佳”对象的问题，而所谓的“最佳”对象包括找到某种评估分数最高或成本最低的对象，它可能是一个集合、一个排列或者一个图。在某些情况下，“最佳”对象并非理论上的最佳，而可能是与理论最佳相接近的对象。
30.图论(graph theory)，是数学的一个分支，它以图为研究对象。图是一个二元组g=（v，e），其中v是一个元素为顶点的集合，e是一个成对的顶点的边构成的集合。
31.有权无向图（weighted undirected graph），也称带权无向图，是图论中一种常见的图形模型，它由一组顶点和连接这些顶点的边组成，每条边都有一个权重，且这些边均没有方向。
32.最大割问题（max-cut problem），是图论中的一类组合优化问题，旨在对二进制变量序列，，寻求最大割目标函数的最大值。这一函数的图论含义如下。对于n个顶点的图g，令为边(i，j)上的权。给每个顶点i赋一个值，用所有取值0的顶点构成集合u，取值1的顶点构成集合d 。u和d之间的边集构成g的一个割。上述函数c(x)就是这个割的总权重。简而言之，最大割问题就是寻求图g的一个割，使得其权重最大。
33.二次无约束二元优化（qubo，quadratic unconstrained binary optimization）问题，是一种用于解决组合优化问题的数学模型，旨在对二进制变量序列， ，寻求二次函数的极值。其中，为自变量，是x的转置，为系数矩阵。
34.伊辛模型（ising model），是一种用于描述磁性物质行为的物理模型，可以定义在一个图/晶格上，其哈密顿量如下：。
[0035][0036]
其中，自旋变量，为边(i，j)上的耦合系数，为顶点系数。
[0037]
伊辛模型的目标是求得上述哈密顿量的最小值。伊辛模型除用来描述物理现象外，还被应用于经济、计算机等众多领域，以求解这些领域的部分组合优化问题。
[0038]
总体上看，最大割问题、二次无约束二元优化问题以及伊辛模型有两处差异：
[0039]
（1）变量取值不同。这可以通过变量代换或来转化。
[0040]
（2）一次项形式不同。这可以通过创建辅助变量来转化。
[0041]
因此，这三类问题是完全等价的。人们通常利用qubo表述对现实问题进行建模，用最大割表述进行算法分析，用伊辛表述进行物理实现。对于组合优化问题，若采用伊辛模型或qubo表述，可以将其转化为最大割问题，进而利用本公开提出的最大割问题求解方法进行求解。
[0042]
为了求解最大割问题，发明人创造性地提出通用稳定子算法用于解决包括最大割问题的组合优化问题，其具体步骤如下。
[0043]
对于给定多项式二元优化问题，通过代换将其目标函数转化为如下哈密顿量：
[0044]
，其中，。记pauli项集合为，系数集合为。
[0045]
步骤1：找出系数集合中绝对值最大的元素，记其下标为；
[0046]
步骤2：如果，则选择稳定子为；如果，则选择稳定子为 。更新r为；
[0047]
步骤3：利用高斯消元法更新，使得与中所有元素均线性无关。合并中的同类项，相应地更新r与；
[0048]
步骤4：重复上述步骤n次，即可找出全部生成元，并得到稳定子群：；
[0049]
步骤5：计算出该稳定子态的能量。其中，为第k个稳定子生成元被选中时的实时系数。
[0050]
通过将最大割问题转化为上述哈密顿量，即可用该稳定子算法求解最大割问题，如此发现尽管求解性能不错，但求解效率并不高。这表现在计算复杂度为。由于相应的哈密顿量中非常数项均为二次项，将这些pauli项编码成行向量，每行中取值1的元素仅有两个，因而非常稀疏。对这种低次的 pauli项用校验矩阵进行编码和操作并不高效。更高效的方法是直接在图上进行相应的操作，基于此发明人创造性地提出了本公开所述的最大割问题求解方法的技术方案。
[0051]
图1是根据一示例性实施例示出的一种最大割问题求解方法的流程图，参见图1，该方法包括：
[0052]
s101，获取待求解的最大割问题对应的有权无向图。
[0053]
s102，计算所述有权无向图的初始的割权。
[0054]
s103，确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半，得到更新后的割权。
[0055]
s104，在所述目标边的权重为负数时，对所述有权无向图中的所述目标边进行常规式边收缩，在所述目标边的权重为正数时，对所述有权无向图中的所述目标边进行差分式边收缩，得到更新后的有权无向图。
[0056]
s105，在所述更新后的有权无向图中存在边未被收缩时，返回执行所述确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半的步骤。
[0057]
s106，在所述更新后的有权无向图中所有边均被收缩时，基于每一所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，并输出最后更新后的割权。
[0058]
在步骤s101中，对于待求解的最大割问题，一般来讲，其定义中有相应的图，因此可以直接获取最大割问题定义中的有权无向图。
[0059]
对于利用qubo或伊辛模型表示的组合优化问题也可以转化为最大割问题，进而获取相应的有权无向图。
[0060]
在一种可能的实施方式中，所述最大割问题求解方法可以应用于超大规模集成电路（very large scale integration circuit，vlsi）设计，在其瞬态路由（transient routing）过程中，属于不同连接网络的导线可能会交叉，因此，某些导线必须在不同的电路板层上布线。为实现相应布线，需要在印刷电路板设计中放置过孔（via），在生产过程中，过孔会导致额外的工作，并经常导致电路板因裂纹而失效，且需要额外的空间，因此希望找到合适的电路板层分配，使得过孔的数量尽量少。
[0061]
以包含两个电路板层的情况为例，假设所有连接网络恰好连接两个引脚，则每个连接网络只有一根导线，将每根导线划分为自由段（free segments）和关键段（critical segments），关键段对应于布局图g＝（v，e）的节点集v，边集e包含两种边，分别为冲突边（conflict edge）和连续边（continuation edge），其中，当关键段i和j必须处于不同电路板层时，对应节点和通过冲突边连接；当关键段通过自由段连接时，对应节点和通过连续边连接。即，其中，a是冲突边的集合，b是连续边的集合。
[0062]
对于g的子图h=（v，a），如果h是二分图（bipartite graph），则h可以分割成连通的二分图分支（bipartite components）。一旦将分支（，）中的一个节点分配到一个电路板层，则中所有其它节点的分配就都确定了。
[0063]
进而可以将上述找到合适的电路板层分配，使得过孔的数量尽量少的问题转化为对应于图r的最大割问题，r=（w，f，c）。
[0064]
对于图r=（w，f，c），节点集合w中的节点是从h的分支（，）中任意选定的代表节点；当且仅当g包含一条（连续）边连接中的某个节点和中的某个节点时，边集合f包含一条连接和的边（i，j），；c为的集合，，为边（i，j）的权重，其中，为和被分配到同一电路板层时，和之间必要的过孔数量，是和被分配到不同电路板层时，和之间必要的过孔数量，和容易通过对图g中连续边统计数量得到。
[0065]
基于上述描述，可选地，最大割问题求解方法应用于超大规模集成电路设计时，在步骤s101中，获取待求解的最大割问题对应的有权无向图，包括：
[0066]
s1011，确定目标超大规模集成电路中目标电路板层的每一导线的关键段以及所述关键段的相连关系。
[0067]
s1012，基于所述关键段和所述相连关系生成图h=（v，a），其中，v为作为节点的所述关键段的节点集合，a为冲突边的边集合，所述冲突边连接存在于不同电路板层的关键段节点。
[0068]
s1013，在所述图h为二分图时，基于所述图h生成对应于所述超大规模集成电路设
计中待求解最大割问题的有权无向图r=（w，f，c），其中，w、f和c分别为所述图r的节点集合、边集合和对应边的权重集合，w中的节点表示所述图h分割后的二分图分支（，），当和中的节点对应的关键段相连时，f包含一条连接和的边，权重集合c中的权重，为连接和的边的权重，为和被分配到相同电路板层时和之间必要的过孔数量，是和被分配到不同电路板层时和之间必要的过孔数量。
[0069]
通过步骤s1011至步骤s1013，可以将超大规模集成电路设计的过孔数量最小化问题转化为对应于上述图r的最大割问题，其具体执行过程可以参见上述相关描述。
[0070]
需要说明的是，在步骤s1011中，目标超大规模集成电路可以是待进行电路设计的超大规模集成电路，目标电路板层可以是待解决过孔数量最小化问题的电路板层，其可以是目标超大规模集成电路中的某两层电路板层，其中的每个连接网络可以仅包含一根导线。可以将每根导线划分为自由段和关键段，并确定关键段的相连关系。
[0071]
在一种可能的实施方式中，本公开的最大割问题求解方法可以应用于自旋玻璃系统的基态能量计算，即待求解的最大割问题可以是自旋玻璃（spin glasses）系统的基态能量计算问题。自旋玻璃是一种稀释在非磁性金属中的磁性杂质的合金。显示自旋玻璃行为的合金如cumn；金属晶体aufe；绝缘体eusrs；和非晶态金属gdal。对自旋玻璃特性的研究如基态能量计算是有序-无序现象（order-disorder phenomena）研究领域的一个核心课题。
[0072]
自旋玻璃系统可以用伊辛模型来描述，其哈密顿量为：
[0073][0074]
这里第一求和项表示磁性杂质之间的相互作用，第二求和项表示磁性杂质与外加磁场之间的相互作用。可以按前述方式通过代换将其转换为最大割问题，并获得相应的有权无向图。
[0075]
具体来讲，将自旋玻璃系统中的磁性杂质（magnetic impurities）1,2
…
n以及外加磁场0作为顶点，磁性杂质之间存在相互作用时，相应的磁性杂质对应的顶点之间存在边，且该边的权重为相互作用的值的负数，即。
[0076]
磁性杂质与外加磁场之间存在相互作用时，磁性杂质与外加磁场对应的顶点之间存在边，该边的权重为磁场强度（strength of the magnetic field）的负数，即，如此可以得到该问题对应的有权无向图。
[0077]
换言之，所述有权无向图的顶点表示所述自旋玻璃系统中的磁性杂质和外加磁场，所述有权无向图的边表示所述磁性杂质之间存在的相互作用以及所述外加磁场作用于所述磁性杂质的磁场强度，所述有权无向图的边的权重为对应的所述相互作用的值的负数以及对应的所述磁场强度的负数。
[0078]
相应的最大割目标函数为：；
[0079]
原哈密顿量可通过该目标函数重新表述为：；其中第二项对于给定问题为常值。
[0080]
步骤s101执行完成后，进入执行步骤s102，在步骤s102中，可以根据有权无向图的所有边的权重来计算初始的割权，可选地，在步骤s102中，计算所述有权无向图的初始的割权，包括：
[0081]
将所述有权无向图的所有边的权重相加之和的一半作为所述有权无向图的初始的割权。
[0082]
以图2所示的有权无向图为例，计算其所有边的权重之和，再将权重之和除以2得到结果16作为该有权无向图的初始的割权。
[0083]
在步骤s103中，可以搜索有权无向图中权重的绝对值最大的边作为目标边，例如可以对其权重的绝对值进行排序，选择绝对值最大的边作为目标边。然后再将该目标边的权重绝对值的一半，加至初始的割权，以对割权进行更新。
[0084]
参见图2，其中的有权无向图共有5个顶点，分别为顶点1、顶点2、顶点3、顶点4、顶点5，通过图中的圆圈表示，圆圈中数字表示顶点序号，圆圈之间的连线表示相应顶点之间的边，边上的数字表示该边的权重，例如数字10所在的连线表示顶点2和顶点4之间的边，该边可以通过序数对（2,4）表示，10为顶点2和顶点4之间的边的权重，其它边依次类推，此处不再赘述。
[0085]
以图2的有权无向图为例，该有权无向图中绝对值最大的权重为10，对应的目标边为（2,4），然后将初始的割权16加上其割权绝对值的一半即5，得到更新后的割权为21。参见图3，确定目标边后，可以将目标边（2,4）的连线加粗表示。
[0086]
在步骤s104中，根据目标边的权重的正负情况对目标边进行相应的边收缩（edge contraction）操作。在图论中，边收缩是一种从图中删除一条边的操作，同时合并被删除的边之前连接的两个顶点。对于有权无向图，若边收缩后，相应的边的权重采用加法进行更新，则该边收缩为常规式边收缩，若采用减法进行更新，则该边收缩为差分式边收缩。
[0087]
具体地，可以先判断目标边的权重的正负情况，若目标边的权重为正数，对目标边进行差分式边收缩，若目标边的权重为负数，对目标边进行常规式边收缩，同时由于边收缩会删除被收缩的目标边，合并目标边连接的两个顶点，同时对有权无向图中相应边的权重进行更新，因此有权无向图整体得到更新，得到更新后的有权无向图。
[0088]
沿用上述例子，由于目标边（2,4）的权重10为正数，因此对目标边（2,4）进行差分式边收缩，具体地可以随机选择目标边的两个邻接点中的一个顶点，将其合并至另一顶点，并对相应的边和权重进行更新。图3中，选择顶点4，将顶点4合并至顶点2，最终可以得到如图4所示的有权无向图。图4中，加粗的线表示对应的边（2,4）被收缩，边收缩后的有权无向图中不存在该边，同时，由于虚线圆圈表示对应的顶点4被收缩，边收缩后的有权无向图中不存在该顶点。
[0089]
可选地，在步骤s104中，对所述有权无向图中的所述目标边进行差分式边收缩，可以包括：
[0090]
s1041，确定与所述目标边邻接的目标顶点和待合并顶点。
[0091]
s1042，针对所述待合并顶点的待合并邻接边，若不存在对应于所述待合并邻接边的目标邻接边，则创建权重为0的该目标邻接边，所述目标邻接边为所述目标顶点与所述待合并顶点的其它邻接顶点的连接边。
[0092]
s1043，将所述待合并顶点合并至所述目标顶点。
[0093]
s1044，将所述待合并顶点的待合并邻接边合并至所述目标顶点的对应目标邻接边。
[0094]
s1045，将所述目标邻接边的权重减去所述待合并邻接边的权重，作为合并后的所述目标邻接边的权重。
[0095]
s1046，从所述有权无向图中删除所述目标边。
[0096]
在步骤s1041中，确定目标边邻接的两个顶点，并可以随机确定其中一个为目标顶点，另一个为待合并顶点，合并方向为待合并顶点合并至目标顶点。当然，在其它可能的实施方式中，也可以根据预设的规则来确定目标顶点和待合并顶点。沿用前述例子，对于图3中的目标边（2,4），确定其邻接的目标顶点为顶点2，待合并顶点为顶点4。
[0097]
步骤s1041执行完后，进入执行步骤s1042。在步骤s1042中，以图3所示的有权无向图为例，作为待合并顶点的顶点4的待合并邻接边（4,5）不存在目标邻接边，因此可以先创建一连接顶点2和顶点5的目标邻接边（2，5），其权重为0。为简化图示，图3中未示出边（2,5）。
[0098]
步骤s1042执行完后，进入执行步骤s1043。在步骤s1043中，将待合并顶点合并至目标顶点，合并后删除待合并顶点，保留目标顶点。沿用前述例子，将顶点4合并至顶点2，顶点4从有权无向图中删除，顶点2保留。
[0099]
步骤s1043执行完成后，进入执行步骤s1044。在步骤s1044中，待合并邻接边的一个邻接点为待合并顶点，目标邻接边的一个邻接点为目标顶点，且待合并邻接边的另一个邻接点与目标邻接边的另一个邻接点相同。将待合并邻接边合并至目标邻接边，合并后，待合并邻接边被删除，目标邻接边保留。
[0100]
沿用前述例子，参见图3，对于作为目标顶点的顶点2，以及作为待合并顶点的顶点4，边（2,1）为顶点4的其它邻接顶点1与顶点2的连接边，边（2,3）为顶点4的其它邻接顶点3与顶点2的连接边，因此边（2,1）和边（2,3）分别为边（4,1）和边（4,3）的目标邻接边，边（4,1）和边（4,3）为顶点4的待合并邻接边，进而将边（4,1）合并至对应的边（2,1），将边（4,3）合并至对应的边（2,3），最终边（2,1）和边（2,3）保留，边（4,1）和边（4,3）被删除。同理，还将边（4,5）合并至上述创建的权重为0的目标边（2,5）。
[0101]
步骤s1044执行完成后，进入执行步骤s1045。在步骤s1045中，将合并前的目标邻接边的权重减去待合并邻接边的权重，作为合并后的目标邻接边的权重。沿用前述例子，参见图3，边（2,1）的权重减去边（4,1）的权重之差为5，进而将5作为合并后的边（2,1）的权重，边（2,3）的权重减去边（4,3）的权重之差为-4，进而将-4作为合并后的边（2,3）的权重。边（2,5）的权重减去边（4,5）的权重之差为-2，进而将-2作为合并后的边（2,5）的权重。
[0102]
步骤s1045执行完成后，进入执行步骤s1046。在步骤s1046中，将目标边从有权无向图中删去即可。沿用前述例子，将图3中的目标边（2,4）删除，最终得到图4中的有权无向图。
[0103]
在一种可能的实施方式中，步骤s1043至步骤s1046也可以同时执行，对于相关步骤的执行顺序，本公开不作具体限制，例如步骤s1046也可以在步骤s1043之前执行。
[0104]
在其它可能的实施方式中，差分式边收缩也可以采用其它的边收缩方式，例如其可以为上述差分式边收缩的变体，对此本公开不再赘述。
[0105]
步骤s104执行完毕后，可以对有权无向图中的边的收缩情况进行判断，当更新后
的有权无向图中存在边未被收缩时，即有权无向图中是否还有剩下的边，若存在边未被收缩，进入执行步骤s105，此时可返回执行步骤s103。若所有边被收缩，则进入执行步骤s106。
[0106]
沿用前述例子，得到图4的有权无向图后，由于其存在边未被收缩，返回执行步骤s103，确定其中的绝对值最大的目标边为（1,5），同时参见图5，将边（1,5）加粗表示其为目标边，同时根据其所述的方法对割权21进行更新得到24.5。由于该边的权重为正数，对其进行差分式边收缩，可以将顶点1合并至顶点5，相应得到图6的有权无向图，收缩过程参见前述描述。此时由于存在边（2,5）和边（2,3）未被收缩，返回执行步骤s103，确定其中的绝对值最大的目标边为（2,5），并相应更新割权为28，参见图7，对边（2,5）加粗表示，由于该边的权重为负数，对其进行常规式边收缩，可以将顶点2合并至顶点5，得到图8所示的有权无向图。此时，还存在边（3,5）未被收缩，再次返回执行步骤s103，确定边（3,5）为目标边，相应更新割权为30，并对其进行常规式边收缩得到如图9所示的各个顶点的关系图。此时所有边被收缩，进入执行步骤s106。
[0107]
可选地，在步骤s104中，对所述有权无向图中的所述目标边进行常规式边收缩，可以包括：
[0108]
s104a，确定与所述目标边邻接的目标顶点和待合并顶点。
[0109]
s104b，针对所述待合并顶点的待合并邻接边，若不存在对应于所述待合并邻接边的目标邻接边，则创建权重为0的该目标邻接边，所述目标邻接边为所述目标顶点与所述待合并顶点的其它邻接顶点的连接边。
[0110]
s104c，将所述待合并顶点合并至所述目标顶点。
[0111]
s104d，将所述待合并顶点的待合并邻接边合并至所述目标顶点的对应目标邻接边。
[0112]
s104e，将所述目标邻接边的权重加上所述待合并邻接边的权重，作为合并后的所述目标邻接边的权重。
[0113]
s104f，从所述有权无向图中删除所述目标边。
[0114]
具体地，步骤s104a至步骤s104d可以分别参见步骤s1041至步骤s1044的描述。
[0115]
步骤s104d执行完后，可以进入执行步骤s104e。在步骤s104e中，将合并前的目标邻接边的权重加上待合并邻接边的权重，作为合并后的目标邻接边的权重。
[0116]
步骤s104e执行完后，可以进入执行步骤s104f。步骤s104f可以参见步骤s1046的描述。在一种可能的实施方式中，步骤s104c至步骤s104f也可以同时执行，对于相关步骤的执行顺序，本公开不作具体限制，例如步骤s104f也可以在步骤s104c之前执行。
[0117]
沿用前述例子，对于图6中的边（2,5）进行常规式边收缩时，确定该边的目标顶点为顶点5，待合并顶点为顶点2，将顶点2合并至顶点5，即删除顶点2，保留顶点5。此时不存在待合并邻接边和目标邻接边，故将边（2,5）删除得到图8所示的有权无向图。边（3,5）的常规式边收缩过程可以参见该过程。
[0118]
在步骤s106中，根据每次迭代过程中目标边被确定时的权重的正负情况，将原本有权无向图中的顶点划分为两个集合，同时将最后更新后的割权输出，进而完成对于最大割问题的求解。
[0119]
沿用前述例子，在图2的有权无向图的边收缩过程中，目标边（2,5）和目标边（3,5）的权重为负数，因此顶点2、顶点3与顶点5属于相同集合；目标边（2,4）和目标边（1,5）的权
重为正数，进而顶点1和顶点5属于不同集合，顶点4和顶点2属于不同集合；最终，顶点2、顶点3与顶点5同属于一个集合，顶点1和顶点4同属于另一个集合。
[0120]
通过上述技术方案，获取待求解的最大割问题对应的有权无向图，计算其初始的割权后，根据目标边的权重的正负情况，分别进行常规式边收缩以及差分式边收缩，以将劣汰型算法和优胜型算法结合，直至有权无向图的所有边被收缩后，根据目标边的权重的正负情况，将有权无向图中的顶点划分为两个集合，并输出最后更新后的割权，以完成对于最大割问题的求解。通过结合利用两种边收缩的优势，在可接受时间内完成对最大割问题的求解，提高了对于最大割问题求解的效率，有利于解决超大规模集成电路设计等技术领域的相关问题。
[0121]
此外，本公开的最大割问题求解方法将稳定子的思想与图论中的边收缩操作相结合，得到了最大割问题的一种专用算法，也可以叫做稳定子-最大割算法。这一算法将前人提出的边收缩与差分式边收缩算法自然地融合在一起，并大幅提高了求解性能。与直接使用通用稳定子算法相比，其求解效率大大提升。这一直观而快捷的算法可以作为一个构造型的子模块加以调用，从而为开发最大割问题的高精度算法奠定基础。
[0122]
可选地，在所述目标边的权重为负数时，所述最大割问题求解方法还包括：设置一正号的标记符号，以标记所述目标边；在所述目标边的权重为正数时，所述最大割问题求解方法还包括：设置一负号的标记符号，以标记所述目标边；所述基于每一所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，包括：在所述标记符号为正号时，确定所述目标边的两个邻接顶点属于同一集合，在所述标记符号为负号时，确定所述目标边的两个邻接顶点属于不同集合，以将所述有权无向图中的顶点划分为两个集合。
[0123]
具体地，在判定目标边的权重为负数时，设置一个正号作为该目标边的标记符号，以便于进行常规式边收缩时基于该正号执行相应权重的加法运算。在判定目标边的权重为正数时，设置一个负号作为该目标边的标记符号，以便于进行差分式边收缩时基于该负号执行相应权重的减法运算。此外，正负号的标记也便于后续进行顶点的划分。在一种可能的实施方式中，标记符号为正号的目标边的两个邻接顶点位于割的同侧，属于相同集合，标记符号为负号的两个邻接顶点位于割的异侧，属于不同集合。
[0124]
对于上述最大割问题求解方法中求解最大割问题步骤的复杂度。注意到其最耗时的步骤是每次选取绝对值最大的边。如果直接在所有边中选取，复杂度为；如果预先排序，并在每个步骤更新排序，复杂度可以降低为；如果对每个顶点标记其权重绝对值最大的邻边，并在每一步更新该标记，则复杂度为，相比于其它求解最大割的方法有较大的提升。
[0125]
在一些tsp（traveling salesman problem，旅行商问题）实例上用前述稳定子算法和本公开的方法分别计算图的最大割，然后比较其时间消耗，结果如下表：
[0126][0127]
在上表中，通用算法表示前述通用稳定子算法，专用算法表示本公开的最大割问题求解方法。从表中可以看出，本公开的方法在保持求解性能的同时，大大提高了求解效率。其次，我们关注本公开方法的近似比率。最大割问题求解方法的性能可以用近似比率来衡量。在知晓最优解的情况下，可以定义近似比率如下：
[0128][0129]
其中，为割权，为最优解对应的割权，而在最优解未知的情况下，可以用总权重代替它来定义：
[0130][0131]
其中，为总权重，在初始权重均非负时，我们有。所以是r的一个下界，即。
[0132]
对于求解最大割问题的常规式边收缩方法，其近似比率，本公开所述的最大割问题求解方法则满足，可见相较于常规式边收缩方法，本公开所述方法有较大的提升，并在形式上统一了常规式边收缩和差分式边收缩，解决了差分式边收缩的方向问题。此外，本公开的最大割问题求解方法在实际求解中的性能跟前述的通用稳定子算法完全一样。因此，它远远优于边收缩，在一定程度上优于差分式边收缩和sg3算法，并在某些实例上可与 gw算法相提并论。
[0133]
图10是根据一示例性实施例示出的一种最大割问题求解装置的框图，参见图10，所述装置1000包括：获取模块1010，用于获取待求解的最大割问题对应的有权无向图；计算模块1020，用于计算所述有权无向图的初始的割权；确定模块1030，用于确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半，得到更新后的割权；边收缩模块1040，用于在所述目标边的权重为负数时，对所述有权无向图中的所述目标边进行常规式边收缩，在所述目标边的权重为正数时，对所述有权无向图中的所述目标边进行差分式边收缩，得到更新后的有权无向图；返回模块1050，用于在所述更新后的有权无向图中存在边未被收缩时，返回执行所述确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权
重的绝对值的一半的步骤；划分输出模块1060，用于在所述更新后的有权无向图中所有边均被收缩时，基于每一所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，并输出最后更新后的割权。
[0134]
可选地，所述边收缩模块1040还用于：确定与所述目标边邻接的目标顶点和待合并顶点；针对所述待合并顶点的待合并邻接边，若不存在对应于所述待合并邻接边的目标邻接边，则创建权重为0的该目标邻接边，所述目标邻接边为所述目标顶点与所述待合并顶点的其它邻接顶点的连接边；将所述待合并顶点合并至所述目标顶点；将所述待合并顶点的待合并邻接边合并至所述目标顶点的对应目标邻接边；将所述目标邻接边的权重加上所述待合并邻接边的权重，作为合并后的所述目标邻接边的权重；从所述有权无向图中删除所述目标边。
[0135]
可选地，所述边收缩模块1040还用于：确定与所述目标边邻接的目标顶点和待合并顶点；针对所述待合并顶点的待合并邻接边，若不存在对应于所述待合并邻接边的目标邻接边，则创建权重为0的该目标邻接边，所述目标邻接边为所述目标顶点与所述待合并顶点的其它邻接顶点的连接边；将所述待合并顶点合并至所述目标顶点；将所述待合并顶点的待合并邻接边合并至所述目标顶点的对应目标邻接边；将所述目标邻接边的权重减去所述待合并邻接边的权重，作为合并后的所述目标邻接边的权重；从所述有权无向图中删除所述目标边。
[0136]
可选地，所述计算模块1020还用于：将所述有权无向图的所有边的权重相加之和的一半作为所述有权无向图的初始的割权。
[0137]
可选地，所述装置1000还包括：正号设置模块，用于在所述目标边的权重为负数时，设置一正号的标记符号，以标记所述目标边；负号设置模块，用于在所述目标边的权重为正数时，设置一负号的标记符号，以标记所述目标边；所述划分输出模块1060还用于：在所述标记符号为正号时，确定所述目标边的两个邻接顶点属于同一集合，在所述标记符号为负号时，确定所述目标边的两个邻接顶点属于不同集合，以将所述有权无向图中的顶点划分为两个集合。
[0138]
关于上述实施例中的装置，其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述，此处将不做详细阐述说明。
[0139]
图11是根据一示例性实施例示出的一种电子设备的框图。如图11所示，该电子设
备700可以包括：处理器701，存储器702。该电子设备700还可以包括多媒体组件703，输入/输出（i/o）接口704，以及通信组件705中的一者或多者。
[0140]
其中，处理器701用于控制该电子设备700的整体操作，以完成上述的最大割问题求解方法中的全部或部分步骤。存储器702用于存储各种类型的数据以支持在该电子设备700的操作，这些数据例如可以包括用于在该电子设备700上操作的任何应用程序或方法的指令，以及应用程序相关的数据，例如联系人数据、收发的消息、图片、音频、视频等等。该存储器702可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，例如静态随机存取存储器（static random access memory，简称sram），电可擦除可编程只读存储器（electrically erasable programmable read-only memory，简称eeprom），可擦除可编程只读存储器（erasable programmable read-only memory，简称eprom），可编程只读存储器（programmable read-only memory，简称prom），只读存储器（read-only memory，简称rom），磁存储器，快闪存储器，磁盘或光盘。多媒体组件703可以包括屏幕和音频组件。其中屏幕例如可以是触摸屏，音频组件用于输出和/或输入音频信号。例如，音频组件可以包括一个麦克风，麦克风用于接收外部音频信号。所接收的音频信号可以被进一步存储在存储器702或通过通信组件705发送。音频组件还包括至少一个扬声器，用于输出音频信号。i/o接口704为处理器701和其他接口模块之间提供接口，上述其他接口模块可以是键盘，鼠标，按钮等。这些按钮可以是虚拟按钮或者实体按钮。通信组件705用于该电子设备700与其他设备之间进行有线或无线通信。无线通信，例如wi-fi，蓝牙，近场通信（near field communication，简称nfc），2g、3g、4g、nb-iot、emtc、或其他5g等等，或它们中的一种或几种的组合，在此不做限定。因此相应的该通信组件705可以包括：wi-fi模块，蓝牙模块，nfc模块等等。
[0141]
在一示例性实施例中，电子设备700可以被一个或多个应用专用集成电路（application specific integrated circuit，简称asic）、数字信号处理器（digital signal processor，简称dsp）、数字信号处理设备（digital signal processing device，简称dspd）、可编程逻辑器件（programmable logic device，简称pld）、现场可编程门阵列（field programmable gate array，简称fpga）、控制器、微控制器、微处理器或其他电子元件实现，用于执行上述的最大割问题求解方法。
[0142]
在另一示例性实施例中，还提供了一种包括程序指令的计算机可读存储介质，该程序指令被处理器执行时实现上述的最大割问题求解方法的步骤。例如，该计算机可读存储介质可以为上述包括程序指令的存储器702，上述程序指令可由电子设备700的处理器701执行以完成上述的最大割问题求解方法。
[0143]
以上结合附图详细描述了本公开的优选实施方式，但是，本公开并不限于上述实施方式中的具体细节，在本公开的技术构思范围内，可以对本公开的技术方案进行多种简单变型，这些简单变型均属于本公开的保护范围。
[0144]
另外需要说明的是，在上述具体实施方式中所描述的各个具体技术特征，在不矛盾的情况下，可以通过任何合适的方式进行组合，为了避免不必要的重复，本公开对各种可能的组合方式不再另行说明。
[0145]
此外，本公开的各种不同的实施方式之间也可以进行任意组合，只要其不违背本公开的思想，其同样应当视为本公开所公开的内容。

技术特征：
1.一种最大割问题求解方法，其特征在于，所述方法包括：获取待求解的最大割问题对应的有权无向图；计算所述有权无向图的初始的割权；确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半，得到更新后的割权；在所述目标边的权重为负数时，对所述有权无向图中的所述目标边进行常规式边收缩，在所述目标边的权重为正数时，对所述有权无向图中的所述目标边进行差分式边收缩，得到更新后的有权无向图；在所述更新后的有权无向图中存在边未被收缩时，返回执行所述确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半的步骤；在所述更新后的有权无向图中所有边均被收缩时，基于每一所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，并输出最后更新后的割权。2.根据权利要求1所述的方法，其特征在于，所述对所述有权无向图中的所述目标边进行常规式边收缩，包括：确定与所述目标边邻接的目标顶点和待合并顶点；针对所述待合并顶点的待合并邻接边，若不存在对应于所述待合并邻接边的目标邻接边，则创建权重为0的该目标邻接边，所述目标邻接边为所述目标顶点与所述待合并顶点的其它邻接顶点的连接边；将所述待合并顶点合并至所述目标顶点；将所述待合并顶点的待合并邻接边合并至所述目标顶点的对应目标邻接边；将所述目标邻接边的权重加上所述待合并邻接边的权重，作为合并后的所述目标邻接边的权重；从所述有权无向图中删除所述目标边。3.根据权利要求1所述的方法，其特征在于，所述对所述有权无向图中的所述目标边进行差分式边收缩，包括：确定与所述目标边邻接的目标顶点和待合并顶点；针对所述待合并顶点的待合并邻接边，若不存在对应于所述待合并邻接边的目标邻接边，则创建权重为0的该目标邻接边，所述目标邻接边为所述目标顶点与所述待合并顶点的其它邻接顶点的连接边；将所述待合并顶点合并至所述目标顶点；将所述待合并顶点的待合并邻接边合并至所述目标顶点的对应目标邻接边；将所述目标邻接边的权重减去所述待合并邻接边的权重，作为合并后的所述目标邻接边的权重；从所述有权无向图中删除所述目标边。4.根据权利要求1所述的方法，其特征在于，所述计算所述有权无向图的初始的割权，包括：将所述有权无向图的所有边的权重相加之和的一半作为所述有权无向图的初始的割权。
5.根据权利要求1所述的方法，其特征在于，在所述目标边的权重为负数时，所述方法还包括：设置一正号的标记符号，以标记所述目标边；在所述目标边的权重为正数时，所述方法还包括：设置一负号的标记符号，以标记所述目标边；所述基于每一所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，包括：在所述标记符号为正号时，确定所述目标边的两个邻接顶点属于同一集合，在所述标记符号为负号时，确定所述目标边的两个邻接顶点属于不同集合，以将所述有权无向图中的顶点划分为两个集合。6.一种最大割问题求解装置，其特征在于，所述装置包括：获取模块，用于获取待求解的最大割问题对应的有权无向图；计算模块，用于计算所述有权无向图的初始的割权；确定模块，用于确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半，得到更新后的割权；边收缩模块，用于在所述目标边的权重为负数时，对所述有权无向图中的所述目标边进行常规式边收缩，在所述目标边的权重为正数时，对所述有权无向图中的所述目标边进行差分式边收缩，得到更新后的有权无向图；返回模块，用于在所述更新后的有权无向图中存在边未被收缩时，返回执行所述确定所述有权无向图中权重的绝对值最大的目标边，并将所述割权加上所述目标边权重的绝对值的一半的步骤；划分输出模块，用于在所述更新后的有权无向图中所有边均被收缩时，基于每一所述目标边的权重的正负情况，将所述有权无向图中的顶点划分为两个集合，并输出最后更新后的割权。7.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现权利要求1-5中任一项所述方法的步骤。8.一种电子设备，其特征在于，包括：存储器，其上存储有计算机程序；处理器，用于执行所述存储器中的所述计算机程序，以实现权利要求1-5中任一项所述方法的步骤。

技术总结
本公开涉及一种最大割问题求解方法、装置、存储介质和电子设备，所述方法包括：获取最大割问题对应的有权无向图；计算有权无向图的初始的割权；确定有权无向图中权重的绝对值最大的目标边，并将割权加上目标边权重的绝对值的一半，得到更新后的割权；在权重为负数时，对目标边进行常规式边收缩，在权重为正数时，对目标边进行差分式边收缩；在更新后的有权无向图中存在边未被收缩时，返回执行确定有权无向图中权重的绝对值最大的目标边，并将割权加上目标边权重的绝对值的一半的步骤；否则，基于每一目标边的权重的正负情况，将有权无向图中的顶点划分为两个集合，并输出最后更新后的割权。权。权。


技术研发人员：左芬 吴垂雄 王佳楠 吕川
受保护的技术使用者：微观纪元（合肥）量子科技有限公司
技术研发日：2023.06.28
技术公布日：2023/8/1