[PYTHON] Optimale Lösung durch Kombination von "Faktorräumen"
Löse den Faktorraum
Der ** Faktorraum ** ist ein Puzzle, das einer Zahl ähnelt. Dieses Rätsel kann auch mit Kombinationsoptimierung gelöst werden. Referenz
Problembeispiel
Mit Zustimmung von Nikori habe ich mir ein Beispiel ausgeliehen. Die linke ist die Frage und die rechte ist die Antwort. Das Problem ist in Räume unterteilt, die von dicken Linien umgeben sind, mit Hinweisnummern oben links. Der Hinweis ist die Multiplikation der Zahlen im Raum. Bei einer Größe von 5 x 5 können Sie 1-5 verwenden. Wie bei Sugoku können nicht dieselben Zahlen in einer vertikalen Zeile oder einer horizontalen Spalte verwendet werden.
Formulierung
Das Wichtigste im Kombinationsoptimierungsmodell ist, es so weit wie möglich als linearen Ausdruck auszudrücken. Die einfache Modellierung der Multiplikation von Variablen führt zu einer nichtlinearen Optimierung und ist schwer zu lösen. Dieses Mal verwenden wir logarithmisch, um einen linearen Ausdruck zu erstellen. Mit anderen Worten, Sie können sich das wie folgt vorstellen.
Auf diese Weise kann es als linearer Ausdruck ausgedrückt werden. Wenn es jedoch so bleibt, wie es ist, tritt ein Berechnungsfehler auf, weil eine unangemessene Zahl verwendet wird. Geben Sie daher den Einschränkungsausdruck so an, dass er in einen kleinen Bereich fällt und nicht in eine gleiche Zahl.
Die Formulierung ist wie folgt.
| $ \ mbox {Variablen} $ | $ x_ {ijk} \ in \ {0, 1 \} ~ \ für alle i, j, k $ | Ist die Masse i, j die Zahl k + 1? (1) |
| $ y_ {ij} \ in \ {1 \ cdots n \} ~ \ für alle i, j $ | Zahlen i, j (2) | |
| $ \ mbox {vorbehaltlich} $ | $ \ sum_k {x_ {ijk}} = 1 ~ \ forall i, j $ | Eine Zahl (3) |
| $ \ sum_k {x_ {ikj}} = 1 ~ \ forall i, j $ | Keine vertikale gleiche Zahl (4) | |
| $ \ sum_k {x_ {kij}} = 1 ~ \ forall i, j $ | Daneben steht nicht dieselbe Nummer (5) | |
| $ y_ {ij}, dargestellt durch x_ {ijk} $ (6) | ||
| Das Produkt der Quadrate entspricht dem Hinweis (7) | ||
Löse mit Python
[Zellstoff](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%E3%81%AE%E3%82 Verwenden Sie% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB) und Pandas.
Das Problem ist, dass es in einer Zeichenfolge ist.
python
ch = """
ABBCD
AEEFD
GGHFD
IJHKK
ILHMM
""".strip().split('\n')
rooms = [6, 15, 1, 12, 20, 8, 10, 6, 4, 4, 15, 1, 10]
Sich fertig machen
python
import pandas as pd
from collections import defaultdict
from pulp import *
from math import log
def addvar(lowBound=0, count=[0], *args, **kwargs):
count[0] += 1
return LpVariable('v%d'%count[0], lowBound=lowBound, *args, **kwargs)
nn, nb = len(ch), len(rooms) #Anzahl der Nummern, Anzahl der Zimmer
rn, rb = range(nn), range(nb)
lognn = [log(k + 1) for k in rn] # 1..nn log
logrm = [log(h) for h in rooms] #Tippprotokoll
Lassen Sie uns eine Tabelle mit Variablen erstellen.
python
a = pd.DataFrame([(i, j, [addvar(cat=LpBinary) for k in rn], addvar())
for i in rn for j in rn],
columns=['Vertikal', 'Seite', 'Vars', 'Var']) # (1), (2)
print(a[:3])
--Vars von vertikalem $ i $ horizontal $ j $ entsprechen [$ x_ {ijk} \ forall k $], und Var entspricht $ y_ {ij} $.
| Vertikal | Horizontal | Vars | Var | |
|---|---|---|---|---|
| 0 | 0 | 0 | [v1, v2, v3, v4, v5] | v6 |
| 1 | 0 | 1 | [v7, v8, v9, v10, v11] | v12 |
| 2 | 0 | 2 | [v13, v14, v15, v16, v17] | v18 |
Formulieren und lösen.
python
m = LpProblem() #Mathematisches Modell
dic = defaultdict(list) #Variablen für jeden Raum(x)Liste von
for _, r in a.iterrows():
m += lpSum(r.Vars) == 1 # (3)
m += lpDot(rn, r.Vars) + 1 == r.Var # (6)
dic[ch[r.Vertikal][r.Seite]].append(r.Vars)
for i in rn:
for k in rn:
m += lpSum(v[k] for v in a.query('Vertikal==%d'%i).Vars) == 1 # (4)
m += lpSum(v[k] for v in a.query('Seite==%d'%i).Vars) == 1 # (5)
for h in rb:
c = lpSum(lpDot(lognn, v) for v in dic[chr(h + 65)]) #Protokoll des Produkts der Zahlen
m += c >= logrm[h] - 0.001 # (7)
m += c <= logrm[h] + 0.001 # (7)
m.solve() #Lösung
Zeigen Sie das Ergebnis an.
python
a['Val'] = a.Var.apply(value)
print(a.Val.reshape(5, -1))
>>>
[[ 2. 3. 5. 1. 4.]
[ 3. 5. 4. 2. 1.]
[ 5. 2. 1. 4. 3.]
[ 1. 4. 2. 3. 5.]
[ 4. 1. 3. 5. 2.]]
das ist alles