Sich fertig machen.

python3

import numpy as np, networkx as nx
from pulp import *
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
    """Dienstprogramm zur Variablenerstellung"""
    var_count[0] += 1
    return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)
def calc(a, r):
    """Berechnen Sie die Menge der erfassten Daten mit r als Installationsort"""
    b = a.copy()
    b[b > 1] = 0
    for x, y in r:
        b[y, x] = 1
    s = b.sum() * 3
    for y in range(0, b.shape[0], 2):
        for x in range(b.shape[1]):
            s -= 2 * b[y, x] * b[y+1,x]
            if x:
                s -= 2 * b[y, x] * b[y+1,x-1]
            if y:
                s -= 2 * b[y, x] * b[y-1,x]
    return s

Solve_by_mip ist eine MIP-Lösung. Gibt den Installationsort zurück.

python3

def solve_by_mip(a):
    """Lösen Sie das Problem mit MIP und geben Sie den Installationsort zurück"""
    nm, nn = a.shape
    b = a.astype(object)
    vv1 = [addvar(cat=LpBinary) for _ in range((b > 1).sum())]
    b[b > 1] = vv1
    vv2 = []
    m = LpProblem(sense=LpMaximize)
    for y in range(0, nm, 2):
        for x in range(nn):
            chk(m, vv2, b[y,x] + b[y+1,x])
            if x: chk(m, vv2, b[y,x] + b[y+1,x-1])
            if y: chk(m, vv2, b[y,x] + b[y-1,x])
    m += 3 * lpSum(vv1) - 2 * lpSum(vv2)
    m.solve()
    return [(x, y) for x in range(nn) for y in range(nm)
            if isinstance(b[y,x], LpVariable) and value(b[y, x]) > 0.5]
def chk(m, vv2, e):
    """Wenn e Variablen enthält, fügen Sie eine Einschränkung hinzu, die die Zielfunktion um 2 reduziert, wenn beide 1 sind."""
    if isinstance(e, LpAffineExpression):
        v = addvar()
        vv2.append(v)
        m += e - v <= 1

Solve_by_graph ist eine minimale Schnittlösung. Geben Sie auch den Installationsort zurück.

python3

def solve_by_graph(a):
    """Lösen Sie das Problem mit dem Minimum-Cut-Problem und geben Sie den Installationsort zurück"""
    nm, nn = a.shape
    g = nx.DiGraph()
    for y in range(0, nm, 2):
        for x in range(nn):
            if a[y, x] == 0: # off
                g.add_edge('s', (x,y), capacity=7)
            elif a[y, x] == 1: # on
                g.add_edge((x,y), 't', capacity=7)
            else:
                g.add_edge('s', (x,y), capacity=0)
                g.add_edge((x,y), 't', capacity=3)
            if a[y+1, x] == 0: # off
                g.add_edge((x,y+1), 't', capacity=7)
            elif a[y+1, x] == 1: # on
                g.add_edge('s', (x,y+1), capacity=7)
            else:
                g.add_edge('s', (x,y+1), capacity=3)
                g.add_edge((x,y+1), 't', capacity=0)
            g.add_edge((x,y+1), (x,y), capacity=2)
            if x:
                g.add_edge((x-1,y+1), (x,y), capacity=2)
            if y:
                g.add_edge((x,y-1), (x,y), capacity=2)
    r = []
    for s in nx.minimum_cut(g, 's', 't')[1]:
        b = 's' in s
        for t in s:
            if isinstance(t, str): continue
            x, y = t
            if a[y, x] > 1 and b == (y%2 != 0):
                r.append((x, y))
    return sorted(r)

Vergleichen wir die Ergebnisse, indem wir zufällig Fixpunkte in einer Größe von 40 x 80 festlegen.

python3

nn, nm = 40, 80 #Horizontal, Vertikal
np.random.seed(1)
a = np.random.randint(0, 6, (nm, nn)) # 0; fix off, 1: fix on, ow:select

%time rmip = calc(a, solve_by_mip(a))
%time rgrp = calc(a, solve_by_graph(a))
print(rmip == rgrp)
>>>
Wall time: 455 ms
Wall time: 185 ms

True

• Sie können sehen, dass beide Methoden die gleiche Menge an erfassten Daten haben (rmip == rgrp). --MIP ist mehr als doppelt so langsam.
• Im Allgemeinen sind dedizierte Löser schneller als Allzwecklöser. ――Wenn ich es separat bestätigte, war die Berechnungszeit des MIP-Lösers allein etwas länger als die Berechnungszeit des Mindestschnitts. ――Obwohl die Theorie unbekannt ist, ändert sich die Menge der erfassten Daten nicht, selbst wenn der MIP linear entspannt ist und die Berechnungszeit etwas schneller ist.

Referenzseite

• Problem E. Das Jahr des Code-Staus: Problem, auf das verwiesen wird
• Lösen Sie das "Burn-Filling-Problem" mit dem Mindestschnitt: Referenzierte Lösung

das ist alles