Sois prêt.

python3

import numpy as np, networkx as nx
from pulp import *
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
    """Utilitaire de création de variables"""
    var_count[0] += 1
    return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)
def calc(a, r):
    """Calculez la quantité de données acquises avec r comme emplacement d'installation"""
    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

résoudre_by_mip est une solution MIP. Renvoie l'emplacement d'installation.

python3

def solve_by_mip(a):
    """Résolvez le problème avec MIP et renvoyez l'emplacement d'installation"""
    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):
    """Ajouter une contrainte pour réduire la fonction objectif de 2 si e contient des variables"""
    if isinstance(e, LpAffineExpression):
        v = addvar()
        vv2.append(v)
        m += e - v <= 1

résoudre_by_graph est une solution de coupe minimale. Renvoyez également l'emplacement d'installation.

python3

def solve_by_graph(a):
    """Résolvez le problème avec le problème de coupure minimum et renvoyez l'emplacement d'installation"""
    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)

Comparons les résultats en définissant aléatoirement des points fixes d'une taille de 40 x 80.

python3

nn, nm = 40, 80 #Horizontal Vertical
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

―― Vous pouvez voir que les deux méthodes ont la même quantité de données acquises (rmip == rgrp). --MIP est plus de deux fois plus lent.

• En général, les solveurs dédiés sont plus rapides que les solveurs à usage général. ――Lorsque je l'ai confirmé séparément, le temps de calcul du solveur MIP seul était légèrement plus long que le temps de calcul de la coupe minimale. ――Bien que la théorie soit inconnue, la quantité de données acquises ne change pas même si le MIP est relâché linéairement, et le temps de calcul est légèrement plus rapide.

Site de référence

• Problème E. The Year of Code Jam: problème référencé
• Résoudre le "problème de brûlage et de remplissage" en utilisant la coupe minimale: Solution référencée

c'est tout