Frage Wie hoch sind die Mindestkosten für die Verbindung aller Inseln?


Es gibt ein Gitter der Größe N x M. Einige Zellen sind Inseln bezeichnet mit "0" und die anderen sind Wasser. Jede Wasserzelle hat eine Nummer, die die Kosten einer Brücke anzeigt, die auf dieser Zelle hergestellt wird. Sie müssen die minimalen Kosten finden, für die alle Inseln verbunden werden können. Eine Zelle ist mit einer anderen Zelle verbunden, wenn sie eine Kante oder einen Scheitelpunkt teilt.

Welcher Algorithmus kann zur Lösung dieses Problems verwendet werden?
Bearbeiten: Was kann als Brute-Force-Ansatz verwendet werden, wenn die Werte von N, M sehr klein sind, sagen wir NxM <= 100?

Beispiel: In dem gegebenen Bild zeigen grüne Zellen Inseln an, blaue Zellen zeigen Wasser an und hellblaue Zellen zeigen die Zellen an, auf denen eine Brücke hergestellt werden sollte. Also für das folgende Bild wird die Antwort sein 17.

http://i.imgur.com/ClcboBy.png

Anfangs dachte ich daran, alle Inseln als Knoten zu markieren und jedes Inselpaar durch eine kürzeste Brücke zu verbinden. Dann könnte das Problem auf Minimum Spanning Tree reduziert werden, aber in diesem Ansatz verpasste ich den Fall, wo Kanten sich überlappen. BeispielsweiseIm folgenden Bild ist die kürzeste Entfernung zwischen zwei Inseln 7(markiert in gelb), also mit Minimum Spanning Trees die Antwort wäre 14, aber die Antwort sollte sein 11 (hellblau markiert).

image2


75
2018-05-31 08:57


Ursprung


Antworten:


Um dieses Problem anzugehen, würde ich ein Integer-Programmier-Framework verwenden und drei Sätze von Entscheidungsvariablen definieren:

  • x_ij: Eine binäre Indikatorvariable dafür, ob wir eine Brücke am Wasserstandort (i, j) bauen.
  • y_ijbcn: Ein binärer Indikator dafür, ob der Wasserort (i, j) der n-te Ort ist, der Insel b mit Insel c verbindet.
  • l_bc: Eine binäre Indikatorvariable, ob die Inseln b und c direkt miteinander verbunden sind (man kann auch nur auf Brückenquadraten von b nach c laufen).

Für Brückenbaukosten c_ij, ist der objektive Wert zu minimieren sum_ij c_ij * x_ij. Wir müssen dem Modell folgende Einschränkungen hinzufügen:

  • Wir müssen sicherstellen, dass y_ijbcn Variablen sind gültig. Wir können immer nur einen Wasserplatz erreichen, wenn wir dort eine Brücke bauen y_ijbcn <= x_ij für jeden Wasserstandort (i, j). Des Weiteren, y_ijbc1 muss gleich 0 sein, wenn (i, j) nicht an Insel b grenzt. Schließlich, für n> 1, y_ijbcn kann nur verwendet werden, wenn in Schritt n-1 eine benachbarte Wasserstelle verwendet wurde. Definieren N(i, j) um die benachbarten Wasserquadrate (i, j) zu sein, entspricht dies y_ijbcn <= sum_{(l, m) in N(i, j)} y_lmbc(n-1).
  • Wir müssen sicherstellen, dass l_bc Variablen werden nur gesetzt, wenn b und c verknüpft sind. Wenn wir definieren I(c) um die Orte zu sein, die an Insel c grenzen, kann dies mit erreicht werden l_bc <= sum_{(i, j) in I(c), n} y_ijbcn.
  • Wir müssen sicherstellen, dass alle Inseln direkt oder indirekt miteinander verbunden sind. Dies kann auf folgende Weise erreicht werden: Für jede nicht leere echte Teilmenge S von Inseln muss mindestens eine Insel in S mit mindestens einer Insel im Komplement von S verknüpft sein, die wir S 'nennen. In Constraints können wir dies implementieren, indem wir eine Constraint für jede nichtleere Menge S der Größe <= K / 2 hinzufügen (wobei K die Anzahl der Inseln ist), sum_{b in S} sum_{c in S'} l_bc >= 1.

Für eine Probleminstanz mit K Inseln, W Wasserquadraten und spezifizierter maximaler Pfadlänge N ist dies ein gemischtes ganzzahliges Programmiermodell mit O(K^2WN) Variablen und O(K^2WN + 2^K) Einschränkungen. Offensichtlich wird dies unlösbar werden, wenn die Problemgröße groß wird, aber es kann für die Größen, die Ihnen wichtig sind, lösbar sein. Um ein Gefühl für die Skalierbarkeit zu bekommen, werde ich es in Python mit dem Zellstoffpaket implementieren. Beginnen wir zuerst mit der kleineren 7 x 9 Karte mit 3 Inseln am Ende der Frage:

import itertools
import pulp
water = {(0, 2): 2.0, (0, 3): 1.0, (0, 4): 1.0, (0, 5): 1.0, (0, 6): 2.0,
         (1, 0): 2.0, (1, 1): 9.0, (1, 2): 1.0, (1, 3): 9.0, (1, 4): 9.0,
         (1, 5): 9.0, (1, 6): 1.0, (1, 7): 9.0, (1, 8): 2.0,
         (2, 0): 1.0, (2, 1): 9.0, (2, 2): 9.0, (2, 3): 1.0, (2, 4): 9.0,
         (2, 5): 1.0, (2, 6): 9.0, (2, 7): 9.0, (2, 8): 1.0,
         (3, 0): 9.0, (3, 1): 1.0, (3, 2): 9.0, (3, 3): 9.0, (3, 4): 5.0,
         (3, 5): 9.0, (3, 6): 9.0, (3, 7): 1.0, (3, 8): 9.0,
         (4, 0): 9.0, (4, 1): 9.0, (4, 2): 1.0, (4, 3): 9.0, (4, 4): 1.0,
         (4, 5): 9.0, (4, 6): 1.0, (4, 7): 9.0, (4, 8): 9.0,
         (5, 0): 9.0, (5, 1): 9.0, (5, 2): 9.0, (5, 3): 2.0, (5, 4): 1.0,
         (5, 5): 2.0, (5, 6): 9.0, (5, 7): 9.0, (5, 8): 9.0,
         (6, 0): 9.0, (6, 1): 9.0, (6, 2): 9.0, (6, 6): 9.0, (6, 7): 9.0,
         (6, 8): 9.0}
islands = {0: [(0, 0), (0, 1)], 1: [(0, 7), (0, 8)], 2: [(6, 3), (6, 4), (6, 5)]}
N = 6

# Island borders
iborders = {}
for k in islands:
    iborders[k] = {}
    for i, j in islands[k]:
        for dx in [-1, 0, 1]:
            for dy in [-1, 0, 1]:
                if (i+dx, j+dy) in water:
                    iborders[k][(i+dx, j+dy)] = True

# Create models with specified variables
x = pulp.LpVariable.dicts("x", water.keys(), lowBound=0, upBound=1, cat=pulp.LpInteger)
pairs = [(b, c) for b in islands for c in islands if b < c]
yvals = []
for i, j in water:
    for b, c in pairs:
        for n in range(N):
            yvals.append((i, j, b, c, n))

y = pulp.LpVariable.dicts("y", yvals, lowBound=0, upBound=1)
l = pulp.LpVariable.dicts("l", pairs, lowBound=0, upBound=1)
mod = pulp.LpProblem("Islands", pulp.LpMinimize)

# Objective
mod += sum([water[k] * x[k] for k in water])

# Valid y
for k in yvals:
    i, j, b, c, n = k
    mod += y[k] <= x[(i, j)]
    if n == 0 and not (i, j) in iborders[b]:
        mod += y[k] == 0
    elif n > 0:
        mod += y[k] <= sum([y[(i+dx, j+dy, b, c, n-1)] for dx in [-1, 0, 1] for dy in [-1, 0, 1] if (i+dx, j+dy) in water])

# Valid l
for b, c in pairs:
    mod += l[(b, c)] <= sum([y[(i, j, B, C, n)] for i, j, B, C, n in yvals if (i, j) in iborders[c] and B==b and C==c])

# All islands connected (directly or indirectly)
ikeys = islands.keys()
for size in range(1, len(ikeys)/2+1):
    for S in itertools.combinations(ikeys, size):
        thisSubset = {m: True for m in S}
        Sprime = [m for m in ikeys if not m in thisSubset]
        mod += sum([l[(min(b, c), max(b, c))] for b in S for c in Sprime]) >= 1

# Solve and output
mod.solve()
for row in range(min([m[0] for m in water]), max([m[0] for m in water])+1):
    for col in range(min([m[1] for m in water]), max([m[1] for m in water])+1):
        if (row, col) in water:
            if x[(row, col)].value() > 0.999:
                print "B",
            else:
                print "-",
        else:
            print "I",
    print ""

Dies dauert 1,4 Sekunden, um den Standardlöser aus dem Pulp-Paket (dem CBC-Solver) zu verwenden und gibt die richtige Lösung aus:

I I - - - - - I I 
- - B - - - B - - 
- - - B - B - - - 
- - - - B - - - - 
- - - - B - - - - 
- - - - B - - - - 
- - - I I I - - - 

Betrachten Sie als Nächstes das vollständige Problem oben in der Frage, das ein 13 x 14 Raster mit 7 Inseln ist:

water = {(i, j): 1.0 for i in range(13) for j in range(14)}
islands = {0: [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)],
           1: [(9, 0), (9, 1), (10, 0), (10, 1), (10, 2), (11, 0), (11, 1),
               (11, 2), (12, 0)],
           2: [(0, 7), (0, 8), (1, 7), (1, 8), (2, 7)],
           3: [(7, 7), (8, 6), (8, 7), (8, 8), (9, 7)],
           4: [(0, 11), (0, 12), (0, 13), (1, 12)],
           5: [(4, 10), (4, 11), (5, 10), (5, 11)],
           6: [(11, 8), (11, 9), (11, 13), (12, 8), (12, 9), (12, 10), (12, 11),
               (12, 12), (12, 13)]}
for k in islands:
    for i, j in islands[k]:
        del water[(i, j)]

for i, j in [(10, 7), (10, 8), (10, 9), (10, 10), (10, 11), (10, 12),
             (11, 7), (12, 7)]:
    water[(i, j)] = 20.0

N = 7

MIP-Solver erhalten oft relativ schnell gute Lösungen und verbringen dann viel Zeit damit, die Optimalität der Lösung zu beweisen. Mit dem gleichen Lösercode wie oben wird das Programm nicht innerhalb von 30 Minuten abgeschlossen. Sie können dem Solver jedoch eine Zeitüberschreitung bereitstellen, um eine ungefähre Lösung zu erhalten:

mod.solve(pulp.solvers.PULP_CBC_CMD(maxSeconds=120))

Dies ergibt eine Lösung mit dem Zielwert 17:

I I - - - - - I I - - I I I 
I I - - - - - I I - - - I - 
I I - - - - - I - B - B - - 
- - B - - - B - - - B - - - 
- - - B - B - - - - I I - - 
- - - - B - - - - - I I - - 
- - - - - B - - - - - B - - 
- - - - - B - I - - - - B - 
- - - - B - I I I - - B - - 
I I - B - - - I - - - - B - 
I I I - - - - - - - - - - B 
I I I - - - - - I I - - - I 
I - - - - - - - I I I I I I 

Um die Qualität der Lösungen, die Sie erhalten, zu verbessern, können Sie einen kommerziellen MIP-Löser verwenden (dies ist kostenlos, wenn Sie an einer akademischen Institution sind und wahrscheinlich nicht kostenlos sind). Zum Beispiel, hier ist die Leistung von Gurobi 6.0.4, wieder mit einem 2-Minuten-Zeitlimit (obwohl wir aus dem Lösungsprotokoll gelesen haben, dass der Löser die aktuell beste Lösung innerhalb von 7 Sekunden gefunden hat):

mod.solve(pulp.solvers.GUROBI(timeLimit=120))

Dies findet tatsächlich eine Lösung des objektiven Werts 16, eine bessere, als die OP von Hand finden konnte!

I I - - - - - I I - - I I I 
I I - - - - - I I - - - I - 
I I - - - - - I - B - B - - 
- - B - - - - - - - B - - - 
- - - B - - - - - - I I - - 
- - - - B - - - - - I I - - 
- - - - - B - - B B - - - - 
- - - - - B - I - - B - - - 
- - - - B - I I I - - B - - 
I I - B - - - I - - - - B - 
I I I - - - - - - - - - - B 
I I I - - - - - I I - - - I 
I - - - - - - - I I I I I I 

57
2018-06-24 21:51



Dieses Problem ist eine Variante des Steinerbaumes genannt Knotengewichteter Steinerbaum, spezialisierte eine bestimmte Klasse von Graphen. Kompakt, Knoten-gewichteten Steiner-Baum ist, angesichts einer Knoten-gewichteten ungerichteten Graphen, wo einige Knoten Terminals sind, finden Sie die günstigste Menge von Knoten einschließlich aller Terminals, die einen verbundenen Teilgraphen induziert. Leider kann ich bei einigen oberflächlichen Suchen keine Löser finden.

Um als Integer-Programm zu formulieren, erstellen Sie eine 0-1-Variable für jeden Nicht-Endpunkt-Knoten, und für alle Untersätze von Nicht-Endpunkt-Knoten, deren Entfernung von dem Startdiagramm zwei Terminals trennt, muss die Summe der Variablen in der Teilmenge sein 1. Dies führt zu viel Einschränkungen, also müssen Sie sie träge erzwingen, indem Sie einen effizienten Algorithmus für die Knotenkonnektivität (max. Fluss) verwenden, um eine maximal verletzte Bedingung zu erkennen. Entschuldigung für den Mangel an Details, aber es wird ein Aufwand sein, dies zu implementieren, selbst wenn Sie bereits mit Integer-Programmierung vertraut sind.


3
2018-06-16 16:58



Ein Brute-Force-Ansatz, in Pseudo-Code:

start with a horrible "best" answer
given an nxm map,
    try all 2^(n*m) combinations of bridge/no-bridge for each cell
        if the result is connected, and better than previous best, store it

return best

In C ++ könnte dies als geschrieben werden

// map = linearized map; map[x*n + y] is the equivalent of map2d[y][x]
// nm = n*m
// bridged = true if bridge there, false if not. Also linearized
// nBridged = depth of recursion (= current bridge being considered)
// cost = total cost of bridges in 'bridged'
// best, bestCost = best answer so far. Initialized to "horrible"
void findBestBridges(char map[], int nm,
   bool bridged[], int nBridged, int cost, bool best[], int &bestCost) {
   if (nBridged == nm) {
      if (connected(map, nm, bridged) && cost < bestCost) {
          memcpy(best, bridged, nBridged);
          bestCost = best;
      }
      return;
   }
   if (map[nBridged] != 0) {
      // try with a bridge there
      bridged[nBridged] = true;
      cost += map[nBridged];

      // see how it turns out
      findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost);         

      // remove bridge for further recursion
      bridged[nBridged] = false;
      cost -= map[nBridged];
   }
   // and try without a bridge there
   findBestBridges(map, nm, bridged, nBridged+1, cost, best, bestCost);
}

Nach dem ersten Aufruf (ich gehe davon aus, dass Sie Ihre 2D-Karten für einfaches Kopieren in 1D-Arrays umwandeln), bestCost enthält die Kosten für die beste Antwort, und best wird das Muster der Brücken enthalten, die es ergeben. Dies ist jedoch extrem langsam.

Optimierungen:

  • Wenn Sie ein "Brückenlimit" verwenden und den Algorithmus zum Erhöhen der maximalen Anzahl von Brücken ausführen, können Sie minimale Antworten finden, ohne den gesamten Baum zu untersuchen. Wenn eine 1-Brücken-Antwort gefunden würde, wäre sie 0 (nm) anstelle von O (2 ^ nm) - eine drastische Verbesserung.
  • Sie können die Suche vermeiden (indem Sie die Rekursion beenden; dies wird auch "Beschneiden" genannt), sobald Sie die Grenze überschritten haben bestCost, weil es keinen Sinn macht, danach zu schauen. Wenn es nicht besser werden kann, nicht weiter graben.
  • Das obige Beschneiden funktioniert besser, wenn Sie sich "gute" Kandidaten ansehen, bevor Sie sich "schlechte" Kandidaten anschauen (so wie es ist, werden Zellen alle von links nach rechts, von oben nach unten betrachtet). Eine gute Heuristik wäre, Zellen, die sich in der Nähe von mehreren nicht verbundenen Komponenten befinden, als höher prioritär einzustufen als Zellen, die dies nicht tun. Sobald Sie jedoch Heuristiken hinzufügen, beginnt Ihre Suche zu ähneln EIN* (Und Sie brauchen auch eine Art von Prioritätswarteschlange).
  • Doppelte Brücken und Brücken ins Nirgendwo sind zu vermeiden. Jede Bridge, die das Island-Netzwerk nicht trennt, wenn sie entfernt wird, ist redundant.

Ein allgemeiner Suchalgorithmus wie z EIN* ermöglicht eine viel schnellere Suche, obwohl das Finden besserer Heuristiken keine einfache Aufgabe ist. Für einen problemspezifischeren Ansatz unter Verwendung vorhandener Ergebnisse auf Steinerbäume, wie von @Gassa vorgeschlagen, ist der Weg zu gehen. Beachten Sie jedoch, dass das Problem, Steinerbäume auf orthogonalen Gittern zu bauen, NP-Complete lautet Papier von Garey und Johnson.

Wenn "gut genug" genug ist, kann ein genetischer Algorithmus wahrscheinlich schnell akzeptable Lösungen finden, solange Sie einige Schlüsselheuristiken zur bevorzugten Brückenplatzierung hinzufügen.


3
2018-06-08 16:42



Da dieses Problem in einem Gitter auftritt und Sie gut definierte Parameter haben, würde ich das Problem mit der systematischen Eliminierung des Problemraums durch die Schaffung eines minimalen Spannbaums angehen. Für mich macht es Sinn, wenn Sie dieses Problem mit Prims Algorithmus angehen.

Leider stößt man jetzt auf das Problem, das Gitter zu abstrahieren, um eine Menge von Knoten und Kanten zu erzeugen ... ergo ist das eigentliche Problem dieses Posts Wie konvertiere ich mein n x m Raster in {V} und {E}?

Dieser Umwandlungsprozess ist auf den ersten Blick wahrscheinlich NP-schwer aufgrund der schieren Anzahl möglicher Kombinationen (unter der Annahme, dass alle Kosten für den Wasserweg identisch sind). Um Instanzen zu behandeln, bei denen sich Pfade überschneiden, sollten Sie in Erwägung ziehen, a virtuelle Insel.

Wenn dies erledigt ist, führen Sie den Algorithmus von Prim aus und Sie sollten die optimale Lösung finden.

Ich glaube nicht, dass die dynamische Programmierung hier effektiv ausgeführt werden kann, weil es kein beobachtbares Prinzip der Optimalität gibt. Wenn wir die minimalen Kosten zwischen zwei Inseln finden, bedeutet das nicht notwendigerweise, dass wir die minimalen Kosten zwischen diesen beiden und der dritten Insel oder einer anderen Teilmenge von Inseln finden, die (nach meiner Definition die MST über Prim finden) in Verbindung gebracht.

Wenn Sie möchten, dass Code (pseudo oder anders) Ihren Grid in eine Menge von {V} und {E} konvertiert, senden Sie mir bitte eine private Nachricht und ich werde mich damit beschäftigen, eine Implementierung zu verbinden.


-1
2018-06-16 17:24



Ich stimme zu, dass dies ein Problem des Geschäftsreisenden ist, aber es kann mit n = 7 brutal erzwungen werden. Berechnen Sie den minimalen Kostenpfad zwischen den einzelnen Inseln und Sie haben nur n (n-1) / 2 Lösungen = 21 Berechnungen


-6
2018-06-08 14:42