寻找可以解决涉及固定，简单的非方向图的组合问题的算法
我正处于创建算法来解决此问题的研究阶段：
这是一种能量最小化问题，我正在寻找灵感和类似的算法。
给定一个简单、无向的图。 假设每个节点都可以有一个由整数定义的类型。
我们在开始时给出了每种类型的数量，总数等于节点的数量，这样在解决方案中，每个节点将具有单一类型。
图中的每条边都有一个能量值。 该能量值是根据给定的关系矩阵计算得出的，该关系矩阵告诉您两种类型节点之间的能量值。
我们想要定义每个节点，使得边的总能量最小。
示例：
能量矩阵：
| - | a | b |
|---|---|---|
| a | 1 | 2 |
| b | 2 | 3 |
图
A - B - A 的
总能量为 2 + 2
而
A - A - B 的
总能量为 1 + 2
我在有关书籍中看过算法，这看起来像是一个组合问题。
I am in the research phase of the creation of an algorithm to resolve this problem :
This is sort of an energy minimization problem and I'm looking for inspiration and similar algorithms.
Given a graph that is simple, undirected.
Lets say that each node can have a type defined by an integer.
We are given a quantity of each type at the start, the total quantity is equal to the number of nodes such that in the solution, each node will have a single type.
Each edge in the graph will have a energy value.
This energy value is calculated from a given relationship matrix that tells you the energy value between two types of nodes.
We want to define each node such that the energy total of the edges is minimal.
Example :
Energy matrix :
| - | a | b |
|---|---|---|
| a | 1 | 2 |
| b | 2 | 3 |
Graph
A - B - A
Would have an energy total of 2 + 2
while
A - A - B
Would have an energy total of 1 + 2
I have looked in books about algorithms, and this seems like a combinatorial problem.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我相信您的问题可以简化为（电容性）设施位置问题这是一个被认为是一个被认为是一个问题 Might-integer程序。通常，通常使用诸如 scip scip ，CPLEX，GUOUROBI等等。
所服务的总能量可以被认为是设施位置的总需求，服务变量可能是任何东西，客户，工厂等。
建模问题限制需要注意。一一添加它们可能会降低编写它们的复杂性。
I believe your problem can be reduced to a (Capacitated) Facility Location problem, which is considered a Mixed-Integer Program. There are multiple ways of solving MIP programs, usually, by using a solver such as SCIP, CPLEX, Gurobi, etc.
The total energy served could be thought of as the total demand in Facility Location, the serving variables could be anything, customers, factories, etc.
Modelling the problem constraints requires a heed. Adding them one by one may reduce the complexity of writing them.