[PYTHON] Essayez de résoudre le problème N Queen avec SA de PyQUBO

J'ai essayé le problème N Queen pour approfondir ma compréhension de PyQUBO en utilisant les heures de fin d'année et de nouvel an.

Je pense que PyQUBO est un outil de création QUBO très pratique pour utiliser une machine de recuit. "Résolvez le problème du réglage de seulement m à 1 sur n avec une machine de recuit utilisant PyQUBO" https://qiita.com/morimorijap/items/196e7fc86ecff927bf40 Je l'utilise également dans de tels cas, mais je vais essayer de résoudre à nouveau le problème de N Queen en utilisant PyQUBO.

Quel est le problème de N Queen? Les 8 reines de Wikipédia ont des carrés de 8 x 8 et 8 reines https://ja.wikipedia.org/wiki/Eight Queen D'autre part, la masse dit des problèmes NxN.

Puisque le mouvement de la reine se déroule dans huit directions en diagonale vers le haut, le bas, la gauche et la droite tant qu'il n'y a pas d'obstruction, il devient un problème de disposer la reine de sorte qu'il n'y ait pas de reine dans la colonne, la rangée ou en diagonale. Sous la forme d'une fonction de coût pour résoudre ce problème sur une machine de recuit,

Hamiltonien dans le problème N-Queen, colonne colonne, ligne rangée, 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)

Ce sera.

L'expression de la fonction de coût diagonal est différente, mais il s'agit d'un article de T-Wave de l'Université de Tohoku "Résolution du problème N-Queen avec une machine D-Wave" https://qard.is.tohoku.ac.jp/T- Vague /? P = 884 Sera également utile.

Dans le cas du 4x4

Considérant l'expression d'une masse comme, PyQUBO exprime un Array comme Binary (q [0]) au format QUBO de 0,1.

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

Tout d'abord, importez ce dont vous avez besoin, comme PyQUBO. Supposons que vous vouliez créer un carré 4x4.

# N-Nombre de carrés de la reine
N = 4

#Créez des variables 0 et 1 avec pyQUBO pour les carrés NxN
q = Array.create('q', (N*N), 'BINARY')

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

Puis

[[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])]]

De cette façon, vous pouvez créer un binaire PyQUBO sous la forme d'un tableau 4x4. La partie de ligne est la suivante dans la formule, donc

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

En exprimant cela dans PyQUBO, vous pouvez découper chaque ligne, les ajouter telles quelles, les mettre au carré et enfin les additionner.

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

En outre, les colonnes peuvent être exprimées comme suit.

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

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

Ce sera.

Et l'expression diagonale du problème,

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

Sera représenté par PyQUBO, mais il peut être divisé en deux parties, "" et "/", en utilisant la conversion de Numpy. (Si vous connaissez un meilleur moyen, faites-le moi savoir)

#Diagonale
#\Qui
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

Quand

#Diagonale
# /Remplacer pour ceux qui,\ faire.
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

Ce sera.

En ajoutant tout cela, nous pouvons exprimer l'hamiltonien de la fonction énergétique. Utilisez également l'espace réservé de PyQUBO pour ajuster les paramètres et ajouter alpha, bêta et gamma.

#énergie(Hamiltonien)Construire

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

#Paramètres
feed_dict = {'alpha': 1.0, 'beta': 1.0, 'gamma': 1.0}

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

Ensuite, convertissez en QUBO.

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

pprint(qubo)

Rien qu'en lui-même, cela fera QUBO.

{('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,

・・・ Parce qu'il est long, il est omis sur le chemin ...

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

est. Cela peut être calculé tel quel avec SA de PyQUBO.

#Calculé avec SA de PyQUBO
solution = solve_qubo(qubo)

#Décodage du résultat du calcul avec SA de pyQUBO
decoded_solution, broken, energy = model.decode_solution(solution, vartype="BINARY", 
feed_dict=feed_dict)

pprint(solution)

Le résultat est,

{'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}

Cela devient ~~, et les conditions sont réunies pour le moment, mais comme Queen peut être incluse dans 13, j'estime qu'il est nécessaire d'ajuster les paramètres. ~~ Post-scriptum: Il semble que la solution optimale n'a pas pu être obtenue car le coin diagonal manquait. Cette fois, la solution est sortie correctement.

Supplémentaire: Expérimentez avec l'échiquier attaché au calendrier de l'avent Harry Potter de Lego 2019 (rires)

Pour PyQUBO, reportez-vous au document officiel. https://pyqubo.readthedocs.io/

c'est tout.

Post-scriptum: 2020/1/3 9:20pm Je l'ai édité parce que la condition diagonale était fausse.