57 lines
1.4 KiB
Python
57 lines
1.4 KiB
Python
import pulp
|
|
|
|
adj = {
|
|
0: [5],
|
|
1: [2,4,5],
|
|
2: [1,3,4],
|
|
3: [2,4,7,8,10],
|
|
4: [1,2,3,5,6,7],
|
|
5: [0,1,4,6,12],
|
|
6: [4,5,7,11,12],
|
|
7: [3,4,6,8,9,11],
|
|
8: [3,7,9,10,11,13],
|
|
9: [7,8,11],
|
|
10: [3,8,13,14],
|
|
11: [6,7,8,9,12,13],
|
|
12: [5,6,11,13,15],
|
|
13: [8,10,11,12,14,15],
|
|
14: [10,13,15],
|
|
15: [12,13,14]
|
|
}
|
|
|
|
n = 16
|
|
A = [[0 for _ in range(n)] for _ in range(n)]
|
|
|
|
# A[click][affected]
|
|
for click in range(n):
|
|
A[click][click] = 2
|
|
for affected in adj[click]:
|
|
A[click][affected] = 1
|
|
|
|
prob = pulp.LpProblem("Map_Burning_Optimal", pulp.LpMinimize)
|
|
|
|
x = [pulp.LpVariable(f"x{i+1}", lowBound=0, cat="Integer") for i in range(n)]
|
|
b = [pulp.LpVariable(f"b{i+1}", cat="Binary") for i in range(n)]
|
|
|
|
prob += pulp.lpSum(x)
|
|
|
|
# Pole startuje od -1, a końcowo ma być 3 albo 4
|
|
# czyli suma wpływów ma dać 4 albo 5
|
|
for j in range(n):
|
|
lhs = pulp.lpSum(A[k][j] * x[k] for k in range(n))
|
|
prob += lhs == 4 + b[j]
|
|
|
|
prob.solve(pulp.PULP_CBC_CMD(msg=0))
|
|
|
|
status = pulp.LpStatus[prob.status]
|
|
objective = pulp.value(prob.objective)
|
|
solution_x = [int(pulp.value(var)) for var in x]
|
|
solution_v = [
|
|
-1 + sum(A[k][j] * solution_x[k] for k in range(n))
|
|
for j in range(n)
|
|
]
|
|
|
|
print(f"Status: {status}")
|
|
print(f"Minimal total clicks: {objective}")
|
|
print("Clicks per pole (x1 to x16):", solution_x)
|
|
print("Final burns per pole (v1 to v16):", solution_v) |