Den Baum der Zeit programmieren



    Einleitung


    Nach dem Lesen der TimeCoder- Artikel - „Zeitreise und Programmierung“ [ 1, 2] Ich erinnerte mich an meine bescheidene praktische Forschung in der Programmierung im Zusammenhang mit der Implementierung von Verzweigungswelten. Einmal warf mir mein Arbeitskollege ein interessantes Problem zu, aber ich konnte es immer noch nicht lösen. Die Aufgabe besteht darin, die Maschinen in die Produktion zu laden. Dem Programmierer war nicht einmal klar, dass eine einfache Aufzählung erforderlich war, aber ich konnte keine geeignete Datenstruktur finden, um einen Rechenalgorithmus bereitzustellen. Die Aufgabe stammt aus der realen Welt, daher habe ich mich entschlossen, die reale Welt in dem Teil des Programms zu implementieren, der zur Berechnung der Aufgabe erforderlich ist. In weiteren Berechnungen gab es jedes Mal die Wahl zwischen zwei Aktionen - es gab eine „Erschaffung von zwei neuen Welten“ mit jeweils unterschiedlichen Lösungen. Ferner entwickelte jede Welt ihren eigenen Weg.

    Im Folgenden erfahren Sie, wie sich die Idee entwickelt hat und wie mir die Erlang geholfen hat. Übung ist das Kriterium der Wahrheit!

    Inhalt


    Terminologie - Chart
    erste Probleme
    zu erinnern , was bereits getan wurde
    Convergence Welten
    Methodik
    Schritt 1: Legen Sie die Beschreibung eines Staates der Welt in einer Autokolonne
    Schritt 2 die Funktion beschreiben , die bestimmt , ob die Welt das Ziel erreicht hat ,
    Schritt 3 die Funktion beschreiben , die bestimmt , ob die weitere Entwicklung ist notwendig , Welt
    Schritt 4. die Funktion der Welt der Verzweigung Beschreiben
    Schritt 5 die Funktion Beschreiben Sie den Hash - Wert des Welt - Berechnungsfunktionen
    verbleibenden
    Framework - Version №1
    Anwendung №1 Rahmen für die Lösung von
    Berechnungsoptionen 120 Rubel verschiedene Papiere Gewährung
    Berechnung Glück Tickets
    Berechnung der Happy Tickets, Versuch Nr. 2
    Die Aufgabe "Wolf, Ziege und Kohl"
    Minute des Humors
    Schlussfolgerungen
    Liste der verwendeten Quellen

    Terminologie - Baum der Zeit


    Golovachev nennt eine solche Darstellung der Entwicklung der Weltgeschichte - den Baum der Zeiten oder ein Fraktal [3]. Des Weiteren werde ich die Ergebnissuchmethode unter Verwendung dieses Ansatzes als "Tree of Times-Methode" bezeichnen.

    Die Welt ist eine Liste der Eigenschaften der Welt und ihrer Bedeutungen, die ihren Zustand bestimmen.

    Lösung der Problem - Lösung Aufgabe vom Baum der Zeit, wissen wir das Ergebnis im Voraus, oder den Wert bestimmter Eigenschaften der Welt , dass wir erhalten möchten. Das heißt, wir kennen das Ergebnis, aber der Weg dorthin ist unbekannt. Die Lösung des Problems ist, den Weg zu finden.

    Die Anfangswelt ist ein Bezugspunkt, die Welt, von der aus wir unsere Reise zur Lösung des Problems beginnen.

    Die Zielwelt ist die Welt (oder vielmehr ihr Zustand), in der wir uns bemühen, das Problem zu lösen.

    Weltentwicklung- Entwicklung der Anfangswelt, bemühen wir uns, die Zielwelt zu erreichen.

    Eine Sackgasse ist keine Sackgasse, sondern eine Sackgasse. Dies ist eine Welt, deren weitere Entwicklung nicht zu einer Zielwelt führen wird.

    Erste Probleme


    Um die Methodik zu testen, entschied ich mich für eine Aufgabe wie die Auswahl von Banknoten zu einem bestimmten Betrag oder die Suche nach Glücksscheinen. In jedem Fall schrieb er rekursive Suchergebnisse. Erstellt eine Klasse, die eine Instanz der Welt und ihres gesamten Staates speichert. Möglichkeiten, eine Kopie der Welt zu schaffen, habe ich noch nicht. Die Aufgaben sind einfach und der Eingabeparameter beschreibt die bescheidene Welt vollständig. Aber auch bei so einfachen Aufgaben wurden alle Nachteile dieses Ansatzes deutlich. Die Entwicklungszweige expandieren sehr schnell.

    In einem Traum kam mir eine Analogie mit einem Atomreaktor und der Teilchenspaltung darin. Es kommt zu einer Spaltung und einer Kettenreaktion infolge einer Explosion. Um die Explosion zu verhindern, wird der Teilungsprozess gesteuert. Es wurde klar, dass der Prozess der Schaffung neuer Zweige der Welten kontrolliert und sehr schwierig sein muss: Wenn die Welt nicht zum gewünschten Ergebnis führt, zerstören wir sie, wenn die Welt das Ziel ihrer Entwicklung erreicht hat, leiten wir das Ergebnis ab. Fazit Die Ergebnisse zeigten , dass die Art und Weise Ergebnisse zu erzielen ist auch notwendig , Welten zu teuer durch (Ausgabe von 1000 Rubel 10-Rubel - Scheine zu kontrollieren und zu zerstören. Ein weiteres Problem ist die Entdeckung von mehreren identischen Ergebnissen war. Verschiedene Möglichkeiten der weltweiten Entwicklung schließlich zu dem gleichen Ergebnis führen könnte.

    In diesem Bei der Berechnung mit der Tree of Times-Methode müssen daher die folgenden Probleme gelöst werden:

    • Beschränken Sie die sinnlose Parallelisierung von Realitäten, da die Ressourcen begrenzt sind
    • Um den Weg zu einem Ergebnis zu analysieren, gehen Sie nicht weiter, wenn Sie die Welt auf eine „harte“ Weise oder auf eine Weise erreicht haben, die wir nicht benötigen
    • Es muss etwas mit doppelten Ergebnissen getan werden. In der Tat können verschiedene Welten auf unterschiedliche Weise zum selben Zustand gelangen - was tun?


    Die langjährige Geschichte der Berechnung der Ergebnisse nach der „Tree of Times-Methode“ lag vorerst „in my desk“. Weil nicht alle Rechenprobleme gelöst wurden. Ja, und es ist klar, dass es Zeit ist, paralleles Rechnen anzuwenden, das sich von den mir vertrauten Programmiersprachen unterscheidet. Es gab jedoch keine einfachen Lösungen.

    Im Laufe der Zeit entwickelt sich die Technologie im Bereich der Programmierung. Es wurde klar, dass es unendlich unmöglich ist, Megahertz zu erhöhen. Die Berechnungen müssen parallelisiert werden. Und solche Gelegenheiten begannen sich zu bieten, und die Unterstützung für Parallelität in den Sprachen begann sich zu vereinfachen.

    Aber was ist mit den Klonen der Welten? Fall aus dem Totpunkt verschoben TimeCoder Artikel . Man muss in der Lage sein, die Zweige der Entwicklung von Welten nicht nur zu trennen, sondern sie auch miteinander zu verbinden.

    Mit neuen Ideen und Werkzeugen ausgestattet, beschloss ich, wieder die Bäume der Zeit zu erkunden.

    Erinnern Sie sich daran, was bereits getan wurde


    Die Herausforderung sind Glückskarten. Ein Ticket hat Glück, wenn die Summe der ersten drei Ziffern der Summe der übrigen Ziffern entspricht.
    C QT [4]:
    void bilet(int x1, int x2, int x3, int x4, int x5, int x6)
    {
        //проверка достижения результата
        if ((x1+x2+x3)==(x4+x5+x6))
        {
            qDebug() << x1<< x2<< x3<< x4<< x5<< x6;
        }
        //новые ветки
        if((x1+1)<3)
            bilet(x1 + 1, x2, x3, x4, x5, x6);
        if((x2+1)<10)
            bilet(x1, x2 + 1, x3, x4, x5, x6);
        if((x3+1)<10)
            bilet(x1, x2, x3 + 1, x4, x5, x6);
        if((x4+1)<10)
            bilet(x1, x2, x3, x4 + 1, x5, x6);
        if((x5+1)<10)
            bilet(x1, x2, x3, x4, x5 + 1, x6);
        if((x6+1)<3)
            bilet(x1, x2, x3, x4, x5, x6 + 1);
    }
    //запуск
    bilet(0, 0, 0, 0, 0, 0);
    

    Ich habe nicht auf das Ergebnis gewartet. Eine lange Zeit. Deshalb habe ich einen Teil des Codes entfernt:
    void bilet(int x1, int x2, int x3, int x4, int x5, int x6)
    {
        //проверка достижения результата
        if ((x1+x2+x3)==(x4+x5+x6))
        {
            qDebug() << x1<< x2<< x3<< x4<< x5<< x6;
        }
        //новые ветки
        if((x1+1)<3)
            bilet(x1 + 1, x2, x3, x4, x5, x6);
        if((x6+1)<3)
            bilet(x1, x2, x3, x4, x5, x6 + 1);
    }
    

    Das Ergebnis war wie folgt:
    000000
    200002
    100001
    200002
    200002
    100001
    200002
    200002
    200002
    

    Der Algorithmus wurde nicht optimiert. Nicht besonders durchdacht. Und das entsprechende Ergebnis ist Duplikate.

    Die Aufgabe ist es, Geld zu tauschen. Es gebe 1000, 500, 100, 50, 10 Rubel. Es ist notwendig, die Optionen für die Ausgabe zu berechnen.
    Erlang-Lösung [5,6]: we01.erl- Datei :
    -module(we01).
    -export([sum_money/6, sum_money/1]).
    sum_money(Itog) ->
    	sum_money(Itog, 0, 0, 0, 0, 0).
    sum_money(Itog, X1000, X500, X100, X50, X10) ->
    	if 
    	((X1000 + X500 + X100 + X50 + X10) > 100) -> 
    		ok;
    	(Itog == ((1000*X1000)+(500*X500)+(100*X100)+(50*X50)+(10*X10))) ->
    		io:format("Itog(~w)(~w) = 1000*~w + 500*~w + 100*~w + 50*~w + 10*~w ~n", [Itog,(X1000 + X500 + X100 + X50 + X10), X1000, X500, X100, X50, X10]);
    	(Itog > ((1000*X1000)+(500*X500)+(100*X100)+(50*X50)+(10*X10))) ->
    		sum_money(Itog, 1+X1000,   X500,   X100,   X50,   X10),
    		sum_money(Itog,   X1000, 1+X500,   X100,   X50,   X10),
    		sum_money(Itog,   X1000,   X500, 1+X100,   X50,   X10),
    		sum_money(Itog,   X1000,   X500,   X100, 1+X50,   X10),
    		sum_money(Itog,   X1000,   X500,   X100,   X50, 1+X10);
    	(true) ->
    		ok		
    	end.
    

    Wie führe ich diese Datei auf Erlang aus?
    1. Starten Sie Erlang:
      erl

    2. Wir kompilieren das Modul:
      c(we01).

    3. Wir starten die Berechnung der Ausgabe von 120 Rubel:
      we01:sum_money(120).

    4. Ergebnis:
      Itog(120)(3) = 1000*0 + 500*0 + 100*1 + 50*0 + 10*2
      Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2
      Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2
      Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2
      Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7
      Itog(120)(3) = 1000*0 + 500*0 + 100*1 + 50*0 + 10*2
      Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2
      Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2
      Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7
      Itog(120)(3) = 1000*0 + 500*0 + 100*1 + 50*0 + 10*2
      Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2
      Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7
      Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7
      Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7
      Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7
      Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7
      Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7
      Itog(120)(12) = 1000*0 + 500*0 + 100*0 + 50*0 + 10*12
      ok        ^
                |
                +---- количество купюр
      


    Offensichtlich müssen Sie Duplikate (identische Welten) irgendwie ignorieren. Ein für die richtige Programmierung geschultes Gehirn beginnt sofort darüber nachzudenken, wie der Algorithmus optimiert werden kann, damit dies nicht passiert, Optimierung, Optimierung ... Eigentlich ist dies ein sehr einfaches Beispiel, aber selbst hier wird es schwierig, eine Optimierung zu finden. Und was wird in komplexeren Welten passieren? Wenn es eine solche Gelegenheit gibt, ist es im Allgemeinen nicht notwendig, offensichtlich überflüssige Welten zu produzieren, in allen anderen Fällen ist es notwendig, Methoden zur Konvergenz von Welten zu erfinden.

    Weltweite Konvergenz


    Versuchen wir zu überprüfen, ob es eine solche gibt. Wenn ja, dann nichts anderes tun (keine Kinderwelten erschaffen).
    Also, QT, die Aufgabe ist wieder die gleiche - Tickets:
    QHash hash; //хэш для хранения миров
    void bilet(int x1, int x2, int x3, int x4, int x5, int x6)
    {
        int result = x1*100000+x2*10000+x3*1000+x4*100+x5*10+x6;
        if(hash.contains(result))
        {
            //вывод поскипанного мира. такой уже есть
            //qDebug() << x1<< x2<< x3<< x4<< x5<< x6 << "skip";
            return;
        } else {
            //нету. добавляем в хеш
            hash.insert(result, ((x1+x2+x3)==(x4+x5+x6)));
        }
        //проверка достижения результата
        if ((x1+x2+x3)==(x4+x5+x6))
        {
            //вывод, если нашли
            //qDebug() << x1<< x2<< x3<< x4<< x5<< x6 << "*";
        } else {
            //вывод, если не нашли
            //qDebug() << x1<< x2<< x3<< x4<< x5<< x6;
        }
        //новые ветки
        if((x1+1)<10)
            bilet(x1 + 1, x2, x3, x4, x5, x6);
        if((x2+1)<10)
            bilet(x1, x2 + 1, x3, x4, x5, x6);
        if((x3+1)<10)
            bilet(x1, x2, x3 + 1, x4, x5, x6);
        if((x4+1)<10)
            bilet(x1, x2, x3, x4 + 1, x5, x6);
        if((x5+1)<10)
            bilet(x1, x2, x3, x4, x5 + 1, x6);
        if((x6+1)<10)
            bilet(x1, x2, x3, x4, x5, x6 + 1);
    }
    

    Um zu analysieren, in welchen Welten wir uns befinden, werden wir die Schlussfolgerung diskutieren, ob wir gefunden haben und ob wir nicht. Ersetzen Sie unter allen Umständen <10 durch <2, um den Rechenaufwand zu begrenzen. Wir fangen an. Ergebnis:
    Ergebnis
    start "00:19:04.394"
    0 0 0 0 0 0 *
    1 0 0 0 0 0
    1 1 0 0 0 0
    1 1 1 0 0 0
    1 1 1 1 0 0
    1 1 1 1 1 0
    1 1 1 1 1 1 *
    1 1 1 1 0 1
    1 1 1 0 1 0
    1 1 1 0 1 1
    1 1 1 0 0 1
    1 1 0 1 0 0
    1 1 0 1 1 0 *
    1 1 0 1 1 1
    1 1 0 1 0 1 *
    1 1 0 0 1 0
    1 1 0 0 1 1 *
    1 1 0 0 0 1
    1 0 1 0 0 0
    1 0 1 1 0 0
    1 0 1 1 1 0 *
    1 0 1 1 1 1
    1 0 1 1 0 1 *
    1 0 1 0 1 0
    1 0 1 0 1 1 *
    1 0 1 0 0 1
    1 0 0 1 0 0 *
    1 0 0 1 1 0
    1 0 0 1 1 1
    1 0 0 1 0 1
    1 0 0 0 1 0 *
    1 0 0 0 1 1
    1 0 0 0 0 1 *
    0 1 0 0 0 0
    0 1 1 0 0 0
    0 1 1 1 0 0
    0 1 1 1 1 0 *
    0 1 1 1 1 1
    0 1 1 1 0 1 *
    0 1 1 0 1 0
    0 1 1 0 1 1 *
    0 1 1 0 0 1
    0 1 0 1 0 0 *
    0 1 0 1 1 0
    0 1 0 1 1 1
    0 1 0 1 0 1
    0 1 0 0 1 0 *
    0 1 0 0 1 1
    0 1 0 0 0 1 *
    0 0 1 0 0 0
    0 0 1 1 0 0 *
    0 0 1 1 1 0
    0 0 1 1 1 1
    0 0 1 1 0 1
    0 0 1 0 1 0 *
    0 0 1 0 1 1
    0 0 1 0 0 1 *
    0 0 0 1 0 0
    0 0 0 1 1 0
    0 0 0 1 1 1
    0 0 0 1 0 1
    0 0 0 0 1 0
    0 0 0 0 1 1
    0 0 0 0 0 1
    end "00:19:04.407"
    

    Insgesamt gibt es 64 Zeilen, d. H. 2 ^ 6, das ist wahr. In vollem Umfang arbeitet der Algorithmus schnell, ungefähr 155 ms. Parallelisierung mit QtConcurect war nicht ohne weiteres möglich.

    Was ist mit Erlang?

    Die Aufgabe ist die gleiche - das Sortieren von Tickets. In Erlang gibt es jedoch keine globalen Variablen.
    Als Repository haben wir einen Prozess.
    %хранилище списка существующих миров (узкое место, замена глобальной переменной)
    world_server(World_list) ->
    	receive
    		finished ->
    			io:format("World server is down~n", []);
    		list ->
    			io:format("World list ~w ~n", [World_list]),
    			world_server(World_list);
    		{new_world, PID, New_world, Par} ->
    			%ищем новый мир
    			case lists:keymember(New_world, 1, World_list) of
    				true ->
    					PID ! world_exist,
    					world_server(World_list); % не добавляем мир
    				false ->
    					PID ! world_new,
    					world_server([{New_world, Par}|World_list]) % добавляем мир
    			end
    	end.
    world_server_start() ->
    	register(ws, spawn(?MODULE, world_server, [[]])).
    world_server_stop() ->
    	ws ! finished.
    

    Wie funktioniert das?
    Um den Server zu starten, wird eine Funktion aufgerufen world_server_start(). Die Funktion world_server wird in einem neuen Thread ausgeführt und mit einem Namen verknüpft ws. Die Funktion ruft sich selbst rekursiv auf und übergibt als Parameter eine Liste von Welten. Zunächst wird es übergeben, []dh ein leeres Array. Während der Arbeit wartet die Funktion immer auf Nachrichten von anderen Prozessen:
    • Wenn die Nachricht ein Atom ist finished, zeigt die Funktion eine Stop-Nachricht an und ruft sich nicht rekursiv auf, wodurch der Server gestoppt wird.
    • Wenn eine Nachricht empfangen wird - atom list, wird eine Liste der Welten angezeigt und die Arbeit wird fortgesetzt (zum Debuggen verwendet).
    • Wenn ein Tupel akzeptiert wird {new_world, PID, New_world, Par}, bedeutet dies, dass der Server gefragt wird, ob eine solche Welt in der Liste enthalten ist. Wenn es eine Welt gibt, wird eine Nachricht an den Prozess world_exist oder zurückgegeben world_new, und die Funktion wird mit dem Hinzufügen einer neuen Welt zur Liste weiter ausgeführt (wenn es bereits keine gibt).


    Einmal in einer Funktion landen wir im Wesentlichen in der Welt. Und zuallererst überprüfen wir die Existenz - wir senden eine Anfrage an den Worlds Repository Server. Wenn Sie eine Antwort bekommen world_exist, arbeiten wir nicht weiter (return ok). Ansonsten zeigen wir Informationen über die Welt an (mit einem Sternchen, wenn es das Ziel ist - das Ticket ist glücklich).

    new_ww(X1, X2, X3, X4, X5, X6) ->
    	ws ! {new_world, self(), X1*10+X2*100+X3*1000+X4*10000+X5*100000+X6*1000000, (X1+X2+X3 == X4+X5+X6) },
    	receive
    		world_exist -> ok;
    		world_new ->
    			if (X1+X2+X3 == X4+X5+X6) ->
    				io:format("~w ~w ~w ~w ~w ~w *~n", [X1, X2, X3, X4, X5, X6]);
    				true-> io:format("~w ~w ~w ~w ~w ~w ~n", [X1, X2, X3, X4, X5, X6])
    			end,	
    			if 
    			   ((X1+1) < 10) ->
    				new_ww(X1+1, X2, X3, X4, X5, X6);
    			   true -> ok
    			end,
    			if 
    			   ((X2+1) < 10) ->
    				new_ww(X1, X2+1, X3, X4, X5, X6);
    			   true -> ok
    			end,
    			if 
    			   ((X3+1) < 10) ->
    				new_ww(X1, X2, X3+1, X4, X5, X6);
    			   true -> ok
    			end,
    			if 
    			   ((X4+1) < 10) ->
    				new_ww(X1, X2, X3, X4+1, X5, X6);
    			   true -> ok
    			end,
    			if 
    			   ((X5+1) < 10) ->
    				new_ww(X1, X2, X3, X4, X5+1, X6);
    			   true -> ok
    			end,
    			if 
    			   ((X6+1) < 10) ->
    				new_ww(X1, X2, X3, X4, X5, X6+1);
    			   true -> ok
    			end
    	end.
    

    Was ist aus neuen Technologien in Form von Erlang geworden? Bisher nichts:
    • gilt als länger als C ++ QT
    • Es gibt keine Parallelisierungen und Multi-Machine-Computing
    • FP enthält keinen eleganten und kompakten Code, sondern Blätter mit demselben Codetyp
    • Insgesamt löste eine rekursive Funktion eine einfache Aufzählung von Werten, die in prozeduralen Sprachen durch Zyklen einfacher und klarer gelöst wird. nicht jeder versteht und liebt Rekursion

    Was zu tun Benötigen Sie eine Methodik! Einfach, Schritt für Schritt, auch für Studenten verständlich.

    Methodik




    Nach den Experimenten bin ich zu dem Schluss gekommen, dass bestimmte Teile des Codes für alle Berechnungen gleich sind, nur die Bedingungen ändern sich. Wenn Sie die Aufgabe und ihre Programmierung festlegen, können Sie sich daher vollständig von Rekursion, Parallelisierung und anderen technischen Tricks verabschieden und sich darauf konzentrieren, die Bedingungen für die Berechnung festzulegen. Das heißt, erstellen Sie eine Art Rahmen für die Berechnung. In Erlang-Methoden wird dies als Verhalten bezeichnet. Um beispielsweise einen Server zu implementieren, müssen Sie unter dem Strich dessen Verhalten implementieren: Was ist beim Starten, Stoppen usw. zu tun?

    Was gibt es? Jedes Verhalten ist eine einfache und unkomplizierte Funktion. Eine reine Funktion, deren Ergebnis nur von den Eingabedaten abhängt. Sie kann unabhängig von anderen überprüft werden.

    So erschien eine Framework-Version 1. Um das Problem zu lösen, müssen Sie die Schritte ausführen

    Schritt 1. Schreiben Sie eine Beschreibung eines Zustands der Welt in ein Tupel

    Ein wichtiger Punkt bei der Programmierung von Berechnungen für Bäume der Zeit ist die Vereinbarung, wie eine Beschreibung der Welt gespeichert werden soll. Was in der Fiktion als "Matrix der Welt" bezeichnet wird. Die Beschreibung der Welt enthält Informationen über den aktuellen Zustand der Welt, aber nur das, was benötigt wird.

    In meinen früheren Studien zu den Bäumen der Zeit habe ich versucht, Klassen und Felder zu verwenden, aber die Programmierung für jede einzelne Aufgabe hat mich dazu gezwungen, viel Code zu schreiben, der schnell nicht mehr verständlich und universell war. Daher ist es notwendig, die Welt so einfach wie möglich zu beschreiben.

    Weltbeschreibungsvereinbarung: Die Welt muss in einem Tupel beschrieben werden.

    Ein Tupel ist eine Menge von Werten mit begrenzter Länge. Das Tupel ist auf geschweifte Klammern beschränkt, und die Elemente des Tupels sind durch Kommas voneinander getrennt. Tupel können ineinander verschachtelt werden.

    Beispiel 1. Ein Tupel, das den Zustand der Welt zum Anfangszeitpunkt der Berechnung der Optionen für Glückskarten beschreibt.
    {0,0,0,0,0,0}
    

    Jede Ziffer ist eine separate Ziffer in der Ticketnummer.

    Richtiger wäre es, nicht „im Anfangszeitpunkt“ zu schreiben, sondern „im Anfangszustand der Welt“, weil die Zeit für eine bestimmte Welt keine Rolle spielt. Nur der Zustand der Welt ist von Bedeutung. Wenn Zeit in der Form, in der wir es zu verstehen gewohnt sind, für die Berechnungen von Bedeutung ist, wird sie als ein weiterer Wert im Tupel hinzugefügt.

    Beispiel 2. Ein Tupel, das den Zustand der Welt beschreibt, in dem wir einen Weg gefunden haben, 120 Rubel in Form von 1x100r und 2x10r auszugeben . Wir haben fünf Arten von Banknoten: 1000, 500, 100, 50, 10. Daher wird die Welt fünf Parameter haben. Es wurde beschlossen, dass sie von größer nach kleiner folgen, dh die erste Zahl ist die Zahl von 1000 Rubel usw.
    {0,0,1,0,2}
    


    Schritt 2. Beschreibe die Funktion, die bestimmt, ob die Welt ihr Ziel erreicht hat

    Die Funktion wird als Parameter an die Welt übergeben. Ihre Aufgabe ist es festzustellen, ob er ins Visier genommen wird. Wenn ja, drucken Sie das Ergebnis aus und senden Sie es zurück true. Sonst false. Wenn die Welt ihr Ziel erreicht hat, muss das Framework es offensichtlich nicht weiterentwickeln. Die Weiterentwicklung der Welt in einem kombinatorischen Problem kann zu anderen Lösungen führen.

    Schritt 3. Beschreiben Sie die Funktion, die bestimmt, ob die Welt weiterentwickelt werden muss.

    Die Funktion wird als Parameter an die Welt übergeben. Ihre Aufgabe ist es, herauszufinden, ob sie weiterentwickelt werden soll. Wenn die Weiterentwicklung der Welt nicht zu einem Ziel führen kann, dann ist ihre Weiterentwicklung nicht sinnvoll. Sackgasse. Wenn Entwicklung nötig ist, kehren wir zurück true. Sonst false. Wenn die weitere Entwicklung der Welt eine Sackgasse ist, bedeutet dies nicht, dass die Welt nicht ins Visier genommen werden kann.

    Schritt 4. Beschreiben Sie die Verzweigungsfunktion der Welt

    Die Entwicklung der Welt kann in verschiedene Richtungen gehen. Die Funktion wird als Parameter an die Welt übergeben. Als Antwort wird eine Liste von Welten ausgegeben, in die Sie sich aus dieser Welt entwickeln können.

    Schritt 5. Beschreiben Sie die Funktion der Berechnung des Hash der Welt

    Standardmäßig sieht die Welt-HASH-Berechnungsfunktion folgendermaßen aus:
    %%хеш мира
    w2hash(Wrld) ->
    	erlang:phash2(Wrld).
    

    Die Standardfunktion erlang:phash2erzeugt einen Hash - die Nummer des übertragenen Tupels. Die genaue Entsprechung einer Welt zur anderen ist jedoch nicht immer erforderlich. Dies wurde in den Artikeln [1, 2] geschrieben, die Quintessenz ist, dass Sie unabhängig von den getroffenen Zwischenentscheidungen zu einem Ergebnis kommen können und die Entwicklungszweige zusammenlaufen werden. Die Welten konvergieren nicht „bis zum Atom“, sondern konvergieren im Rahmen der Problemlösung. Wenn die Aufgabe darin besteht, mit dem Auto zur Arbeit zu kommen, können Sie über verschiedene Straßen kommen, aber um 12 Uhr sind wir beim Treffen. Der Unterschied wird natürlich in der Laufleistung des Autos liegen, aber dieser Moment spielt für uns keine Rolle.

    Die Konvergenz der Welten im Rahmen Nummer 1 wird durch das Repository von bereits erstellten Welten implementiert. Vielmehr die Hash-Nummern dieser Welten. Und wenn die Welt, die wir während der Entwicklung eines Zweigs betreten haben, bereits im Repository vorhanden ist, dann findet die weitere Entwicklung der Welt nicht statt. Tatsächlich konvergieren die Welten, weil die beiden Entwicklungspfade der Welten zu demselben Ergebnis führten und den gleichen Weg weiter gingen. Wenn daher einer der Parameter der Welt das Ergebnis nicht beeinflusst, müssen Sie die Funktion zur Berechnung des Hash der Welt so anpassen, dass dieser Parameter nicht an der Konvertierung der Tupel-> Hash-Nummer beteiligt ist.

    Andere Funktionen

    Funktionen wie Aufzählung, Welten, Konvergenz von Welten sind für jede Aufgabe gleich. Sie werden in das Framework aufgenommen und der Benutzer muss sie nicht ändern / verstehen. Wenn Sie sich strikt an die Methodik halten, können Sie das Framework im Hinblick auf paralleles Rechnen verbessern, ohne die Funktionen zu ändern, die die Regeln der Welt definieren.

    Framework Version 1

    wf1.erl
    -module(wf1).
    -export([start/0, stop/0, br/1, is_target/1, is_dead/1, ent/1, lib/0]).
    %%хеш мира
    w2hash(Wrld) ->
        erlang:phash2(Wrld).
    %%хранилище миров
    lib() -> lib([]).
    lib(List) ->
        receive
    	stop -> ok;
    	{Wrld, Pid} ->
    	    WHash = w2hash(Wrld),
    	    NewList = case lists:member(WHash, List) of
    					false ->
    						Pid ! ok,
    						[WHash]++List;
    					true ->
    						Pid ! exist,
    						List
    				  end,
    	    lib(NewList);
    	_ -> ok
        end.
    ent([]) -> ok;
    %%на вход подается список кортежей миров, список делится на первый мир в списке Wrld
    %%и на хвост Tail из оставшихся
    ent([Wrld|Tail]) ->
    	try spawn(?MODULE, ent, [Wrld]) of
    		_Pid -> ent(Tail)
    	catch
    		_:_ -> 
    		io:format("spawn overload~n", []),
    		ent(Wrld),
    		ent(Tail)
    	end;
    %%на вход подается кортеж одного мира
    ent(Wrld) ->
        lib_srv ! {Wrld, self()}, %% проверяем существует ли такой мир уже
        receive 
    		ok ->
    			is_target(Wrld), %% является ли целевым
    			Is_dead = is_dead(Wrld), %% является ли тупиком
    			if
    				(Is_dead==false) -> %% если не тупик - плодим ветки и идем в них
    					NewBranches = br(Wrld),
    					ent(NewBranches);
    				true -> ok
    			end;
    		exist ->
    			ok
    	end.
    stop() ->
        lib_srv ! stop.
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %% функции, определяемые пользователем
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%Мир достиг цели?
    is_target(Wrld) ->
        true.
    %%Мир - тупиковая ветвь
    is_dead(Wrld) ->
        false.
    %%Ветвление мира
    br(Wrld) ->
    [].
    %%запуск расчета
    start() ->
        register(lib_srv, spawn(?MODULE, lib, [])),
        io:format("start~n", []),
    	%% внутри [] нужно передать начальный мир
        spawn(?MODULE, ent, [[]]).
    


    Anwendung des Framework Nr. 1 zur Lösung von Problemen



    Berechnung der Optionen für die Ausgabe von 120 Rubel mit verschiedenen Papierstücken



    Schritt 1 - Die Welt in eine Wagenkolonne legen Die

    Welt wird in fünf Ziffern beschrieben.
    {0,0,0,0,0}
    


    Schritt 2. Beschreibe die Funktion, die bestimmt, ob die Welt ihr Ziel erreicht hat
    %%Мир достиг цели?
    is_target(Wrld) ->
    	{X1000,X500,X100,X50,X10} = Wrld,
    	if ((X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)==120) ->
    		io:format("120 (~w) = 1000p*~w 500p*~w 100p*~w 50p*~w 10p*~w~n", [X1000+X500+X100+X50+X10,X1000,X500,X100,X50,X10]);
    		true -> ok
    	end,
    	(X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)==120. 
    

    Ein kleiner Hinweis zur Erlang-Syntax. Die allererste Operation ist keine Aufgabe, sondern eine Übereinstimmung. Die Variable Wrld enthält ein Tupel mit fünf Elementen. Wenn die Operation ausgeführt wird, werden die Werte der Elemente im Tupel den Variablen zugewiesen X1000, X500, X100, X50, X10. Weitere Details zum Spiel in Erlang lesen Sie bitte auf eigene Faust. Oder akzeptieren Sie einfach die Syntax, um beispielsweise Werte aus einem Tupel zu ziehen.

    Schritt 3. Beschreiben Sie die Funktion, die bestimmt, ob die Welt weiterentwickelt werden muss.
    %%Мир - тупиковая ветвь
    is_dead(Wrld) ->
    	{X1000,X500,X100,X50,X10} = Wrld,
    	(X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)>120. 
    


    Schritt 4. Beschreiben Sie die Verzweigungsfunktion der Welt
    %%Ветвление мира
    br(Wrld) ->
    	{X1000,X500,X100,X50,X10} = Wrld,
        [
    	 {X1000+1,X500,X100,X50,X10},
    	 {X1000,X500+1,X100,X50,X10},
    	 {X1000,X500,X100+1,X50,X10},
    	 {X1000,X500,X100,X50+1,X10},
    	 {X1000,X500,X100,X50,X10+1}
    	].
    


    Berechnung starten
    %%запуск расчета
    start() ->
        register(lib_srv, spawn(?MODULE, lib, [])),
        io:format("start~n", []),
    	%% внутри [] нужно передать начальный мир
        spawn(?MODULE, ent, [{0,0,0,0,0}]).
    


    Als Ergebnis erhielten wir:
    1> c(wf1).
    {ok,wf1}
    2> wf1:start().
    start
    <0.455.0>
    120 (3) = 1000x0 500x0 100x1 50x0 10x2
    120 (4) = 1000x0 500x0 100x0 50x2 10x2
    120 (8) = 1000x0 500x0 100x0 50x1 10x7
    120 (12) = 1000x0 500x0 100x0 50x0 10x12
    


    Berechnung von Glückskarten



    Schritt 1 - Lege die Welt in eine Wagenkolonne, die sechsstellig

    beschrieben ist.
    {0,0,0,0,0,0}
    


    Schritt 2. Beschreibe die Funktion, die bestimmt, ob die Welt ihr Ziel erreicht hat
    %%Мир достиг цели?
    is_target(Wrld) ->
    	{X1,X2,X3,X4,X5,X6} = Wrld,
    	if ((X1+X2+X3)==(X4+X5+X6)) ->
    		cnt_srv ! inc,
    		cnt_srv ! {cnt, self()},
    		receive
    			X -> ok
    		end,
    		io:format("~w ~w ~w ~w ~w ~w (~w)~n", [X1,X2,X3,X4,X5,X6, X]);
    		true -> ok
    	end,
    	((X1+X2+X3)==(X4+X5+X6)). 
    


    Schritt 3. Beschreiben Sie die Funktion, die bestimmt, ob die Welt weiterentwickelt werden muss.
    %%Мир - тупиковая ветвь
    is_dead(Wrld) ->
    	{X1,X2,X3,X4,X5,X6} = Wrld,
    	if
    		(X1>9)-> true;
    		(X2>9)-> true;
    		(X3>9)-> true;
    		(X4>9)-> true;
    		(X5>9)-> true;
    		(X6>9)-> true;
    		true -> false
    	end.
    


    Schritt 4. Beschreiben Sie die Verzweigungsfunktion der Welt
    %%Ветвление мира
    br(Wrld) ->
    	{X1,X2,X3,X4,X5,X6} = Wrld,
        [
    	 {X1+1,X2,X3,X4,X5,X6},
    	 {X1,X2+1,X3,X4,X5,X6},
    	 {X1,X2,X3+1,X4,X5,X6},
    	 {X1,X2,X3,X4+1,X5,X6},
    	 {X1,X2,X3,X4,X5+1,X6},
    	 {X1,X2,X3,X4,X5,X6+1}
    	].
    


    Um die Anzahl der glücklichen Tickets zu berechnen, werden wir einen weiteren Server erstellen, der die Anzahl der gefundenen Welten speichert, erhöht und mit einem positiven Ergebnis versieht:
    %%кол-во результатов
    cnt() -> cnt(0).
    cnt(N) ->
    	receive
    	inc -> cnt(N+1);
    	{cnt,Pid} ->
    		Pid ! N,
    		cnt(N)
    	end.
    


    Wenn Sie die Berechnung starten, starten wir sie auch:
    %%запуск расчета
    start() ->
        register(lib_srv, spawn(?MODULE, lib, [])),
        register(cnt_srv, spawn(?MODULE, cnt, [])),	
        io:format("start~n", []),
    	%% внутри [] нужно передать начальный мир
        spawn(?MODULE, ent, [{0,0,0,0,0,0}]).
    


    Wenn Sie die Regeln jedoch auf diese Weise festlegen, müssen Sie lange auf das Ergebnis warten. Es werden so viele Prozesse erstellt, dass der Erlang-Knoten nicht mehr mit so vielen Prozessen zu tun hat und keine neuen Prozesse mehr erstellt. Und das ist gut so, denn ich musste eine Lösung für dieses Problem finden (via try).

    Offensichtlich ist die Verzweigung der Welten nicht optimal eingestellt, und es stellt sich heraus, dass dieselben Welten mehrmals geschaffen werden, dass ständig Kontrollen durchgeführt werden und dass die Welten bereits existierten. Dies deutet darauf hin, dass Sie bei solch anspruchsvollen Aufgaben immer noch das Gehirn benutzen müssen.

    Berechnung der Glückskarten, Versuch Nr. 2



    Die Lösung des Problems der glücklichen Tickets erwies sich als sehr nützlich. Während des Lösungsprozesses wurden für jeden Schritt eine Reihe sehr wichtiger Nuancen gefunden, und der Hauptzyklus der Verarbeitung der Welten erforderte eine Anpassung. Und sogar die Notwendigkeit von Schritt Nr. 5 (der ursprünglich nicht vorhanden war) wurde offengelegt.

    Ein früherer Versuch, das Problem mit Tickets zu lösen, zeigte, dass wir die Welten nicht effektiv verzweigten, was zu einer großen Anzahl von Takes führte. Es ist jedoch kein Problem, alle Optionen für die Entwicklung der Welt unmittelbar vom Ausgangszustand an zu berechnen. Aber wir haben Erlang, also werden wir es rekursiv tun, indem wir das Segment in zwei Hälften teilen. Das Segment wird von 0 bis 999999 sein, wir werden es teilen, bis die Grenzen der Bereiche zusammenfallen. Daher werden die Eigenschaften der Welt zwei weitere: der linke und der rechte Rand werden hinzugefügt. Gleichzeitig werden diese Grenzen nur für die rekursive Funktion der Berechnung der Weltenliste benötigt und sind vom Ergebnis nicht betroffen. Außerdem ist die Aufteilung des Segments in zwei Hälften ganzzahlig und irgendwo im Algorithmus habe ich einen Fehler gemacht, der uns die gleichen Welten auf verschiedenen Segmenten gibt. Daher ist eine Anpassung der Berechnung des Hash der Welt erforderlich.

    Schritt 1 - Setze die Welt in ein Tupel

    Die ersten beiden Parameter sind ein Bereich. Der Rest ist der gleiche wie zuvor.
    {0,999999,0,0,0,0,0,0}
    


    Schritt 2. Beschreibe die Funktion, die bestimmt, ob die Welt ihr Ziel erreicht hat
    %%Мир достиг цели?
    is_target(Wrld) ->
    	{_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld,
    	if ((X1+X2+X3)==(X4+X5+X6)) ->
    		cnt_srv ! inc,
    		cnt_srv ! {cnt, self()},
    		receive
    			X -> ok
    		end,
    		io:format("~w ~w ~w ~w ~w ~w (~w)~n", [X1,X2,X3,X4,X5,X6, X]);
    		true -> ok
    	end,
    	((X1+X2+X3)==(X4+X5+X6)). 
    


    Schritt 3. Beschreiben Sie die Funktion, die bestimmt, ob eine weitere Entwicklung für die Welt notwendig ist: Die

    Entwicklung der Welten wird in dieser Version der Berechnung nicht vorausgesetzt, da wir alle Entwicklungsmöglichkeiten sofort kennen. Das heißt, die Entwicklung hat nur einen Schritt - den allerersten, wenn der Bereich 0 - 999999 angegeben ist. Wenn der Bereich in unserer Liste aufgeführt ist, sollte es keine Entwicklung der Welt mehr geben. Die Welt ist bis auf den ersten Schritt immer eine Sackgasse.
    %%Мир - тупиковая ветвь
    is_dead(Wrld) ->
    	{St_d,En_d,_X1,_X2,_X3,_X4,_X5,_X6} = Wrld,
    	(St_d == En_d).
    


    Schritt 4. Beschreiben Sie die Verzweigungsfunktion der Welt
    %%Ветвление мира
    br(Wrld) ->
    	{St_d,En_d,X1,X2,X3,X4,X5,X6} = Wrld,
    	THalf = round((St_d + En_d) / 2),
    	if
    		(St_d == En_d) ->
    			[];
    		((En_d - St_d) == 1) -> 
                XX6 = En_d rem 10,
    			XX5 = trunc((En_d rem 100)/10),
    			XX4 = trunc((En_d rem 1000)/100),
    			XX3 = trunc((En_d rem 10000)/1000),
    			XX2 = trunc((En_d rem 100000)/10000),
    			XX1 = trunc((En_d rem 1000000)/100000),
    			[{St_d,St_d,XX1,XX2,XX3,XX4,XX5,XX6}] ++
    			[{En_d,En_d,XX1,XX2,XX3,XX4,XX5,XX6}];
    		true ->
    			br({St_d,THalf,X1,X2,X3,X4,X5,X6}) ++
    			br({THalf,En_d,X1,X2,X3,X4,X5,X6})
    	end.
    


    Schritt 5. Beschreiben Sie die Funktion des HASH der Welt
    %%хеш мира
    w2hash(Wrld) ->
    	{_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld,
    	X1*100000 + X2*10000 + X3*1000 + X4*100 + X5*10 + X6.
    

    Oder Sie können ein Tupel zusammenstellen, jedoch ohne Reichweite
    %%хеш мира
    w2hash(Wrld) ->
    	{_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld,
    	erlang:phash2({X1,X2,X3,X4,X5,X6}).
    


    Starten Sie

    %%запуск расчета
    start() ->
        register(lib_srv, spawn(?MODULE, lib, [])),
        register(cnt_srv, spawn(?MODULE, cnt, [])),	
        io:format("start~n", []),
    	%% внутри [] нужно передать начальный мир
        spawn(?MODULE, ent, [{0,999999,0,0,0,0,0,0}]).
    


    Zusammenfassung

    Dabei hat das Programm eine Liste mit Glückstickets herausgegeben, die sich als 55252 herausstellte. Converged, Prost !!!

    Рашение одной строкой
    length([ [A,B,C,D,E,F] || A <- [0,1,2,3,4,5,6,7,8,9], B<-[0,1,2,3,4,5,6,7,8,9], C<-[0,1,2,3,4,5,6,7,8,9], D <- [0,1,2,3,4,5,6,7,8,9], E  <- [0,1,2,3,4,5,6,7,8,9], F <- [0,1,2,3,4,5,6,7,8,9], (A+B+C==D+E+F)]).


    Die Zeit für die Berechnung des Ergebnisses ist unglücklich: um 16:49 Uhr begann die Berechnung und endete um 17:23 Uhr. Das sind mehr als 30 Minuten. Aber was hat das Ticketproblem gelöst und was musste überwunden werden? Das sind zunächst einmal eine Million Welten im Speicher. Anfangs habe ich keine Welt-Hashes im Repository aufgezeichnet, sondern direkt die Tupel der Welt. Wenn Sie in einer Liste mit so vielen Einträgen suchen, stellen wir bereits große Verzögerungen fest. Die Verwendung eines Hashs hat die Geschwindigkeit erhöht. Und die Gedanken in Schritt 5 bestätigten auch die Richtigkeit der Verwendung von Hashes. Grundsätzlich kann man zwar ein Tupel der Welt speichern, aber durch Löschen unwichtiger Informationen daraus. Darüber hinaus zeigt die aktuelle Architektur, dass hinsichtlich der Produktivität noch Reserven für qualitatives Wachstum bestehen, da die zu berechnenden Welten in einem Array angegeben werden und die Elemente eines Arrays von Welten auf mehreren Erlang-Knoten parallel berechnet werden können. Alle Weltberechnungen werden jedes Mal in einem neuen Prozess gestartet. Und theoretisch können Sie die maximale Anzahl von Prozessen in der virtuellen Erlang-Maschine erreichen, was zu einem Fehler führen sollte. Die Berechnung der Tickets, die in die Einschränkung "geraten" dürfen, verarbeitet den Fehler und stellt sicher, dass das Ergebnis korrekt ist.

    Aufgabe „Wolf, Ziege und Kohl“



    „Der Bauer muss den Wolf, die Ziege und den Kohl über den Fluss transportieren. Aber das Boot ist so beschaffen, dass nur ein Bauer hineinpassen kann, und damit entweder ein Wolf oder eine Ziege oder ein Kohl. Aber wenn Sie den Wolf mit der Ziege verlassen, frisst der Wolf die Ziege, und wenn Sie die Ziege mit Kohl verlassen, frisst die Ziege Kohl. Wie hat der Bauer seine Fracht transportiert? “

    Mehr über die Aufgabe sowie über zwei Möglichkeiten, sie zu lösen, finden Sie hier [7].

    Schritt 1. Geben Sie eine Beschreibung eines beliebigen Zustands der Welt in die Wagenkolonne ein.

    Dabei gilt ( r- rechts, l- links) das Ufer, an dem der Großvater, die Ziege, der Wolf, der Kohl und der vorherige Pfad ([] ist eine Liste). Wofür ist die Liste? Schließlich müssen wir wissen, wie wir zum Ergebnis gekommen sind.
    {{ded,r},{koza,r},{volk,r},{kapusta,r},[]}
    


    Schritt 2. Beschreibe die Funktion, die bestimmt, ob die Welt ihr Ziel erreicht hat
    %%Мир достиг цели?
    is_target(Wrld) ->
    	{{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld,
    	if ((DedBereg==r) and (KozaBereg==r) and (VolkBereg==r) and (KapustaBereg==r)) ->
    		cnt_srv ! inc,
    		cnt_srv ! {cnt, self()},
    		receive
    			X -> ok
    		end,
    		io:format("~w) movs=~w ~w ~n", [X, length(History),History]);
    		true -> ok
    	end,
    	((DedBereg==r) and (KozaBereg==r) and (VolkBereg==r) and (KapustaBereg==r)). 
    


    Das heißt, wenn sich alles am richtigen Ufer befindet, ist das Problem gelöst.

    Schritt 3. Beschreiben Sie die Funktion, die bestimmt, ob die Welt weiterentwickelt werden muss.
    %%Мир - тупиковая ветвь
    is_dead(Wrld) ->
    	{{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld,
    	if
    		(length(History) > 8) -> true;
    		((KozaBereg==VolkBereg)and(DedBereg/=KozaBereg)) -> true; %%волк съел козу, если дед на другом берегу
    		((KozaBereg==KapustaBereg)and(DedBereg/=KozaBereg)) -> true; %%коза съела капусту, если дед на другом берегу
    		true -> false
    	end.
    


    Wenn der Großvater zu lange syudy reitet, dann ist das eine Sackgasse.

    Wenn das Ufer bei der Ziege und dem Wolf zusammenfällt und kein Großvater in ihrer Nähe ist (Großvater auf der anderen Seite), dann frisst der Wolf die Ziege.

    Wenn das Ufer bei Ziege und Kohl zusammenfällt und kein Großvater in der Nähe ist (Großvater auf der anderen Seite), dann frisst die Ziege Kohl.

    In anderen Fällen können Sie weiterleben und auf die Zukunft hoffen.

    Schritt 4. Beschreiben Sie die Funktion, die Welt zu verzweigen.

    Hier hat es nicht sofort funktioniert, weil ich mich entschlossen habe, schlau und vereinfacht zu sein. Und Sie müssen nichts vereinfachen. Wir müssen es so machen, wie es ist - so machen wir es.

    Zuerst schreibe ich eine Funktion, die die gegenüberliegende Bank von der übergebenen Bank zurückgibt (dies wird uns unten nützlich sein):
    na_drugoi_bereg(l) -> r;
    na_drugoi_bereg(r) -> l.
    


    Wir erstellen eine Liste von Entwicklungsoptionen für die übertragene Welt. Aber vorher fügen wir die übertragene Welt der Liste hinzu - Geschichte. Schließlich müssen wir wissen, wie wir zum Ergebnis gekommen sind.
    %%Ветвление мира
    br(Wrld) ->
    	{{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld,
    	NewHistory = History ++ [{{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg}}],
    	%%каждый раз, дед однозначно переплывает с берега на берег
    	%%но перевезти с собой на другой берег он сможет только того, кто с ним сейчас на одном берегу
    	%%либо он плывет один, не взяв никого
    	%%есть коза - везем её, иначе вариант не вариант
    	if (DedBereg==KozaBereg) ->
    		Variant1 = {{ded,na_drugoi_bereg(DedBereg)},{koza,na_drugoi_bereg(KozaBereg)},{volk,VolkBereg},{kapusta,KapustaBereg},NewHistory};
    		true -> Variant1 = []
    	end,	
    	%%есть волк - везем его, иначе вариант не вариант
    	if (DedBereg==VolkBereg) ->
    		Variant2 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,na_drugoi_bereg(VolkBereg)},{kapusta,KapustaBereg},NewHistory};
    		true -> Variant2 = []
    	end,	
    	%%есть капуста - везем её, иначе вариант не вариант
    	if (DedBereg==KapustaBereg) ->
    		Variant3 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,VolkBereg},{kapusta,na_drugoi_bereg(KapustaBereg)},NewHistory};
    		true -> Variant3 = []
    	end,	
    	%%никого не везем - едем порожняком - вполне себе вариант
    	Variant4 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},NewHistory},
    	%%при сложении списков получается список
    	[Variant1]++[Variant2]++[Variant3]++[Variant4].
    


    Schritt 5. Beschreiben Sie die Funktion zur Berechnung des HASH der

    Welt. Der Standard-HASH der Welt ist für uns durchaus geeignet.
    %%хеш мира
    w2hash(Wrld) ->
    	erlang:phash2(Wrld).
    


    Und wenn wir nur den Hash der resultierenden Welt berechnen? Ja, er wird im Allgemeinen nicht benötigt. Das Ergebnis wissen wir bereits - alles ist am richtigen Ufer. Der Weg ist uns wichtig - der Wert des Feldes der Geschichte. Daher macht es keinen Sinn, etwas daraus zu entfernen, bevor der Hash der Welt berechnet wird.

    Starten Sie
    %%запуск расчета
    start() ->
        register(lib_srv, spawn(?MODULE, lib, [])),
        register(cnt_srv, spawn(?MODULE, cnt, [])),	
        io:format("start~n", []),
    	%% внутри [] нужно передать начальный мир
        spawn(?MODULE, ent, [{{ded,l},{koza,l},{volk,l},{kapusta,l},[]}]).
    


    Analyse des Ergebnisses

    Bei einer bestimmten Anzahl von Bewegungen des Großvaters über den Fluss gibt es mehrere Möglichkeiten, das Problem zu lösen. Unter ihnen sind die kürzesten Entscheidungen in 7 Sätzen. Es gibt zwei solche Lösungen, wie sie im Artikel [ 7 ] geschrieben sind.

    1) movs=7 [
    {{ded,l},{koza,l},{volk,l},{kapusta,l}}, - все на левом берегу
    {{ded,r},{koza,r},{volk,l},{kapusta,l}}, - перевез козу на правый берег
    {{ded,l},{koza,r},{volk,l},{kapusta,l}}, - вернулся на левый берег
    {{ded,r},{koza,r},{volk,r},{kapusta,l}}, - перевез волка на правый берег
    {{ded,l},{koza,l},{volk,r},{kapusta,l}}, - вернулся на левый берег вместе с козой
    {{ded,r},{koza,l},{volk,r},{kapusta,r}}, - перевез капусту на правый берег
    {{ded,l},{koza,l},{volk,r},{kapusta,r}}] - вернулся на левый берег за козой, чтобы перевезти ее на правый берег
    


    5) movs=7 [
    {{ded,l},{koza,l},{volk,l},{kapusta,l}}, - все на левом берегу
    {{ded,r},{koza,r},{volk,l},{kapusta,l}}, - перевез козу на правый берег
    {{ded,l},{koza,r},{volk,l},{kapusta,l}}, - вернулся на левый берег
    {{ded,r},{koza,r},{volk,l},{kapusta,r}}, - перевез капусту на правый берег
    {{ded,l},{koza,l},{volk,l},{kapusta,r}}, - вернулся на левый берег вместе с козой
    {{ded,r},{koza,l},{volk,r},{kapusta,r}}, - перевез волка на правый берег
    {{ded,l},{koza,l},{volk,r},{kapusta,r}}] - вернулся на левый берег за козой, чтобы перевезти ее на правый берег
    


    Andere Optionen erfordern mehr Bewegungen, aber es ist offensichtlich, dass diese Körperbewegungen bedeutungslos sind:
    2) movs=9 [
    {{ded,l},{koza,l},{volk,l},{kapusta,l}}, - все на левом берегу
    {{ded,r},{koza,r},{volk,l},{kapusta,l}}, - отвез козу на правый берег
    {{ded,l},{koza,r},{volk,l},{kapusta,l}}, - вернулся на левый берег
    {{ded,r},{koza,r},{volk,r},{kapusta,l}}, - отвез волка на правый берег
    {{ded,l},{koza,l},{volk,r},{kapusta,l}}, - вернулся на левый вместе с козой
    {{ded,r},{koza,l},{volk,r},{kapusta,r}}, - отвез капусту на правый берег
    {{ded,l},{koza,l},{volk,r},{kapusta,l}}, - отвез капусту обратно на левый
    {{ded,r},{koza,l},{volk,r},{kapusta,r}}, - отвез еще раз капусту на правый берег
    {{ded,l},{koza,l},{volk,r},{kapusta,r}}] - вернулся за козой
    


    Ein Moment des Humors


    Bild - Illustration der Methode des Baums der Zeiten


    Amerikanische Version des Problems um den Wolf, die Ziege und den Kohl.


    Schlussfolgerungen


    Zusammenfassend lässt sich sagen, dass die Methode tatsächlich für Berechnungen verwendet werden kann und die Sprache erlang als Werkzeug alle erforderlichen Fähigkeiten zur praktischen Umsetzung der Methode besitzt. Es wurde eine Technik und ein Framework entwickelt, um die Programmierung von Berechnungen mit dieser Methode zu vereinfachen.

    Kritik an der Methode.
    Die Methode ist mathematisch unwissenschaftlich. Zur Lösung von Problemen, beispielsweise bei Produktionsbeladung, können Massenservice-Theorien usw. angewendet werden. Die Essenz der Methode ist die Aufzählung von Optionen (die "Brute Force" -Methode), die bedeutungslos große Rechenressourcen verbraucht und möglicherweise keine Lösung findet, wenn der Rechenbereich schlecht begrenzt ist. Wikipedia betrachtet Brute Force als eine Methode zur Lösung mathematischer Probleme .

    Weiterentwicklung
    Cluster-Computing. Experimentieren mit Erlang Pool.

    Entwicklung eines Frameworks Nr. 2 zur Lösung einer anderen Klasse von Problemen, wenn zuerst ein Baum gebaut wird, und dann Lösungen dafür. Zum Beispiel AI für die Implementierung von Tic Tac Toe. Für sie wird aus allen möglichen Kombinationen im Spiel ein Baum gebaut, um zu gewinnen. Wenn die Spielrunde beginnt, findet AI die Welt im Baum, wählt einen der Entwicklungszweige aus, der die Welt zu einer siegreichen Zielwelt führt und den entsprechenden Schritt unternimmt.

    Liste der verwendeten Quellen


    1. Zeitreise und Programmierung - habrahabr.ru/post/150300
    2. Zeitreise und Programmierung 2: Paradoxe - habrahabr.ru/post/178959
    3. Vasiliy Golovachev - Scharfrichter der Zeiten
    4. qt-project.org
    5. Der Anfang Arbeit mit der Erlang - rsdn.ru/article/erlang/GettingStartedWithErlang.xml
    6. www.erlang.org
    7. Aufgabe "Wolf, Ziege und Kohl" - suhin.narod.ru/mat4.htm
    8. der Constraint - Programmierung - en.wikipedia .org / wiki / Constraint_programming
    9. Programmieren in Constraints - de.wikipedia.org/wiki/Programmieren in Constraints
    10. Professor Mats Karlsson - Programmieren in Constraints.Open Video Lecture
    11. Die Methode der Zweige und Grenzen - de.wikipedia.org/wiki/Metod_Branches_and Borders

    PS. Ich suche interessante Aufgaben!
    - Turm von Hanoi
    - Sudoku
    - Euler Pferd

    Jetzt auch beliebt: