Geekly Articles each Day

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



はじめに


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。面癜いタスクを探しおいたす
-ハノむの塔
-数独
- オむラヌ銬

Source: https://habr.com/ru/post/J217031/

More articles:


All Articles