[PYTHON] Lösen des N Queen-Problems mit kontinuierlicher / kombinierter Optimierung

Was ist das

Hier sind einige Tipps zum Lösen mit Kombinationsoptimierung basierend auf dem N Queen-Problem.

Originalartikel: N Queen-Problem mit Kombinationsoptimierung lösen

Fazit

Durch Ändern der Reihenfolge der Einschränkungen kann die Berechnungszeit geändert werden. Lassen Sie uns mit 4 Mustern überprüfen.

Löse das N Queen Problem

Überprüfen Sie zunächst, ob Sie es tatsächlich mit 8x8 lösen können.

from ortoolpy import pd, addbinvars, model_min, lpSum, addvals
n = 8
df = pd.DataFrame([(i, j) for i in range(n) for j in range(n)],
                  columns=['X', 'Y'])
addbinvars(df);
m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%time m.solve()
addvals(df)
cc = df.Val.astype(int).map('.O'.__getitem__).values.reshape(n, n)
print('\n'.join(''.join(c) for c in cc))

Ausgabe

Wall time: 27 ms
..O.....
O.......
......O.
....O...
.......O
.O......
...O....
.....O..

Überprüfen Sie ab dem nächsten die Ausführungszeit mit vier Formulierungen mit einer Größe von 100 x 100.

Muster 1 (4,0 Sekunden)

m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()

3.97 s ± 702 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)

Muster 2 (4,7 Sekunden)

m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()

4.7 s ± 423 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)

Muster 3 (2,2 Sekunden)

m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
for i in range(n):
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()

2.24 s ± 36.5 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)

Muster 4 (6,4 Sekunden)

m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
for i in range(n):
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()

6.44 s ± 129 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)

Was soll ich machen

Die vier Muster haben die gleiche Formulierung, nur die Reihenfolge der Einschränkungen ist unterschiedlich. Die Berechnungszeit hat sich jedoch fast dreimal geändert. Darüber hinaus ist die Tendenz in Abhängigkeit von n unterschiedlich.

In einem solchen Fall ist es möglicherweise besser, mehrere Muster vorzubereiten und gleichzeitig wie dieses auszuführen, und alle zu stoppen, wenn auch nur eine Antwort gefunden wird.

Ergänzung

Die Berechnung wurde auf dem ThinkPad X280 durchgeführt. Die Bibliotheksinstallation ist "pip install or toolpy".

Das 100 x 100 N Queen-Problem hat 10.000 0-1-Variablen. Die Kombination ist $ 10 ^ {3010} $. Es ist eine enorme Anzahl von Kombinationen, aber es ist erstaunlich, dass Sie es in etwas mehr als 2 Sekunden mit freier Software (PuLP) lösen können.