Subset Summe mit Nachbarschaftssuche - Java

Question

Ich versuche Subset Sum Problem mit dem Nachbarschaftsalgorithmus zu implementieren. Hier ist der Pseudo-Code: 1. Generate a random solution for the problem and call it S 2. Compute the neighborhood of S and choose S' as the best solution in the neighborhood 3. If S' is better than S then go to step 4, else go to step 6 4. S = S' 5. Go to step 2 6. Return S as the best solution encountered Angesichts einer Menge X von 10 Elementen (+ ve und -ve), muss ich eine Teilmenge von X so finden, dass die Summe so nahe wie möglich 0 ist.

Nach dem Pseudo-Code, habe ich eine zufällige Lösung S erzeugt, aber ich habe einige Schwierigkeiten beim Aufbau der Nachbarschaft anzutreffen S.

Wie kann ich die Nachbarschaft von S berechnen? Was ist die Nachbarschaft von S?

z.

X = [x0, x1, x2, x3, x4, x5, x6, x7, x8, x9]

S = [x1, X7, x2, x3]

Was die Nachbarschaft ist von S?

Answer 1

Es gibt keine eindeutige Definition von Nachbarschaft, es hängt von dem Problem ab. In Ihrem Fall könnte eine gute Definition all the tuples that have (at most) n different elements from the current solution sein, wo n 1, 2 , size - 1 sein könnte (wenn Sie n = size nehmen, betrachten Sie den ganzen Lösungsraum und Sprechen von Nachbarschaft hat keinen Sinn mehr).

In Ihrem Beispiel alle Lösungen nehmen, die von dem aktuellen von einem Schritt unterscheiden endet un in dem folgenden Satz von Lösungen:

D = [[x0, x7, x2, x3], [x4, x7 , x2, x3], [x5, x7, x2, x3], [x6, x7, x2, x3], [x8, x7, x2, x3], [x9, x7, x2, x3], [x1, x0 , x2, x3], [x1, x4, x2, x3], ...]

Answer 2

Lasst uns das Beispiel verwenden:

S eine Lösung ist, wollen wir sehen, wie können wir ein anderes daraus zu generieren:

• Wir können einen anderen x_i, um es zu schaffen zum Beispiel [x1, x2, x3, x7, x8]
• hinzuzufügen, oder wir können eine x_i daraus zu schaffen zum Beispiel [x2, x3, x7]

entfernen Jede solche Lösung, die von S unter Verwendung einer der obigen Operationen erhalten wird, ist ein Nachbar von S. Alle diese Lösungen bilden die Nachbarschaft.

Beachten Sie, dass [x1, x3, x2] und [x1, x2, x3] die gleiche Lösung sind, da die Reihenfolge der Elemente keine Rolle spielt.

---

Formell ist jede Lösung ein binärer Vektor v der Länge 10, bestehend aus 0 und 1 ist, wie v [i] == 1, wenn die entsprechende Lösung x_i enthält.

Ein Vektor zur S aus Beispiel entsprechend würde wie folgt aussehen: S = [0, 1, 1, 1, 0, 0, 0, 1, 0, 0]

Jedes solches Vektor eine Vertex in der Grafik der Lösungen. Die Kante zwischen zwei solchen Eckpunkten existiert, wenn man in eine andere transformiert werden kann, indem man eine Art einfache Operation wie die oben beschriebenen verwendet.

Ich hoffe, das hilft.