Mahjong-solitaire solver-Algorithmus, der braucht speed-up

Question

Ich bin die Entwicklung eines Mah-Jongg-solitaire solver und so weit bin ich schon ziemlich gut.Jedoch, es ist nicht so schnell, wie ich möchte, dass es so ist, ich bin zu Fragen, für zusätzliche Optimierung die Techniken, die du Jungs, die möglicherweise kennen.

Alle Fliesen sind bekannt aus den layouts, aber die Lösung nicht.Im moment habe ich ein paar Regeln, die garantieren die sichere Entfernung der bestimmte Paare von gleichen Fliesen (nicht ein Hindernis für die mögliche Lösung).

Für Klarheit, eine Fliese ist frei, wenn es abgeholt werden kann jederzeit und Fliesen Locker ist, wenn es nicht gebunden, andere Fliesen überhaupt.

• Wenn es vier freie Kacheln zur Verfügung, entfernen Sie Sie sofort.
• Wenn es drei Kacheln, die abgeholt werden können, und mindestens einer von Ihnen ist ein loser Ziegel, entfernen Sie den nicht-lose diejenigen.
• Wenn es drei Kacheln, die abgeholt werden können-und nur eine freie Kachel (zwei verliert), entfernen Sie die freien und zufälligen Locker.
• Wenn es drei losen Fliesen verfügbar sind, entfernen zwei von Ihnen (egal welche).
• Da es vier mal die exakt gleiche Fliese, wenn zwei von Ihnen übrig sind, entfernen Sie Sie, da Sie sind die einzigen, Links.

Mein Algorithmus durchsucht Lösung in mehreren threads rekursiv.Eine Verzweigung abgeschlossen ist (bis zu einer position, wo es keine Züge mehr) und es hat nicht zu einer Lösung führt, stellt es die position in einen Vektor mit schlechten.Nun, jedes mal, wenn eine neue Niederlassung wird gestartet, es werde iteriert über die schlechte Positionen zu prüfen, wenn die entsprechende position wurde bereits überprüft.
Dieser Prozess wird fortgesetzt, bis die Lösung gefunden ist oder alle möglichen Positionen überprüft werden.

Dies funktioniert gut auf ein layout enthält, sagen wir, 36 oder 72 Fliesen.Aber wenn es mehr ist, dieser Algorithmus wird ziemlich nutzlos aufgrund der riesigen Menge von Positionen zu suchen.

Also, ich Frage dich noch einmal, wenn alle von Ihnen haben gute Ideen, wie zu implementieren Regeln für die sichere Fliesen-entfernen oder jedem anderen besonderen speed-up in Bezug auf den Algorithmus.

Beste Grüße, nhaa123

Answer 1

Ich don T vollständig verstehen, wie Ihr solver arbeitet.Wenn Sie die Wahl haben, bewegt sich, wie Sie sich entscheiden, die Möglichkeit zu erforschen zuerst?

Wenn Sie wählen Sie eine beliebige ein, es ist nicht gut genug - es ist nur rohe suchen, grundsätzlich.Möglicherweise müssen Sie erkunden die "bessere Zweige" erste.Um zu bestimmen, welche Zweige sind die "besser" ist, müssen Sie eine heuristische Funktion, das bzw. der ein-position.Dann können Sie mithilfe einer der beliebtesten heuristische Suchalgorithmen.Überprüfen Sie diese:

• A* - Suche
• beam search

(Google ist dein Freund)

Answer 2

Vor einigen Jahren schrieb ich ein Programm, das löst Solitaire Mahjongg boards, die durch spähen.Ich verwendet es zu untersuchen, eine million Schildkröten (dauerte einen Tag oder etwas über die Hälfte einen computer:es hatte zwei Kerne) und es zeigte sich, dass etwa 2.96 Prozent von Ihnen nicht gelöst werden können.

http://www.math.ru.nl/~debondt/mjsolver.html

Ok, das war nicht das, was Sie gefragt, aber Sie könnte haben einen Blick auf den code zu finden, einige beschneiden Heuristiken, dass es nicht dein Geist überqueren so weit.Das Programm macht nicht mehr als ein paar Megabyte Speicher.

Answer 3

Anstatt einen Vektor mit den "schlechten" Positionen, verwenden Sie ein set, das hat eine Konstante lookup-Zeit statt linear.