[PYTHON] Versuchen Sie, das N Queen-Problem mit SA von PyQUBO zu lösen

Ich habe versucht, mit dem N Queen-Problem mein Verständnis von PyQUBO anhand der Jahresend- und Neujahrsstunden zu vertiefen.

Ich denke, PyQUBO ist ein sehr praktisches QUBO-Erstellungswerkzeug für die Verwendung einer Glühmaschine. "Lösen des Problems, mit PyQUBO mit einer Glühmaschine nur m auf 1 von n zu setzen" https://qiita.com/morimorijap/items/196e7fc86ecff927bf40 Ich benutze es auch in solchen Fällen, aber ich werde versuchen, das N Queen-Problem erneut mit PyQUBO zu lösen.

Was ist das N Queen Problem? Die 8 Königinnen von Wikipedia haben 8x8 Quadrate und 8 Königinnen https://ja.wikipedia.org/wiki/Eight Queen Auf der anderen Seite sagt die Masse NxN-Probleme.

Da die Bewegung der Königin in acht Richtungen diagonal nach oben, unten, links und rechts verläuft, solange kein Hindernis vorhanden ist, wird es zu einem Problem, die Königin so anzuordnen, dass sich keine Königin in der Spalte, Reihe oder diagonal befindet. In Form einer Kostenfunktion, um dies auf einer Glühmaschine zu lösen,

Hamiltonian im N-Queen-Problem, Spaltenspalte, Zeilenzeile, diagonale Diagonale

H = \sum_{col}\left(\sum_{i \in col} x_i - 1\right)^2 + \sum_{row}\left(\sum_{i \in row} x_i - 1\right)^2 + \sum_{diag} \left((\sum_{i \in diag} x_i ) (\sum_{i \in diag} x_i - 1 )\right)

Es wird sein.

Der Ausdruck der diagonalen Kostenfunktion ist unterschiedlich, aber es ist ein Artikel von T-Wave der Tohoku University "Lösen des N-Queen-Problems mit einer D-Wave-Maschine" https://qard.is.tohoku.ac.jp/T- Welle /? P = 884 Wird auch hilfreich sein.

Im Falle von 4x4

Unter Berücksichtigung des Ausdrucks einer Masse wie drückt PyQUBO ein Array wie Binär (q [0]) im QUBO-Format von 0,1 aus.

from pyqubo import Array, Placeholder, solve_qubo, Sum
from pprint import pprint
import numpy as np

Importieren Sie zunächst das, was Sie benötigen, z. B. PyQUBO. Angenommen, Sie möchten ein 4x4-Quadrat erstellen.

# N-Anzahl der Quadrate der Königin
N = 4

#Erstellen Sie mit pyQUBO 0- und 1-Variablen für NxN-Quadrate
q = Array.create('q', (N*N), 'BINARY')

q_shape = np.reshape(q,(N,N))
print(q_shape)

Dann

[[Binary(q[0]) Binary(q[1]) Binary(q[2]) Binary(q[3])] [Binary(q[4]) Binary(q[5]) Binary(q[6]) Binary(q[7])] [Binary(q[8]) Binary(q[9]) Binary(q[10]) Binary(q[11])] [Binary(q[12]) Binary(q[13]) Binary(q[14]) Binary(q[15])]]

Auf diese Weise können Sie eine PyQUBO-Binärdatei in Form eines 4x4-Arrays erstellen. Der Linienteil ist also wie folgt in der Formel

\sum_{row}\left(\sum_{i \in row} x_i - 1\right)^2

Wenn Sie dies in PyQUBO ausdrücken, können Sie jede Zeile in Scheiben schneiden, sie so hinzufügen, wie sie sind, quadrieren und schließlich addieren.

#Linie
row_const = 0.0
for row in range(N):
    row_const += (sum(i for i in q_shape[row, :]) -1)**2

Die Spalten können auch wie folgt ausgedrückt werden.

\sum_{col}\left(\sum_{i \in col} x_i - 1\right)^2

#Säule
col_const = 0.0
for col in range(N):
    col_const += (sum(i for i in q_shape[:, col]) -1)**2

Es wird sein.

Und der diagonale Ausdruck des Problems,

\sum_{diag} \left((\sum_{i \in diag} x_i ) (\sum_{i \in diag} x_i - 1 )\right)

Wird durch PyQUBO dargestellt, kann aber mithilfe der Konvertierung von Numpy in zwei Teile unterteilt werden: "" und "/". (Wenn Sie einen besseren Weg kennen, lassen Sie es mich bitte wissen)

#Diagonale
#\Wer
diag_const = 0.0
xi = 0.0
xi_1 = 0.0
for k in range(-N+1,N):
    xi += (sum(i for i in np.diag(q_shape,k=k)))
    xi_1 += (sum(i for i in np.diag(q_shape,k=k))) -1 
    diag_const += xi * xi_1

Wann

#Diagonale
# /Ersetzen Sie für diejenigen, die,\ machen.
diag_const_f = 0.0
xi = 0.0
xi_1 = 0.0
for k in range(-N+1,N):
    xi += (sum(i for i in np.diag(np.fliplr(q_shape),k=k)))
    xi_1 += (sum(i for i in np.diag(np.fliplr(q_shape),k=k))) -1 
    diag_const_f += xi * xi_1

Es wird sein.

Indem wir all dies hinzufügen, können wir den Hamilton-Operator der Energiefunktion ausdrücken. Verwenden Sie außerdem den Platzhalter von PyQUBO, um die Parameter anzupassen und Alpha, Beta und Gamma hinzuzufügen.

#Energie(Hamiltonianer)Bauen

alpha = Placeholder("alpha")
beta = Placeholder("beta")
gamma = Placeholder("gamma")

#Parameter
feed_dict = {'alpha': 1.0, 'beta': 1.0, 'gamma': 1.0}

H = alpha * col_const + beta * row_const  + gamma *(diag_const + diag_const_f)

Als nächstes konvertieren Sie zu QUBO.

#QUBO kompilieren
model = H.compile()
qubo, offset = model.to_qubo(feed_dict=feed_dict)

pprint(qubo)

Allein wird es QUBO machen.

{('q[0]', 'q[0]'): -11.0, ('q[0]', 'q[10]'): 6.0, ('q[0]', 'q[11]'): 4.0, ('q[0]', 'q[12]'): 2.0, ('q[0]', 'q[13]'): 6.0, ('q[0]', 'q[14]'): 6.0, ('q[0]', 'q[15]'): 6.0, ('q[0]', 'q[1]'): 6.0, ('q[0]', 'q[2]'): 4.0,

・・・ Weil es lang ist, wird es unterwegs weggelassen ...

('q[8]', 'q[8]'): -19.0, ('q[8]', 'q[9]'): 14.0, ('q[9]', 'q[9]'): -21.0}

ist. Dies kann wie bei SA von PyQUBO berechnet werden.

#Berechnet mit SA von PyQUBO
solution = solve_qubo(qubo)

#Dekodierung des Berechnungsergebnisses mit SA von pyQUBO
decoded_solution, broken, energy = model.decode_solution(solution, vartype="BINARY", 
feed_dict=feed_dict)

pprint(solution)

Ergebnis ist,

{'q[0]': 0, 'q[10]': 0, 'q[11]': 0, 'q[12]': 0, 'q[13]': 0, 'q[14]': 1, 'q[15]': 0, 'q[1]': 1, 'q[2]': 0, 'q[3]': 0, 'q[4]': 0, 'q[5]': 0, 'q[6]': 0, 'q[7]': 1, 'q[8]': 1, 'q[9]': 0}

Es wird ~~ und die Bedingungen sind vorerst erfüllt, aber da Queen in 13 enthalten sein kann, halte ich es für notwendig, die Parameter anzupassen. ~~ Nachtrag: Es scheint, dass die optimale Lösung nicht erhalten werden konnte, weil die diagonale Ecke fehlte. Diesmal kam die Lösung richtig heraus.

Extra: Experimentieren Sie mit dem Schachbrett, das an Legos Harry Potter-Adventskalender 2019 angehängt ist (lacht)

Informationen zu PyQUBO finden Sie im offiziellen Dokument. https://pyqubo.readthedocs.io/

das ist alles.

Nachtrag: 2020/1/3 9:20pm Ich habe es bearbeitet, weil die diagonale Bedingung falsch war.