Clever Geek Handbook

時間のツリーのプログラミング





はじめに



TimeCoderの記事「Time Travel and Programming」[ 1、2 ]を読んだ後、分岐世界の実装に関連するプログラミングのささやかな実践的研究を思い出しました。 私の同僚が私に興味深い問題を投げかけたが、私はまだそれを解決することができませんでした。 タスクは、本番環境でマシンをロードする方法です。 単純な列挙が必要であることはプログラマーにとっても明らかではありませんでしたが、計算アルゴリズムを提供する適切なデータ構造を思い付くことができませんでした。 タスクは実世界からのものであるため、タスクの計算に必要な部分でプログラムに実世界を実装しようとすることにしました。 毎回、さらなる計算では、2つのアクションから選択がありました。それぞれに異なるソリューションを持つ「2つの新しい世界の作成」がありました。 さらに、各世界は独自の方法を開発しました。



カットの下で、アイデアがどのように発展し、アーランが私をどのように助けたかを説明します。 実践は真実の基準です！



内容



用語-時間の木

最初の問題

すでに行われたことを思い出してください

世界の収束

方法論

ステップ1.世界のあらゆる状態の記述をタプルに入れる

ステップ2.世界が目標に到達したかどうかを判断する関数を説明する

ステップ3.世界がさらに発展する必要があるかどうかを決定する機能を説明します。

ステップ4.世界の分岐機能を説明する

ステップ5.世界のHASH計算関数を説明する

その他の機能

バージョン1フレームワーク

問題解決のためのフレームワーク№1の適用

異なる紙片で120ルーブルを発行するためのオプションの計算

ラッキーチケットの計算

ラッキーチケットの計算、試行番号2

タスク「オオカミ、ヤギ、キャベツ」

ユーモアの瞬間

結論

使用されたソースのリスト



用語-時間の木



ゴロバチョフは、そのような世界史の発展の表象を、時系列の木またはフラクタルと呼んでいます[3]。 さらに、このアプローチを使用した結果検索メソッドを「Tree of Timesメソッド」と呼びます。



世界は、 世界のプロパティとその状態を決定する意味のリストです。



問題の解決-Trees of Timesメソッドによって問題を解決します。結果、または取得したい世界の特定のプロパティの値を事前に知っています。 つまり、結果はわかっていますが、それを取得する方法は不明です。 問題の解決策は道を見つけることです。



最初の世界は基準点であり、そこから問題を解決する旅が始まります。



対象の世界とは、問題の解決に努める世界（またはその状態）です。



世界の発展-初期の世界を発展させ、目標の世界を達成するよう努めています。



行き止まりの世界は行き止まりの枝ではなく、行き止まりの世界です。 これは、さらなる発展が目標世界につながらない世界です。



最初の問題



方法論をテストするために、特定の金額までの紙幣の選択やラッキーチケットの検索などのタスクを選択しました。 それぞれのケースで、彼は再帰的な検索関数の結果を書きました。 世界のインスタンスとその状態全体を格納するクラスを作成しました。 世界のコピーを作成する機会、私はまだなっていない。 タスクは単純で、入力パラメーターは控えめな世界を完全に記述しています。 しかし、このような単純なタスクであっても、このアプローチの欠点はすべて明らかになりました。 開発のブランチは非常に迅速に拡大します。



夢の中で、原子炉とその中の粒子の核分裂についての類推が私に来ました。 爆発の結果として、分裂と連鎖反応があります。 爆発を防ぐために、分割プロセスが制御されます。 世界の新しいブランチを作成するプロセスを制御する必要があり、非常に厳しいことが明らかになりました。世界が望ましい結果をもたらさない場合、それを破壊し、世界がその開発目標に到達した場合、結果を導き出します。 結果の結論は、結果を達成する方法は、あまりにも高価な世界（10ルーブル紙幣で1000ルーブルの発行。別の問題は、いくつかの同一の結果の発見であった。



そのため、Tree of Timesメソッドを使用した計算では、次の問題を解決する必要があります。







当分の間「Tree of Timesメソッド」を使用して結果を計算する長年の歴史は、「私の机に」横たわっていました。 すべてのコンピューティングの問題が解決されたわけではないからです。 はい、そして、私がよく知っているプログラミング言語とは異なる、新しい並列コンピューティングを適用する時が来たことは明らかです。 しかし、簡単な解決策はありませんでした。



時間が経つにつれて、プログラミングの分野の技術は発展しています。 メガヘルツを上げることは無限に不可能であることが明らかになりました。 計算を並列化する必要があります。 そして、そのような機会が現れ始め、言語の並列処理のサポートが簡素化され始めました。



しかし、世界のクローンはどうですか？ デッドセンターシフトのTimeCoder記事のケース。 世界の発展の枝を分離するだけでなく、それらを結び付けることができなければなりません。



新しい新しいアイデアとツールを武器に、時間の木の探索に戻ることにしました。



すでに行われたことを思い出してください



チャレンジはラッキーチケットです。 最初の3桁の合計が残りの合計と等しい場合、チケットはラッキーと見なされます。

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);


結果を待ちませんでした。 長い間。 したがって、コードの一部を削除しました。 
 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); }


結果は次のとおりです。 

 000000 200002 100001 200002 200002 100001 200002 200002 200002


アルゴリズムは最適化されていません。 特に考えられていません。 そして、対応する結果は倍になります。



仕事はお金を交換することです。 1000、500、100、50、10ルーブルの紙幣があるとします。 発行のオプションを計算する必要があります。

Erlangソリューション[5,6]：ファイル<i> we01.erl </ i>： 
 -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.


このファイルをErlangで実行する方法は？
  1. Erlangを起動します。 

     erl


  2. モジュールをコンパイルします。 

     c(we01).


  3. 120ルーブルの発行の計算を開始します。 

     we01:sum_money(120).


  4. 結果： 

     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 ^ | +----




明らかに、重複（同一の世界）をどうにかして無視する必要があります。 適切なプログラミングのために訓練された頭脳は、アルゴリズムが最適化されないように、最適化、最適化、最適化の方法をすぐに考え始めます...実際、これは非常に単純な例ですが、ここでも最適化を考えるのは難しくなります。 そして、より複雑な世界では何が起こるでしょうか？ 一般的に、そのような機会があれば、明らかに余計な世界を作り出す必要はありません。他のすべての場合には、世界を収束させる方法を発明する必要があります。



世界の収束



このようなものがあるかどうかを確認してみましょう。 ある場合は、他に何もしません（子ワールドを作成しないでください）。

QT、タスクも同じです-チケット： 
 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); }


私たちがどんな世界にいるのかを分析するために、見つかった場合と見つからなかった場合の結論について話し合います。 すべての条件で、計算量を制限するには、<10を<2に置き換えます。 始めます。 結果：

結果 
 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"


合計64行、つまり2 ^ 6行があります。 全体として、アルゴリズムは約155ミリ秒の高速で動作します。 QtConcurectをオフハンドで使用して並列化することはできませんでした。



しかし、Erlangはどうですか？



タスクは同じです-チケットをソートします。 しかし、Erlangにはグローバル変数はありません。

リポジトリとしてプロセスがあります。 
 %    ( ,   ) 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.


仕組み
サーバーを起動するには、 world_server_start()



関数がworld_server_start()



ます。 新しいスレッドでworld_server関数を実行し、 ws



という名前に関連付けます。 関数はそれ自体を再帰的に呼び出し、パラメーターとしてワールドのリストを渡します。 最初に、 []



が渡されます。つまり、空の配列です。 作業中、関数は常に他のプロセスからのメッセージを待ちます：

  • メッセージを受信した場合- finished



    アトム、関数は停止メッセージを表示し、それ自体を再帰的に呼び出さないため、サーバーを停止します。
  • メッセージが受信された場合-atom list、ワールドのリストが表示され、作業が続行されます（デバッグに使用されます）
  • タプル{new_world, PID, New_world, Par}



    、これはサーバーがリストにそのような世界があるかどうか尋ねられることを意味しますか？ ワールドがある場合、メッセージworld_exist



    またはworld_new



    world_exist



    に返され、リストに新しいワールドを追加して関数がさらに実行されます（すでにワールドがない場合）





一度機能すると、私たちは本質的に世界に行き着きます。 そしてまず、存在を確認します-ワールドリポジトリサーバーにリクエストを送信します。 答えがworld_exist



場合、それ以上作業しません（return ok



）。 それ以外の場合は、世界に関する情報を表示します（ターゲットの場合はアスタリスク付き-チケットは幸せです）。 



 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.


Erlangの形の新しいテクノロジーから私たちは何になりましたか？ これまでのところ何もありません：



どうする？ 方法論が必要です！ シンプルで、一歩一歩、学生でも理解できる。



方法論







実験の後、コードの特定の部分はどの計算でも同じであり、条件のみが変わるという結論に達しました。 したがって、タスクとそのプログラミングを設定するとき、再帰、並列化、およびその他の技術的なトリックから完全に離れ、計算の条件の設定に集中できます。 つまり、計算用の何らかのフレームワークを作成します。 アーラン方法論では、これは動作と呼ばれます。 一番下の行は、たとえばサーバーを実装するために、その動作を実装する必要があるということです：起動時、停止時などにどうするか



それは何を与えますか？ 各動作は1つの単純で単純な機能です。 結果が入力データのみに依存する純粋な関数。 他とは独立してチェックできます。



したがって、フレームワークバージョン1が登場しました。 問題を解決するには、手順を実行する必要があります



ステップ1.世界のあらゆる状態の記述をタプルに入れる


Trees of Timeのプログラミング計算における重要なポイントは、世界の記述を保存する方法に関する合意です。 フィクションでは「世界のマトリックス」と呼ばれるもの。 世界の記述には、現在の世界の状態に関する情報が含まれていますが、必要なものだけが含まれています。



Trees of Timeに関する以前の研究では、クラス、フィールドを使用しようとしましたが、個々のタスクごとにプログラミングを行うと、多くのコードを実行せざるを得なくなりました。 したがって、世界をできるだけ簡単に記述する必要があります。



世界記述協定：世界は1つのタプルで記述されなければなりません。



タプルは、制限された長さの値のセットです。 タプルは中括弧に制限されており、タプルの要素はコンマで互いに区切られています。 タプルは互いにネストできます。



例1.ラッキーチケットのオプションを計算するときの最初の瞬間の世界の状態を記述するタプル。 

 {0,0,0,0,0,0}


各数字は、チケット番号の個別の数字です。



時間は特定の世界にとって重要ではないため、「最初の瞬間」ではなく「世界の初期状態で」と書く方が正しいでしょう。 重要なのは世界の状態だけです。 理解に慣れている形式の時間が計算にとって重要である場合、タプルの別の値として追加されます。



例2.世界の状態を記述するタプルで、 1x100rと2x10rの形式で120ルーブルを発行する方法を見つけました。 1000、500、100、50、10の5種類の紙幣があります。したがって、世界には5つのパラメーターがあります。 彼らは大きいものから小さいものへと続くことに決めました。つまり、最初の数字は1000ルーブルなどの数字です。 

 {0,0,1,0,2}




ステップ2.世界が目標に到達したかどうかを判断する関数を説明する


関数はパラメーターとしてワールドに渡されます。 彼女の仕事は、彼が標的にされているかどうかを判断することです。 その場合、結果を出力してtrue



を返しtrue



。 それ以外の場合はfalse



です。 世界がその目標に到達した場合、フレームワークは明らかにそれをさらに開発する必要はありません。 組み合わせの問題における世界のさらなる発展は、他の解決策につながる可能性があります。



ステップ3.世界がさらに発展する必要があるかどうかを決定する機能を説明します。


関数はパラメーターとしてワールドに渡されます。 彼女の仕事は、さらに開発するかどうかを決定することです。 世界のさらなる発展が目標につながることができない場合、それをさらに発展させることは意味がありません。 行き止まりのブランチ。 開発が必要な場合は、 true



返しtrue



。 それ以外の場合はfalse



です。 同時に、世界のさらなる発展が行き止まりである場合、これは世界を標的にできないという意味ではありません。



ステップ4.世界の分岐機能を説明する


世界の発展はさまざまな方向に進むことができます。 関数はパラメーターとしてワールドに渡されます。 これに応じて、この世界から発展できる世界のリストが発行されます。



ステップ5.世界のHASH計算関数を説明する


デフォルトでは、ワールドHASH計算関数は次のとおりです。 
 %%  w2hash(Wrld) -> erlang:phash2(Wrld).


標準erlang:phash2



関数erlang:phash2



、ハッシュ（送信されたタプルからの数）をerlang:phash2



。 しかし、ある世界と別の世界を正確に対応させることは必ずしも必要ではありません。 これは記事[1、2]に書かれていますが、最終的には、どのような中間的な決定が下されても、1つの結果が得られ、開発のブランチが収束するということです。 世界は「原子まで」収束するのではなく、問題を解決するという文脈で収束します。 車で仕事をすることが仕事の場合は、さまざまな道を行くことができますが、12時に会議に出席します。 もちろん、違いは車の走行距離にありますが、この瞬間は私たちにとって重要ではありません。



フレームワーク番号1での世界の収束は、すでに作成された世界のリポジトリを通じて実装されます。 むしろ、これらの世界のハッシュ番号。 また、ブランチの開発中に入力した世界がリポジトリに既に存在する場合、世界のさらなる開発は行われません。 実際、世界の発展の2つのパスが同じ結果になり、同じ方法でさらに進んだため、世界は収束します。 したがって、ワールドのパラメーターのいずれかが結果に影響しない場合、このパラメーターがtuple->ハッシュ番号の変換に関与しないように、ワールドのハッシュを計算する機能を調整する必要があります。



その他の機能


列挙、ワールド、ワールドの収束などの機能は、どのタスクでも同じです。 それらはフレームワークに含まれ、ユーザーはそれらを変更/理解する必要はありません。 そして、方法論を厳密に守れば、世界のルールを定義する機能を変更することなく、フレームワークを並列コンピューティングに関して改善できます。



バージョン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, [[]]).




問題解決のためのフレームワーク№1の適用





異なる紙片で120ルーブルを発行するためのオプションの計算






ステップ1-タプルに世界を置く



世界は5桁で記述されます。 

 {0,0,0,0,0}




ステップ2.世界が目標に到達したかどうかを判断する関数を説明する 
 %%  ? 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.


Erlang構文に関する小さなメモ。 最初の操作は割り当てではなく、一致です。 Wrld



変数にWrld



5つの要素をWrld



タプルがWrld



ます。 操作が実行されると、タプル内の要素の値が変数X1000, X500, X100, X50, X10



割り当てられます。 Erlangでの試合の詳細については、ご自身でお読みください。 または、タプルから値を取得する方法などの構文をそのまま受け入れます。



ステップ3.世界がさらに発展する必要があるかどうかを決定する機能を説明します。 
 %% -   is_dead(Wrld) -> {X1000,X500,X100,X50,X10} = Wrld, (X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)>120.




ステップ4.世界の分岐機能を説明する 
 %%  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} ].




計算開始 
 %%  start() -> register(lib_srv, spawn(?MODULE, lib, [])), io:format("start~n", []), %%  []     spawn(?MODULE, ent, [{0,0,0,0,0}]).




その結果、次のものを受け取りました。 
 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




ラッキーチケットの計算






ステップ1-タプルに世界を置く



世界は6桁で記述されます。 

 {0,0,0,0,0,0}




ステップ2.世界が目標に到達したかどうかを判断する関数を説明する 
 %%  ? 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)).




ステップ3.世界がさらに発展する必要があるかどうかを決定する機能を説明します。 
 %% -   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.




ステップ4.世界の分岐機能を説明する 
 %%  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} ].




ハッピーチケットの数を計算するために、見つかったワールドの数を格納、増加し、肯定的な結果を与える別のサーバーを作成します。 
 %%-  cnt() -> cnt(0). cnt(N) -> receive inc -> cnt(N+1); {cnt,Pid} -> Pid ! N, cnt(N) end.




計算を開始すると、それも開始します。 
 %%  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}]).




ただし、この方法でルールを設定すると、結果が出るまで長時間待たなければなりません。 非常に多くのプロセスが作成されるため、Erlangノードは多くのプロセスの処理を停止し、新しいプロセスの作成を停止します。 そして、この問題の解決策を（試してみて）見つけなければならなかったので、これは良いことです。



明らかに、世界の分岐は最良の方法で設定されておらず、同じ世界が複数回作成され、チェックが絶えず進行しており、世界がすでに存在していることがわかります。 これは、このような要求の厳しいタスクでは、まだ脳を使用する必要があることを示唆しています。



ラッキーチケットの計算、試行番号2






幸せなチケットの問題を解決することは非常に有用であることが判明しました。 解決の過程で、各ステップで多数の非常に重要なニュアンスが見つかり、世界を処理するメインサイクルには調整が必要でした。 また、ステップ5（本来はなかった）の必要性も明らかになりました。



チケットの問題を解決するための以前の試みは、私たちが効果的に世界を分岐させなかったことを示しており、それは多くのテイクをもたらしました。 しかし、初期状態から直ちに世界の発展のためのすべてのオプションを計算することに問題はありません。 しかし、Erlangがあるので、セグメントを半分に分割して再帰的に実行します。 セグメントは0から999999までで、範囲の境界が一致するまで分割します。 したがって、世界のプロパティはさらに2つになります。左右の境界線が追加されます。 同時に、これらの境界は、ワールドのリストを計算する再帰的な機能にのみ必要であり、結果の影響を受けません。 さらに、セグメントの半分の分割は整数であり、アルゴリズムのどこかで、異なるセグメントで同じ世界を提供するミスを犯しました。 したがって、世界のハッシュの計算を調整する必要があります。



ステップ1-タプルに世界を置く



最初の2つのパラメーターは範囲です。 残りは以前と同じです。 
 {0,999999,0,0,0,0,0,0}




ステップ2.世界が目標に到達したかどうかを判断する関数を説明する 
 %%  ? 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)).




ステップ3.世界がさらに発展する必要があるかどうかを決定する機能を説明します。



このバージョンの計算での世界の開発は想定されていません。なぜなら、すべての開発オプションがすぐにわかるからです。 つまり、開発には1つのステップしかありません-範囲0〜999999が指定されている場合の最初のステップです。 世界は、最初の一歩を除いて、常に行き止まりです。 
 %% -   is_dead(Wrld) -> {St_d,En_d,_X1,_X2,_X3,_X4,_X5,_X6} = Wrld, (St_d == En_d).




ステップ4.世界の分岐機能を説明する 
 %%  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.




ステップ5.世界のHASHの機能を説明する 
 %%  w2hash(Wrld) -> {_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld, X1*100000 + X2*10000 + X3*1000 + X4*100 + X5*10 + X6.


または、タプルを組み立てることができますが、範囲はありません 
 %%  w2hash(Wrld) -> {_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld, erlang:phash2({X1,X2,X3,X4,X5,X6}).




打ち上げ 



 %%  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}]).




まとめ



実行の過程で、プログラムはラッキーチケットのリストを発行しました。これは55252であることが判明しました。



単一行の改行 
 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)]).




結果を計算する時間は幸せではありません。16：49に計算を開始し、17：23に終了しました。それは30分以上です。しかし、チケットの問題の解決策は何であり、何を克服する必要があったのでしょうか？まず第一に、これは100万のストレージの世界です。最初は、リポジトリにワールドハッシュを記録しませんでしたが、ワールドのタプルを直接記録しました。エントリが非常に多いリストを検索すると、すでに大きな遅延に直面し始めています。ハッシュを使用すると速度が向上します。また、ステップ5の考えから、ハッシュの使用が正しいことが確認されました。原則として、世界のタプルを保存できますが、そこから重要でない情報を削除します。さらに、現在のアーキテクチャは、計算が必要な世界は配列で与えられ、世界の配列の要素は複数のアーランノードで並列に計算できるため、生産性の観点から質的成長の余地があることを示しています。すべてのワールドの計算は、新しいプロセスで毎回起動されます。そして理論的には、エラーにつながるはずのErlang仮想マシンで最大数のプロセスを達成できます。制限の「実行」を許可されたチケットの計算、エラーの処理、および結果が正しいことの確認。



タスク「オオカミ、ヤギ、キャベツ」






「農民はオオカミ、ヤギ、キャベツを川を渡って運ぶ必要があります。しかし、ボートは小作人だけがそれに合うことができて、それで1匹のオオカミ、または1匹のヤギ、または1匹のキャベツです。しかし、オオカミをヤギと一緒に離れると、オオカミはヤギを食べ、キャベツと一緒にヤギを離れると、ヤギはキャベツを食べます。農民はどのように彼の貨物を輸送したのですか？」



タスクの詳細と、それを解決するための2つのオプションについては、ここで見つけることができます [7]。



ステップ1.世界のあらゆる状態の説明をモーターカードに入力します



場所（r



-右、l



-左）-祖父、ヤギ、オオカミ、キャベツ、および前のパス（[]はリスト）の海岸。リストは何ですか？結局のところ、結果に到達した方法を知る必要があります。
 {{ded,r},{koza,r},{volk,r},{kapusta,r},[]}




ステップ2.世界が目標に到達したかどうかを判断する関数を説明する 
 %%  ? 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)).




つまり、すべてが適切な銀行にあれば、問題は解決します。



ステップ3.世界がさらに発展する必要があるかどうかを決定する機能を説明します。 
 %% -   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.




祖父があまりにも長い間走る場合、これは行き止まりです。



ヤギとオオカミの海岸が一致し、近くに祖父がいない場合（反対側の祖父）、オオカミはヤギを食べます。



ヤギとキャベツの海岸が一致し、それらの近くに祖父がいない場合（反対側の祖父）、ヤギはキャベツを食べます。



それ以外の場合、あなたは生き続け、将来を期待することができます。



ステップ4.世界を分岐させる機能を説明する



ここでは、スマートで単純化することに決めたため、すぐには機能しませんでした。そして、何も単純化する必要はありません。そのまま行う必要があります。



最初に、渡された銀行とは反対の銀行を返す関数を作成します（以下で役立ちます）。
 na_drugoi_bereg(l) -> r; na_drugoi_bereg(r) -> l.




移管された世界の開発オプションのリストを作成しています。しかしその前に、移された世界をリストに追加します-歴史。結局のところ、結果に到達した方法を知る必要があります。
 %%  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].




ステップ5.



世界のHASHを計算する機能を説明する世界の標準HASHは、私たちに非常に適しています。
 %%  w2hash(Wrld) -> erlang:phash2(Wrld).




そして、結果の世界のハッシュを計算するだけなら？はい、彼は一般に必要ありません。私たちがすでに知っている結果-すべてが正しい銀行にあります。パスは私たちにとって重要です-履歴の配列の値。したがって、世界のハッシュを計算する前に、そこから何かを削除しても意味がありません。



打ち上げ 
 %%  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},[]}]).




結果の分析



川を渡る一定数の祖父の動きで、問題を解決するためのいくつかのオプションがあります。その中で、最も短い決定は7つの動きにあります。記事[ 7 ]に書かれているように、このようなソリューションが2つあります。 



 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}}] -      ,




他のオプションではより多くの動きが必要ですが、これらの体の動きが無意味であることは明らかです。
 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}}] -




ユーモアの瞬間



写真-Trees of Timesメソッドの図。





オオカミ、ヤギ、キャベツに関する問題のアメリカ版。





結論



まとめると、このメソッドは実際に計算に使用でき、ツールとしてのアーラン言語は、メソッドを実際に実装するために必要なすべての機能を提供していると言えます。この方法による計算のプログラミングを簡素化するための手法とフレームワークが開発されました。



メソッドの批判。

この方法は、数学的な観点からは非科学的です。たとえば、生産ロードの問題を解決するために、マスサービス理論などを適用できます。このメソッドの本質はオプションの列挙（「ブルートフォース」メソッド）であり、これは無意味に膨大な計算リソースを消費し、計算ドメインの制限が不十分な場合には解決策を見つけられない可能性があります。しかし、ウィキペディアはブルートフォースを数学的問題を解決する方法と考えています。



さらなる開発

クラスターコンピューティング。アーランプールの実験。



ツリーが最初に構築されたときに別のクラスの問題を解決するためのフレームワークNo. 2の開発、およびそのソリューションが見つかりました。たとえば、三目並べの実装のためのAI。彼女にとっては、勝つためのゲーム内の可能な組み合わせからツリーが構築されます。ゲームのターンが始まると、AIはツリー内の世界を見つけ、開発ブランチの1つを選択します。これにより、世界を勝利のターゲット世界に導き、適切なステップを踏みます。



使用されたソースのリスト



1.タイムトラベルとプログラミング-habrahabr.ru/post/150300

2.タイムトラベルとプログラミング2：パラドックス-habrahabr.ru/post/178959

3. Vasiliy Golovachev-実行者

4. qt-project.org

5.開始-アーランと仕事rsdn.ru/article/erlang/GettingStartedWithErlang.xml

6. www.erlang.org

7.タスク「オオカミ、ヤギとキャベツ」 - suhin.narod.ru/mat4.htm

制約プログラミングの8 - en.wikipedia .org / wiki / Constraint_programming

9. 制約でのプログラミング-en.wikipedia.org/wiki/Programming in Constraints

10.教授Mats Karlsson-制約でのプログラミング。公開ビデオ講義

11.枝とボーダーの方法-ja.wikipedia.org/wiki/Metod



PS。面白いタスクを探しています！

-ハノイの塔

-数独

- オイラー馬


More articles:


All Articles