Irgendwie habe ich es mir ausgedacht.
Ich denke, es ist bekannt, dass Sie Mathematik ohne menschliche Kraft lösen können, indem Sie sie mit linearer Programmierung oder einem Hopfield-Netzwerk lösen. Ich dachte jedoch, dass es möglich sein würde, es zu lösen, indem man die Anzahl der Versuche erhöht, ohne die Regeln von Sugoku zu kennen, also habe ich es tatsächlich versucht.
Es ist eine Art Puzzlespiel. Siehe Wikipedia für Details. Deutschland
optuna Eine von Preferred Networks entwickelte Python-Bibliothek zur Optimierung von Hyperparametern. Der Hyperparametersuchalgorithmus verwendet TPE, das mit HyperOpt identisch ist.
Kurz gesagt, wenn detaillierte Erklärungen weggelassen werden, wird die Zielfunktion auf nette Weise optimiert, selbst wenn das Ziel der Optimierung eine Black Box ist.
Wie oben erwähnt, werden wir optuna verwenden. Daher wird die Zielfunktion so eingestellt, dass der Wert kleiner wird, wenn sich die Antwort der richtigen Antwort nähert.
Die Zielfunktion entscheidet, die Anzahl der Regelverstöße zu zählen. Weniger Verstöße bedeuten hier, der richtigen Antwort näher zu kommen. Ich kenne die richtige Antwort nicht explizit, aber wenn ich den Wert der Zielfunktion minimiere, erreiche ich schließlich 0 Verstöße und die richtige Antwort.
def evaluate(answer):
#Es verletzt die deutsche Schleife und gibt die Nummer zurück. Wenn die Antwort richtig ist, ist die Bewertung 0
#Die Antwort ist ein zweidimensionales 9x9-Array mit den Nummern 1-9 in jedem Element
tmp = np.reshape(answer, [3, 3, 3, 3])
loss = np.sum((
#Anzahl der Verstöße in jeder Spalte
np.sum([np.count_nonzero(np.logical_not(np.any(answer == i, axis=0))) for i in range(9)]),
#Anzahl der Verstöße in jeder Zeile
np.sum([np.count_nonzero(np.logical_not(np.any(answer == i, axis=1))) for i in range(9)]),
#Anzahl der Verstöße pro 3x3-Bereich
np.sum([np.count_nonzero(np.logical_not(np.any(tmp == i, axis=(1, 3)))) for i in range(9)]),
))
return loss
Die Anzahl der Verstöße zählt nicht die Anzahl der doppelten Nummern, sondern die Anzahl der nicht angezeigten Nummern.
Wenn die Regeln erfüllt sind, wird 1-9 für jede Bedingung einmal angezeigt. Wenn aufgrund eines Regelverstoßes ein Duplikat vorliegt, wurde die Anzahl der Auftritte einer der anderen Nummern auf 0 verringert. Zählen Sie dies.
Im Falle einer Duplizierung gibt es verschiedene Muster von 2 bis 9 Mal, aber wenn die Anzahl der Auftritte abnimmt, gibt es nur 0 Mal, daher denke ich, dass es einfacher ist, dies zu zählen.
Das Problem, das ich lösen wollte, war im Quellcode fest codiert. Es ist im Grunde das gleiche wie der Code in der Optuna-Dokumentation.
from itertools import product
import numpy as np
import optuna
import click
"""
Das Problem ist https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%Aus dem AC-Beispielbild
-----------------
|5|3| | |7| | | | |
|-+-+-+-+-+-+-+-+-|
|6| | |1|9|5| | | |
|-+-+-+-+-+-+-+-+-|
| |9|8| | | | |6| |
|-+-+-+-+-+-+-+-+-|
|8| | | |6| | | |3|
|-+-+-+-+-+-+-+-+-|
|4| | |8| |3| | |1|
|-+-+-+-+-+-+-+-+-|
|7| | | |2| | | |6|
|-+-+-+-+-+-+-+-+-|
| |6| | | | |2|8| |
|-+-+-+-+-+-+-+-+-|
| | | |4|1|9| | |5|
|-+-+-+-+-+-+-+-+-|
| | | | |8| | |7|9|
-----------------
"""
#Das Teil mit dem Wert im Voraus
preset = {'p00': 5, 'p01': 3, 'p04': 7,
'p10': 6, 'p13': 1, 'p14': 9, 'p15': 5,
'p21': 9, 'p22': 8, 'p27': 6,
'p30': 8, 'p34': 6, 'p38': 3,
'p40': 4, 'p43': 8, 'p45': 3, 'p48': 1,
'p50': 7, 'p54': 2, 'p58': 6,
'p61': 6, 'p66': 2, 'p67': 8,
'p73': 4, 'p74': 1, 'p75': 9, 'p78': 5,
'p84': 8, 'p87': 7, 'p88': 9}
def evaluate(answer):
#Wie oben
def objective(trial):
candidate = (1, 2, 3, 4, 5, 6, 7, 8, 9)
answer = np.empty([9, 9], dtype=np.uint8)
for i, j in product(range(9), repeat=2):
key = 'p{}{}'.format(i, j)
if key in preset:
answer[i, j] = preset[key]
else:
answer[i, j] = trial.suggest_categorical(key, candidate)
return evaluate(answer)
def run(n_trials):
study_name = 'sudoku'
study = optuna.create_study(study_name=study_name, storage='sqlite:///sudoku.db', load_if_exists=True)
study.optimize(objective, n_trials=n_trials)
show_result(study.best_params, study.best_value)
df = study.trials_dataframe()
df.to_csv('tpe_result.csv')
def show_result(best_params, best_value):
for i in range(9):
for j in range(9):
key = 'p{}{}'.format(i, j)
if key in preset:
print('*{:1d}'.format(preset[key]), end='')
else:
print('{:2d}'.format(best_params[key]), end='')
print('')
print('loss: {}'.format(best_value))
@click.command()
@click.option('--n-trials', type=int, default=1000)
def cmd(n_trials):
run(n_trials)
def main():
cmd()
if __name__ == '__main__':
main()
Es tut mir leid für diejenigen, die so weit in Erwartung lesen.
Ich konnte es überhaupt nicht lösen.
Die für jede Bewertung erforderliche Zeit ist viel länger als erwartet, und die Anzahl der Versuche reicht nicht aus. Die Anzahl der Versuche beträgt 0 für ungefähr 7 Sekunden und 200 für ungefähr 25 Sekunden.
Selbst wenn wir so weitermachen, werden Hunderttausende bis Millionen von Versuchen erforderlich sein, um die richtige Antwort zu erhalten. Ich denke, dass dies in der Realität unmöglich zu erreichen ist.
Schließlich wird vorerst die Ausgabe am Ende von 200 Mal angezeigt.
*5*3 5 5*7 2 6 1 2
*6 7 8*1*9*5 7 3 5
4*9*8 6 3 7 8*6 4
*8 1 4 7*6 9 7 6*3
*4 3 9*8 5*3 2 7*1
*7 8 9 3*2 1 5 4*6
3*6 1 6 7 9*2*8 7
5 7 3*4*1*9 8 1*5
4 7 6 2*8 4 3*7*9
loss: 73.0
Die Zahlen mit * auf der linken Seite sind die Zahlen von Anfang an als Hinweise für die Antwort.
Dougoku kann nicht mit optuna (TPE-Algorithmus) gelöst werden. Ich hatte vor, die Anzahl der Versuche zu erhöhen, aber die Berechnungszeit war viel länger als erwartet und ich konnte nicht pushen.
Die Abtastung von optuna (TPE-Algorithmus) nimmt mit zunehmender Anzahl von Versuchen mehr Zeit in Anspruch.
Die Ursache für diesen Fehler war die lange Berechnungszeit des TPE-Algorithmus. Ich denke, dass dieses Problem mit einem anderen Algorithmus gelöst werden kann. Da der TPE-Algorithmus die bedingte Verteilung überhaupt nicht berücksichtigt, ist er ein eher ungeeigneter Algorithmus zum Lösen von Mathematik.
Das nächste Mal möchte ich einen Algorithmus ausprobieren, der aus einer bedingten Verteilung abtastet. Daher ist es notwendig, die Regeln von Sugoku vor dem Lösen zu verstehen. Es wäre ein rücksichtsloser Versuch gewesen, die richtige Antwort zu finden, ohne die Regeln Deutschlands wie diesmal zu kennen.
Der Zeitplan ist völlig unentschlossen. Ich denke, dass der Algorithmus ein simuliertes Glühsystem sein wird, aber die Buchungszeit ist unentschlossen, da ich ihn von nun an untersuchen werde.
Recommended Posts