Zur Frage von Wirth und Ketten

Algorithmen + Datenstrukturen = Programme - Virt N.

"Wir hatten eine wunderbare Gelegenheit, eine kleine, aber äußerst lehrreiche taktische Übung durchzuführen."

Trotz der ersten Inschrift zu diesem Beitrag erlaube ich mir, dem Autor nicht zuzustimmen und zu zeigen, dass in einigen Fällen die richtige Wahl der Datenstruktur wichtiger sein kann als die richtige Wahl der Algorithmen. Um eine solch aufrührerische These zu veranschaulichen, betrachten wir eine einfache, aber vielversprechende Aufgabe, um das Spiel "Chain" zu studieren.

Zunächst zu den Spielregeln - zwei Spieler spielen, die Startposition besteht aus N Objekten in der Nähe. Der nächste Schritt besteht darin, ein oder zwei Objekte in der Nähe zu entfernen (Sie können versuchen, eine formale Definition des "nahe gelegenen Standorts" zu geben, dies ist jedoch auf einer intuitiven Ebene verständlich). Der Spieler, der das letzte Objekt entfernt, gewinnt - das direkte Spiel oder derjenige, der das letzte Objekt aufheben muss (Sie können den Zug nicht überspringen) - das umgekehrte Spiel gewinnt. Da in dieser Version der Regeln ein direktes Spiel einfach uninteressant ist (dazu später mehr), wird eine zusätzliche Einschränkung eingeführt - nur ein Objekt kann im ersten Zug gelöscht werden.

Zunächst stellen wir fest, dass das Spiel endlich ist, da mit jedem Zug die Anzahl der Objekte stark abnimmt und das Spiel endet, wenn die Anzahl der durch Null berechneten Objekte erreicht ist. Daher haben wir das Recht, beim Studium dieses Spiels mit dem Erfolg zu rechnen. Darüber hinaus ist es offensichtlich, dass das Spiel nicht länger als N Züge dauern kann. Erinnern wir uns an diese Tatsache.

Die Untersuchung des Spiels besteht darin, zu bestimmen, ob für eine bestimmte anfängliche Anzahl von Objekten der Spieler, der den ersten Zug macht, gewinnt (da dies ein Spiel mit der Nullsumme ist, andernfalls verliert er) mit einem optimalen Spiel auf beiden Seiten und in welcher minimalen Anzahl von Zügen der Gewinn erreicht wird (oder durch Was ist die maximale Anzahl von Zügen, die der Verlust wegbewegt?

Für einige von H ist die Antwort offensichtlich - mit einem Objekt gewinnt das erste ein direktes Spiel in einer Runde und verliert auch ein inverses Spiel (P1 = 1, I1 = -1). Bei zwei Objekten verliert der erste Spieler in zwei Zügen in einem direkten Spiel und gewinnt in zwei Zügen invers (P2 = -2, I2 = 2), was zu einer Hypothese über die Einfachheit der Bewertung dieses Spiels führen kann, die durch den Fall von drei Objekten bestätigt wird (P2 = 3, I3 = -3). Glücklicherweise (sonst wäre dieser Beitrag nicht veröffentlicht worden) verändert ein Spiel mit vier Objekten das Bild etwas (P4 = -4, aber I4 = -3), so dass eine Recherche des Spiels wirklich erforderlich ist.

Für einige von H und für eine bestimmte Art von Spiel gibt es heuristische Algorithmen, die eine garantierte Auszahlung ermöglichen. Zum Beispiel kann für ein direktes Spiel mit einem ungeraden Anfangs-H garantiert werden, dass Sie gewinnen, wenn Sie das zentrale Objekt mit dem ersten Zug entfernen und dann die Züge des Gegners unter Verwendung einer zentralen Stelle als Symmetrieachse wiederholen. Dann wird garantiert, dass wir das letzte Objekt aufnehmen und gewinnen. Die gleiche Strategie würde mit einer geraden Anzahl von Objekten funktionieren, wenn nicht die Einschränkungen für den ersten Zug, was das Spiel nicht so trivial macht. Im Allgemeinen ist die Verwendung symmetrischer Strategien bei Zählspielen weit verbreitet, jedoch kein Allheilmittel, da diese Strategie beispielsweise in unserem umgekehrten Spiel fehlschlägt. Es sollte beachtet werden, dass Heuristiken einen Gewinnalgorithmus liefern, aber keine genaue Schätzung der Position liefern, da es Strategien geben kann, die zu schnelleren Gewinnen führen (dies ist für dieses spezielle Spiel der Fall).

Wie können wir eine Bewertung des Spiels abgeben - genau wie ich die vorherigen Schätzungen für 1-4 Objekte erhalten habe - die Methode wird als erschöpfende Suche von oben nach unten bezeichnet - wir müssen den vollständigen Baum des Spiels berücksichtigen, dh alle möglichen Bewegungen für beide Seiten und jede Position bewerten, einschließlich Quelle nach bestimmten Regeln. Es ist zu beachten, dass das Vorhandensein erfolgreicher Heuristiken keine genaue Einschätzung garantiert, da nur die erste Hälfte der Frage beantwortet wird - wer gewinnt, aber nicht die erforderliche Mindestanzahl von Zügen angibt.

Dies bedeutet, dass wir einen vollständigen Spielbaum erstellen müssen, aber bevor wir mit der Konstruktion fortfahren, müssen wir ein Modell des untersuchten Objekts erstellen, in unserem Fall des Spiels.

Warum konzentriere ich mich auf diese Phase - weil wir das Objekt in seiner materiellen Verkörperung nicht erforschen können. Nein, rein theoretisch ist dies möglich („auf der Welt ist im Allgemeinen rein theoretisch wenig möglich“), und ich kann mir ein Bild vorstellen, in dem eine sehr große Anzahl von Robotern in der realen Welt viele Spiele spielt, aber die Materialkosten für eine solche Lösung des Problems der Bewertung des Spiels übersteigen die Mengen, so sind wir gezwungen, den Weg der Modellierung realer Objekte mit ihren Software-Gegenstücken zu beschreiten. Und hier ist es sehr wichtig, eine feine Linie zu gehen und ein ausreichendes Maß an Modelladäquanz mit der notwendigen Vereinfachung zu kombinieren.

Aber zuerst ein wenig Mathematik, um die Komplexität der Aufgabe zu beurteilen - wir müssen alle möglichen Züge im Spiel sortieren (Aufmerksamkeit sind nicht alle möglichen Positionen, dies ist das Thema einer anderen Methode, nämlich die Züge) und wir möchten die erforderliche Menge an Ressourcen vor Beginn der Arbeit bewerten -, um die Reihenfolge der Aufgabe zu bestimmen. Beim ersten Zug haben wir die Möglichkeit, jeden Chip (ich werde weiterhin Objekte nennen) aus H zu entfernen, der beim nächsten Zug verfügbar ist - alle verbleibenden H-1 oder zwei Chips in der Nähe (es gibt nicht mehr als solche Paare als H-2) gibt die Gesamtzahl der Optionen Hx (H-1 + H-2) an. Es ist leicht zu erkennen, dass wir nach dem dritten Zug Hx (H-1 + H-2) x (H-2 + H-3 + Δ) und so weiter haben.

Wenn wir uns in jeder Klammer nur auf die ersten Terme der Summe beschränken, erhalten wir eine Schätzung der Gesamtzahl der Züge als H!, Die uns eine Schätzung in Quadraturen von H ^ H gibt.

Dies ist ein sehr unangenehmes Ergebnis, das behauptet, dass wir sehr große Probleme mit signifikantem H haben werden, so dass die "frontale" Modellierung höchstwahrscheinlich erhebliche Rechenkosten verursachen wird. Zum Beispiel müssen wir für 16 Chips in der Startposition ungefähr 16! = 1013 Züge berücksichtigen, und wenn ein Zug 10E-9 Sekunden beträgt (ziemlich optimistische Schätzung), beträgt die Gesamtzeit ungefähr 10E4 Sekunden oder fast 3 Stunden, was ein bisschen viel ist , aber akzeptabel, aber für nur 20 Chips beträgt die erwartete Berechnungszeit 77 Jahre, was eindeutig nicht akzeptabel ist. Factorial wächst sehr schnell und es gibt nichts zu tun.

Wir machen darauf aufmerksam, dass die Anzahl der Züge die Anzahl der möglichen Positionen, die nur 2 ^ N beträgt, deutlich übersteigt, und es ist offensichtlich, dass wir für 16 Chips 10E (13-5) = 10E7-mal in eine separate Position fallen werden, was für jeden ein ziemlich alltägliches Ereignis ist Suchaufgaben. Denken Sie daran, es wird uns später nützlich sein.

Trotzdem werden wir ein Programm schreiben, für das wir das Modell bestimmen werden. Zuerst nummerieren wir die Chips von 1 bis H, erstellen dann ein Array mit der Anzahl der Elemente H und bestimmen, dass die Nummer 1 im Array-Element mit dem Index n das Vorhandensein der Chipnummer n und die Nummer 0 bedeutet - ihre Abwesenheit an einer bestimmten Position. Ein solches Modell ist angemessen, einfach, intuitiv und ermöglicht es Ihnen, Chipentfernungsvorgänge effektiv zu gestalten und den Zustand der "Nähe" zu bestimmen.

Nachdem wir ein Modell (Datenstruktur) haben, können wir beginnen, den Algorithmus für dieses Modell zu ziehen (Eulen auf dem Globus). Der Algorithmus der vollständigen Aufzählung mit Rückgabe ist im Blockdiagramm einfach und besteht aus zwei unabhängigen Teilen - der eigentlichen Aufzählung und Bewertung von Positionen. Zunächst werden wir den ersten Teil implementieren. Beachten Sie, dass dieser Algorithmus nicht am besten im Rahmen des strukturellen Programmierparadigmas implementiert werden kann und etwas effektiver wäre, wenn wir uns erlauben, einen Übergang zu verwenden oder den Code zu wiederholen. Aber auch ohne diese Abweichungen vom Stil ist die Implementierung keineswegs anspruchsvoll (zyklomatische Komplexität ist durchaus akzeptabel). . Da wir noch keine Bewertung eingeführt haben und das Ergebnis aus dem Programm erhalten möchten, leiten wir einfach die betrachteten Positionen ab und schauen sie mit unseren Augen durch, um die korrekte Umsetzung zu bewerten und sicherzustellen, dass die Ergebnisse den erwarteten entsprechen.

Fügen wir nun eine Positionsschätzung hinzu - natürlich ist gut geschriebener Code selbstdokumentierend (obwohl es unterschiedliche Meinungen zu dieser Aussage gibt), aber dieser Teil lässt sich am besten in Worten beschreiben. Die Idee ist, dass wir eine eindeutige Bewertung der Endpositionen (in unserem Fall ist sie einzigartig und besteht aus null Chips) basierend auf den Spielregeln geben und für alle anderen Positionen eine vorläufige neutrale Bewertung abgeben und dann beginnen, sie zu verfeinern, indem wir die Schätzung nach oben verschieben . Wenn Sie sich rückwärts bewegen, ändert sich die Schätzung der aktuellen Position um eins in Richtung von Null. Anschließend wird sie invertiert und an die vorherige Position übertragen, wo sie gemäß den folgenden Regeln mit der vorherigen Schätzung kombiniert wird:

1. neutrale Bewertung ändert sich zu einer neuen,
2. eine positive Bewertung ändert sich zu einer kleineren positiven Bewertung,
3. Eine negative Bewertung ändert sich in eine große negative oder positive.

Nachdem wir alle Schritte vollständig durchlaufen haben, ist die Bewertung der Ausgangsposition endgültig.

Wir fügen unserem Verfahren zur Generierung aller Positionen Schätzungen hinzu und können die Ergebnisse der Analyse, die in einer Tabelle angezeigt werden, bewundern, einen Fortschrittszähler und einen Zeitmesser für die Analyse hinzufügen. Auf dem gcc-Compiler (im Optimierungsmodus -O2) auf einer Maschine mit einem Prozessor habe ich eine solche Tabelle erhalten, die unsere anfänglichen Annahmen über die faktorielle Reihenfolge der Komplexität der Aufgabe vollständig bestätigt. Aus derselben Tabelle geht hervor, dass ich aufgehört habe, Ergebnisse mit H über 11 zu erwarten, weil die Berechnungszeit nicht mehr akzeptabel war (für mich sind Sie vielleicht bereit, eine halbe Stunde zu warten) und unsere Annahme über den Kurs und die Nanosekunde nicht der Realität entspricht (durchschnittliche Zeit) Berücksichtigung der Position ist 100 ns). Es stellt sich die Frage, was wir tun sollen, wenn wir eine Schätzung für mehr als 11 Chips in der Ausgangsposition haben möchten.

Wir könnten den Weg kleiner Optimierungen einschlagen, mit Übergängen und Flags spielen, in Assembler-Einfügungen gehen, knifflige Vektoroperationen aus dem Befehlssystem unseres Prozessors anwenden, und auf diese Weise können Sie manchmal eindeutig an Geschwindigkeit gewinnen, und zwar um eine Größenordnung - vielleicht zwei Größenordnungen - Es ist sehr unwahrscheinlich, aber wir brauchen einen Gewinn von vielen Größenordnungen, da wir in der Größenordnung (und noch mehr) eine Erhöhung von H um eins über 10 essen. Übrigens, wenn Sie nur die Compiler-Optimierung aktivieren, wird dies etwas für uns tun und die Ausführungszeit wird sich verringern Ich habe 4 mal - nicht schlecht und im Einklang mit unseren Erwartungen.

Daher müssen wir zuerst versuchen, die angewandten Algorithmen zu verbessern, und die erste dieser (und die Haupt-) Verbesserung ist die Cut-Off-Brute-Force-Methode oder das "Alpha-Beta-Verfahren". Die Hauptidee sieht ziemlich robust aus und besteht darin, dass wir, wenn wir eine bestimmte Position als eine gewinnende Position bewerten, die Bewertung für diese Position nicht mehr verbessern und zum Baum zurückkehren. Dieser Ansatz kann die Geschwindigkeit des Algorithmus erheblich erhöhen, insbesondere wenn wir zunächst erfolgreiche Züge untersuchen (die zu einem Gewinn führen). Es kann aber auch die Zeit verlängern, da die Überprüfung der aktuellen Bewertung hinzugefügt wird und das Verfahren zur Auswahl des Kurses kompliziert ist. Es ist sehr schwierig, den Einfluss dieser Methode im Voraus abzuschätzen. Es ist notwendig, ein Experiment durchzuführen. Und noch eine Überlegung: Wir sollten nicht vergessen, dass wir bei einer Suche mit Cut-Off und bei einer Gewinnposition eine echte, aber nicht genaue Schätzung abgeben, da wir einen Teil der Optionen nicht berücksichtigen und sie in weniger Zügen einen Gewinn erzielen könnten. Wenn eine solche Abnahme der Genauigkeit zu uns passt, warum nicht diese Methode verwenden, aber für eine genaue Beurteilung funktioniert nichts als eine umfassende Suche nicht.

Die Ergebnisse der Clipping-Aufzählung sind in der folgenden Tabelle aufgeführt. Wir sehen, dass es einen Leistungsgewinn und einen signifikanten Anstieg gibt, der jedoch nicht ausreicht, um große Werte von N zu untersuchen. In welche Richtung wir unsere Forschung fortsetzen werden - zuerst werden wir uns eine andere Datenstruktur ansehen, und dann Sie haben es erraten (schön, mit einem schlauen Publikum umzugehen) ist ein weiterer Algorithmus.

Beachten wir die Tatsache, dass die von uns verwendete Datenstruktur die Chips einzigartig macht und beispielsweise ein einzelner (nicht benachbarter) Chip in Position nicht einem einzelnen Chip in Position n + 2 entspricht, was völlig falsch ist. Wir wählen das Schlüsselelement der Spielposition aus - die Gruppe der Chips, die sich daneben befinden, und bestimmen deren Hauptmerkmal - die Anzahl der Chips in der Gruppe. Es sind diese Informationen, die jede Position im Spiel eindeutig bestimmen, und wir müssen sie in einer für die Programmierung geeigneten Form präsentieren. Wir wählen die einfachste und offensichtlichste Datenstruktur - wir starten ein Array von H-Elementen und speichern im n-Element des Arrays die Anzahl der Gruppen mit genau n Chips. Dann zum Beispiel. Für die Startposition mit 3 Chips haben wir die Darstellung {0,0,1}. Das Ausführungsverfahren für die gegebene Präsentation ist immer noch einfach und effektiv, obwohl es natürlich komplizierter ist als in der ersten Version. Nach dem ersten Zug (von denen es zwei statt drei gab) erhalten wir die Positionen {0,1,0} und {2,0,0}.

Versuchen wir, den erwarteten Gewinn bei der Anzahl der Züge für eine bestimmte Datenstruktur abzuschätzen. Für den ersten Zug haben wir (H-1) / 2 + 1 Optionen, für den zweiten (wir haben die Gruppe H in m und N-m-1 unterteilt) (m-1) / 2 + (N-m-1-1) / 2 (nimm 1 Chip) + (m-2) / 2 + (N-m-1-2) / 2 (nimm 2 Chips) = (H-3) / 2 + (H-5) / 2 und analog Wir schließen daraus, dass wir bei jedem Schritt mindestens die Hälfte der Züge speichern. Dann sollte unser Gewinn mindestens 2 ^ H betragen, was für große H sehr, sehr gut ist. Tatsächlich ist die Verstärkung sogar noch größer, zum Beispiel für die Position {8,0 ...} in der ersten Ausführungsform müssen Sie 8 Züge aussortieren, und in der zweiten ist nur 1 und die Verstärkung in diesem Fall 8-mal. Wir können uns also fest auf 2 ^ H verlassen, aber viel mehr erwarten, was wir überprüfen werden. Und sicher erhalten wir für das Programm gemäß dieser Darstellung Tabelle 4, die letzte Zeile zeigt den Leistungsgewinn beim Umschalten auf die zweite Version der Datenstruktur (von Hand berechnet). Das Wachstum ist einfach kolossal und wir haben zuversichtlich (am Ende) die Obergrenze der Möglichkeit der Analyse von bis zu 20 Chips in der Startposition zu angemessenen Zeitkosten durchbrochen.

Darüber hinaus können wir den Algorithmus für eine bestimmte Datenstruktur subtil optimieren und sogar einen Leistungsgewinn erzielen, aber wir werden kein so dramatisches (um Größenordnungen) Wachstum erzielen, was wiederum darauf hinweist, dass Wirth falsch lag. Im obigen Programm war beispielsweise das Verfahren zum Erstellen des nächsten Kandidaten für den Umzug absichtlich nicht optimal, und seine offensichtliche Korrektur (überlassen wir es dem neugierigen Leser) erhöht die Geschwindigkeit um das Dreifache, aber dies ist eine Kleinigkeit, wenn auch eine angenehme.

Lassen Sie uns auf die Ergebnisse achten und einige nicht offensichtliche Dinge sehen. Zum Beispiel behauptet das Programm, dass ein garantierter Gewinn in einem direkten Spiel für 9 Chips nicht in 9 Zügen erreicht wird, wie aus dem heuristischen symmetrischen Algorithmus folgt, sondern in nur 7, und der erste Zug fällt mit der Heuristik zusammen (und ist darüber hinaus die einzige Gewinnposition ), aber der dritte und die folgenden sollten die Züge des Gegners überhaupt nicht wiederholen, wie aus dem naiven Algorithmus hervorgeht, und der Schlüssel hier ist {1,0,0,1}, was eine Bewertung von +4 hat. Nachdem wir eine genaue Einschätzung des Spiels abgegeben haben, können wir interessante Fragen zum Vorhandensein von Positionen mit einer stabilen Einschätzung (in der wir den Gegner für sich selbst gehen lassen können), zum Vorhandensein von Schlüsselpositionen im Aufzählungsbaum, zum Finden von Positionen mit dem einzig richtigen Zug usw. stellen sogar Antworten auf diese und die richtigen Fragen erhalten).

Hier ist die Übersichtstabelle

Chips	Direkt	Feedback	Positionen / Zeit	Positionen / Zeit
1	1	-1	1/0	1/0
2	-2	2	4/0	2/0
3	3	-3	17/0	7/0
4	-4	-3	82/0	20/0
5	5	4	463/0	71/0
6	5	-5	3032/0	263/0
7	7	6	22693/0	1107/0
8	-8	-7	191422/0	4945/0
9	7	-7	1798427 / 0.1	24.283 / 0
10	9	8	18634228 / 0,8	125419/0
11	11	-9	211177537 / 10.4	699165 / 0,1
12	-10	-9	*** / 127	4057686 / 0,6
13	11	10		25056975 / 3,84
14	-12	-11		160643971/28
15	13	12		1082854607/213
16	-14	-13		*** / 1698

Wir sehen jedoch, dass die Schätzung der Betriebszeit faktoriell blieb, wenn auch mit einem signifikanten Rückgang der Wachstumsrate. Lassen Sie uns nach anderen Möglichkeiten suchen, um den Spielbaum zu erkunden.

Wir haben den Top-Down-Algorithmus perfektioniert (natürlich haben wir ihn nicht in der hässlichen Form fertiggestellt, die ich auf der Rückseite des Umschlags skizziert habe. Sie können die Leistung erheblich verbessern, indem Sie die grundlegenden Verfahren sorgfältig umschreiben. Dies ist sicher möglich, aber das Problem ist nicht grundlegend entscheidet), also gehen wir in die andere Richtung - von unten nach oben. Die Idee dieser Methode ist intuitiv einfach und verständlich, aber für den menschlichen Gebrauch sehr schwierig. Wir gehen von der endgültigen Position aus, die nach den Spielregeln geschätzt wird, und beginnen, die Schätzung nach den gleichen Regeln wie bei der Top-Down-Suche auf den Baum zu übertragen. Gleichzeitig erwägen wir natürlich nicht mögliche Bewegungen von der aktuellen Position nach unten, aber wir betrachten alle Positionen, von denen aus wir in einer Bewegung in die aktuelle Position gelangen könnten. Wir übertragen die Schätzung gemäß den oben genannten Regeln. Darüber hinaus wenden wir dieses Verfahren iterativ an und wenn es keine Ergebnisse mehr liefert, dh in der nächsten Runde hat keine einzige Position die Bewertung geändert, die Aufgabe ist abgeschlossen und die Bewertung der Ausgangsposition ist korrekt und genau. Mit diesem Ansatz können Sie die Suchzeit erheblich verkürzen, insbesondere wenn Sie einige Verbesserungen vornehmen. Er weist jedoch einen starken Nachteil auf (und dies ist ein Klassiker - wir ändern die Speicherzeit), wodurch der Umfang erheblich eingeschränkt wird - hohe Speicheranforderungen, da Schätzungen gespeichert werden müssen , ( ).Im Fall des fraglichen Spiels bietet sich die Bitrepräsentationsmethode für die erste Datenstruktur an. Es gibt andere Methoden, die die Menge des erforderlichen Speichers reduzieren können (Speichern nur der drei betrachteten Baumebenen mit Ausnahme der unteren Schicht), aber natürlich durch Verschlechterung der Leistung, da die Suche sehr nicht trivial wird. Für H nicht größer als 20 beträgt die Gesamtzahl der Positionen jedoch nicht mehr als 2 ^ 20, und ein Array dieser Größe im Speicher für Elemente, die eine Zahl von -20 bis 20 enthalten, dh eine 8-Bit-Zahl, kann ich mir durchaus vorstellen und seine Umsetzung wird nicht schwierig sein. Es ist also durchaus möglich, ein Programm für einen solchen Algorithmus zu schreiben und die resultierende Leistung zu bewerten, aber lassen Sie uns nicht eilen und Schätzungen vornehmen. Welche Art von Speicher wir zuweisen müssen, ist nicht schwer zu bestimmen, aber mit temporären Parametern ist es etwas komplizierter.Angenommen, wir erstellen sofort alle möglichen Positionen, sie sind M, dann kann die durchschnittliche Anzahl von Zügen von einer Position als nicht mehr als 2 * N geschätzt werden (eine sehr grobe Schätzung). Dann müssen wir bei jeder Iteration nicht mehr als M * 2 * H-Übertragung der Schätzung durchführen, und da wir in jedem Zyklus die Schätzung von mindestens einer Position verbessern, liegt die Gesamtarbeitszeit in der Größenordnung von M * 2 * H * M.

Dann erhalten wir für die erste Art der Darstellung der Daten 2 ^ H * M * 2 ^ H = 2 ^ (2 * H) * M (wir betonen noch einmal, dass diese Schätzung von oben sehr stark ist) und zum Beispiel für H = 20 die Schätzung der Suchzeit von oben -down wird 20 sein! ~ 10E18, und für die Bottom-up-Suche haben wir 2 ^ 40 * 20 = (2 ^ 10) ^ 4 * 40 = (10 ^ 3) ^ 4 * 40 ~ 10 ^ 14, dh für 20 Chips Wir gewinnen mindestens 10E6 Mal in der Zeit, was sehr gut ist. Wir werden auch für 9 anfängliche Chips zählen und 9! ~ 10E6 für die Top-Suche und 2 ^ 9 * 2 ^ 9 * 18 ~ 10E6 für das Bottom-Up-Screening erhalten, dh ab dieser Zahl gewinnt die Bottom-Line-Suche. Die letzte Anweisung ist etwas voreilig, da die Prozedur zur Bewertung der nächsten Position erheblich länger geworden ist - wir müssen sie unter den bereits generierten suchen, aber für diese spezielle Darstellung in Form eines Bit-Arrays wird diese Prozedur in O (1) ausgeführt.

Für die zweite Präsentation ist es notwendig, die Anzahl der verschiedenen Positionen zu bewerten, was eine Aufgabe aus dem Bereich der Kombinatorik ist. Stellen Sie sich als Beispiel ein Spiel mit 9 Anfangschips vor, für das die Gesamtzahl der verschiedenen Positionen 1+ (1 + 4) + (1 + 3 + 2) + (1 + 3 + 3 + 2) + (1 + 2 +) beträgt 2 + 1 + 1) + (1 + 2 + 1 + 1) + (1 + 1 + 1) + (1 + 1) + 1 = 1 + 5 + 6 + 9 + 7 + 5 + 3 + 2 + 1 = 39.
Dann führt eine Schätzung nach der gleichen Methode zu einem Wert von H * M * M = 39 * 39 * 9 ~ 10E4, der im Vergleich zur ersten Darstellung zwei Größenordnungen schneller ist, und wenn H wächst, nimmt die Verstärkung nur zu. Verglichen mit der Suche von oben nach der zweiten Ansicht sollte man auch eine signifikante Verbesserung der Leistung erwarten, aber es ist schwieriger, sie zu bewerten, so dass es einfacher ist, es zu versuchen.

Wenn Sie daher ein Parsing-Programm von unten nach oben ausführen, dann für die zweite Präsentation. Ich werde das Programm nicht geben, ich muss den Lesern etwas für die Heimanalyse überlassen. Wir sollten in sehr vernünftiger Zeit Ergebnisse für signifikantes H erhalten. Ein weiterer Vorteil des Bustings von unten besteht darin, dass wir erheblich sparen können, indem wir die Schätzung für die untere Hälfte der Positionen festlegen (die eine geringere Anzahl von Chips als N / 2 aufweist), da die geschätzte untere Hälfte einmal ohne Änderungen für die nächste Anzahl von Chips übertragen wird, was uns einen zusätzlichen Gewinn einbringt 2 mal.

— , , . , , ( ) .

Zusammenfassend lässt sich sagen, dass die notwendige Erklärung für diejenigen, die meinen Beitrag zu ernst genommen haben und mit (fairer) Empörung brennen - ich bin mir nicht sicher, ob die Angabe der Algorithmen als erster Begriff in der Programmdefinitionsformel ihre größere Bedeutung bestätigt. Ich stimme dem vollkommen zu In bestimmten Situationen kann ein korrekt gewählter Algorithmus zu einer geordneten Steigerung der Produktivität führen, und ich wollte Dijkstra (den ich respektiere) nicht mit Fehlern belasten. Es war alles ein Satz, um Aufmerksamkeit zu erregen, und in dem Beitrag geht es um etwas anderes - dass die Datenstruktur auch für die Leistung äußerst wichtig ist, und ich wollte dies im Designprozess nicht vergessen.

PS.Sie erzählen mir hier vom Publikum (hi Max), dass es eine andere Methode gibt, das Spiel zu erforschen - mathematisch, und angesichts der Hypothese des doppelten Nachnamens, dass die meisten Zählspiele auf Nims Spiel zurückzuführen sind, müssen wir ihn nur berechnen - die Summe die Ausgangsposition (meiner Meinung nach ist die Aussage zweifelhaft), und Sie können das ursprüngliche Spiel auch in Spiele in der Grafik umwandeln (hier gibt es keine Einwände), für die Sie zum Zeitpunkt der Arbeit eine Schätzung von 1,878 ^ N erwarten können (obwohl mich die spezifische Zahl etwas verwirrt hat). Wahrscheinlich haben diese Überlegungen das Recht auf Leben, zumindest die Artikel dieses Inhalts sehen überzeugend aus, aber ich bin ein reiner Praktiker und überlasse diese Optionen wieder neugierigen Lesern (ars longa, vita brevis).