optimization - 使用 ORtools 求解器进行图形着色的目标函数
问题描述
我写了一个 cp 函数来用 ORtools 解决图形着色
(最小化颜色使用,当边缘上每两个顶点的颜色需要不同时)我得到奇怪的结果,这不是最优的,我不知道为什么 - 我认为我的目标函数是错误的,或者我的约束公式是错误的,任何帮助? 谢谢
def cp_with_ortools(node_count, edge_count, edges, M, solution, max_degree):
global colors
from ortools.sat.python import cp_model
solution = [0] * (node_count)# list of colors to nodes initialized with 0
# Creates the model.
model = cp_model.CpModel()
# Creates the variables.
for i in range(node_count):
solution[i] = model.NewIntVar(0, int(node_count), '')
#shouldnt be max_degree? isnt working..
# Adds constraint
for edge in edges:
model.Add(solution[edge[0]] != solution[edge[1]])
# Create the objective function
obj_var = model.NewIntVar(0, node_count, 'makespan')
model.AddMaxEquality(obj_var,solution)
model.Minimize(obj_var)
#model.Minimize(len(set(solution)))
#model.Minimize(sum(solution)))
# Creates a solver and solves the model.
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
colors = [solver.Value(solution[i]) for i in range(node_count)]
return colors
解决方案
推荐阅读
- javascript - 上传前预览文件名
- python - 如何在python中使用正则表达式在下面的行中添加一个单词?
- css - CSS 固定元素导致跳转到顶部
- php - 如何在laravel中的2个表之间建立关系
- c++ - 为什么 std::uniform_real_distribution::max() 返回独占上限?
- javascript - 如何将简单的 JS 导入 Angular 组件
- c++ - 使用 luaL_ref 获取对表中用户数据的引用?
- javascript - Javascript自动运行?
- mysql - 如何在mysql中使用一个SQL查询选择多个静态行
- java - 从 ContactsContract 获取电话号码失败