ねえ、フルスタック、スキルを訓練しましょう。 脳回を練ることをお勧めします。私には思えますが、これを別の異常なパラダイムを使用して行うのは興味深いです。 ほとんどの開発者は、アルゴリズム化の高度なスキルを備えています。タスクは、目的の結論に至る一連の動きを検討するために、接続する必要があるレンガに変わります。
ここで、一週間前、プロローグが言及されましたが、プロローグ言語は問題を解決するのに適していると答えたいと思います。 私はすでにこのトピックに触れ、アルゴリズムのタスクを備えたサイトから利用可能なランダムタスクにいくつかのソリューションをもたらしました。複雑なソリューションは宣言型言語で利用可能であり、遅くは動作しないことを示したいと思いますそれほど遅くない）。
次の問題を提示するまでに長い時間がかかりました。最初の解決策がすでに受け取られているので、問題を実証し、それがどれほど遅いかを調べます。
プロローグは、多くの解決策を示し、それを制限することもできますが、反復する方法を提供しない演programプログラムを作成できるという点で興味深いです。
アルゴリズムが開発されます ソルバー 通訳。
したがって、タスクは次のとおりです。
- 雨水を閉じ込めるii
2D標高マップ内の各単位セルの高さを表す正の整数のmxnマトリックスが与えられた場合、降雨後にトラップできる水の量を計算します。
注：
mとnは両方とも110未満です。各ユニットセルの高さは0より大きく、20,000未満です。
例：
次の3x6の高さマップがある場合：
[
[1,4,3,1,3,2]、
[3,2,1,3,2,4]、
[2,3,3,2,3,1]
]
戻る4。
解決策を策定するための長い試みの後、私はこの言葉遣いに来ました：
各セルに最大量の水を注ぐ必要がありますが、水はこぼれません 。 各セルに一定量の水を注ぐことをお勧めしますが、可能な限りすべての水が最大値を下回るようにします。
次のようになりました。
reptest(X0,X2):- flatten(X0,FX0), sort(0,>,FX0,Vals), repdown(X0,Vals,X0,X2),!.
この述語は入力リスト（マトリックス）を受け取り、それを解に、有効な答えになる他の値が存在するマトリックスに変換します。 次に、別の述部がこれら2つのリストを要素ごとに取り、合計金額を見つけます。
repdown(X0,Vals,X,X1):- puts(Vals,X0,X1), X\=X1, balns(X0,X1),!. repdown(_,_,X,X).
この述部は解決策の1つを取り、「通常」満たされているかどうかを確認します。問題の条件を満たしている場合、これが解決策です。
これは「生成および検証」メソッドです。値がそのようなセットにあると言い、何らかのセットの終了条件をチェックして、このセットのすべての要素を修正します。
したがって、次に、puts（Vals、X0、X1）述語を使用して新しいソリューションを取得します。ここでは、このマトリックスにあるすべての可能な高さのリストがあり、そこから各セルの可能な高さを選択します。 入力テストの分析によれば、このタスクでは、セルの周りに大量の水を挿入して「頭で」溢れ出せば、セル全体を埋めることができることがわかりました。
全体的に、この述語はより複雑に見え、1つの3x3正方形を構成するトリプルの行を処理する必要があります（はい、Prologには配列はありませんが、入力データの説明のように見えますが、宣言型プログラミングで使用します。 、先頭と末尾のリストのみがあるため、入力仕様に一致するテンプレートを記述してください）。
puts(_,[],[]). puts(_,[X],[X]). puts(_,[X,Z],[X,Z]). puts(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,sel_biger(R2,V,R21),puts(V,[R21,R3|T],St). puts(V,[R1,R2,R3|T],[R1|St]) :- puts(V,R2,R21),puts(V,[R21,R3|T],St).
これは、マトリックスのバイパスを表現する方法です。最初の3行（およびそれ以上）を取得し、そこから左から右に要素のトリプルを選択することもできます。8つの隣接するセルの間には、1つの[板谷] [うたや]セルがあります sel_biger（R2、V、R21）の助けを借りて、このセルの新しい意味が作られました。
この値は現在のセルに設定でき、可能な高さの1つであり、リストも降順で並べ替えられるため、最初のセルは利用可能な最高の高さになり、その後は次のようになります。
sel_biger(C,[H|_],H):-H>=C. sel_biger(C,[_|T],X):-sel_biger(C,T,X).
これは「意思決定ジェネレーター」の説明であり、各ポイントで任意に埋められた高さから取得したマトリックスが、必要な答えに類似していることを確認する必要があります。
そして、水が穴に落ち着くような状態を見つけることが必要でした、私はそれをこのようにしようとします：
正方形の9つの値は3 x 3であり、中心には常に入力マップと矛盾しない高さが必要です。したがって、元々これらのセルにあったバランスの変化が得られず、高さがあったとしても、その上にセルがあってはなりませんすべてが水であふれるので、ここで、高いセルはそのままであるか、より高い値に置き換えられるべきであると言えますが、それはすべての隣人、つまり 現在のセルから左、右、上から下のセルは、セル内にさらに水がある場合、それが周りに上昇した場合にのみ、それを超えるか等しいはずです...
%% balns([],[]). balns([_],[_]). balns([_,_],[_,_]). balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :- blevel(B1,B2,B3,R1,R2,R3), balns([B2,B3|Tb],[R2,R3|T]). %% , 33 blevel([],[],[],[],[],[]). blevel([_],[_],[_],[_],[_],[_]). blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]). blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb], [_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):- equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]), blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb], [U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]). %% , % equ(_,[],_,[]):-!. equ(C,_,C,_):-!. equ(C0,_,C,N):-C>C0,!,findall(X,(member(X,N),X<C),[]). equ(C0,[C0|T0],C,[C|T]):-!,equ(C0,T0,C,T).
最後の2つの述語は、入力行列を受け取り、適切な結果の検索を開始し、要素間の要素の合計を減算し、問題に必要な最終合計を見つけます。
diffall(L0,L2,S):- flatten(L0,F0),sum_list(F0,S0), flatten(L2,F2),sum_list(F2,S2), S is S2-S0. %% , sums(X,S):-reptest(X,X1),diffall(X,X1,S).
このサイトが提供するテストを紹介します。
reptest(X0,X2):- flatten(X0,FX0), sort(0,>,FX0,Vals), repdown(X0,Vals,X0,X2),!. repdown(X0,Vals,X,X1):- puts(Vals,X0,X1), X\=X1, balns(X0,X1),!. repdown(_,_,X,X). puts(_,[],[]). puts(_,[X],[X]). puts(_,[X,Z],[X,Z]). puts(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,sel_biger(R2,V,R21),puts(V,[R21,R3|T],St). puts(V,[R1,R2,R3|T],[R1|St]) :- puts(V,R2,R21),puts(V,[R21,R3|T],St). sel_biger(C,[H|_],H):-H>=C. sel_biger(C,[_|T],X):-sel_biger(C,T,X). % balns([],[]). balns([_],[_]). balns([_,_],[_,_]). balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :- blevel(B1,B2,B3,R1,R2,R3), balns([B2,B3|Tb],[R2,R3|T]). % , 33 blevel([],[],[],[],[],[]). blevel([_],[_],[_],[_],[_],[_]). blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]). blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb], [_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):- equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]), blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb], [U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]). % , % equ(_,[],_,[]):-!. equ(C,_,C,_):-!. equ(C0,_,C,N):-C>C0,!,findall(X,(member(X,N),X<C),[]). equ(C0,[C0|T0],C,[C|T]):-!,equ(C0,T0,C,T). diffall(L0,L2,S):- flatten(L0,F0),sum_list(F0,S0), flatten(L2,F2),sum_list(F2,S2), S is S2-S0. sums(X,S):-reptest(X,X1),diffall(X,X1,S). %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). :-assert_are_equal(sums([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]],4),true). :-assert_are_equal(sums([[1,3,3,1,3,2],[3,2,1,3,2,3],[3,3,3,2,3,1]],4),true). :-assert_are_equal(sums([[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]],14),true). :-assert_are_equal(sums([[2,3,4],[5,6,7],[8,9,10],[11,12,13],[14,15,16]],0),true). :-assert_are_equal(sums([],0),true). :-assert_are_equal(sums([[1]],0),true). :-assert_are_equal(sums([[2,3]],0),true). :-assert_are_equal(sums([[3],[2]],0),true). :-assert_are_equal(sums([[18,2,3],[4,5,6],[7,8,9]],0),true). :-assert_are_equal(sums([[3,5,5],[5,4,5],[5,5,5]],1),true). :-assert_are_equal(sums([[5,5,5,1],[5,1,1,5],[5,1,5,5],[5,2,5,8]],3),true). :-assert_are_equal(sums([[2,2,2],[2,1,2],[2,1,2],[2,1,2]],0),true). :-assert_are_equal(sums([[17,2,3,4,5,6,7,8,9,10]],0),true). :-assert_are_equal(sums([[9,9,9,9,9],[9,2,1,2,9],[9,2,8,2,9],[9,2,3,2,9],[9,9,9,9,9]],57),true). %:-assert_are_equal(sums([[9,9,9,9,9,9,8,9,9,9,9],[9,0,0,0,0,0,1,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,9,9,9,9,9,9,9,9,9,9]],215),true). :-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true). :-assert_are_equal(sums([[3,3,4,4,4,2],[3,1,3,2,1,4],[7,3,1,6,4,1]],5),true). %:-assert_are_equal(sums([[78,16,94,36],[87,93,50,22],[63,28,91,60],[64,27,41,27],[73,37,12,69],[68,30,83,31],[63,24,68,36]],44),true).
私はテストについてコメントしなければなりませんでした すべてが合格したわけではありません。
タスクはそれをスピードアップする方法ですか？
ソリューションの検索が長いために見つからないソリューションもありますが、この順序で生成されるのは遅すぎます。ここでは複雑さはおそらくn！です。配列の各セルのすべての可能な値はソートされます。
プログラミングシステムでこのタスクを制限して表現すると便利です。Prologでは、 CLP（FD）：Constraint Logic Programming over Finite Domainsと呼ばれています。
clp（fd）は、標準のSWI-Prolog配布に含まれるライブラリです。 変数間の関係が満たされる必要がある変数のセットに関連する問題を解決します。
>>
私はこのような問題を定式化します：
このようなリストが必要です。マップ全体の最大値以上の値のセットの各要素は、対応するこぼれた液体の順に要素を明確に配置する必要があるという制限を考慮します。
これは、指定された範囲（現在の要素のR2値からVの最大値まで）で要素が不明になった新しいリストである入力リストから行う方法です。
入力ではリストのリスト、出力では値の最大配列を持つ新しいリスト、
「流体バランス」バランスの制限を満たします。
checks(X0,X2):- flatten(X0,FX), max_list(FX,Max),checks(Max,X0,X2), balns(X0,X2), flatten(X2,FX2), labeling([down],FX2). checks(_,[],[]). checks(_,[X],[X]). checks(_,[X,Z],[X,Z]). checks(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!, R21 in R2..V, checks(V,[R21,R3|T],St). checks(V,[R1,R2,R3|T],[R1|St]) :- checks(V,R2,R21),checks(V,[R21,R3|T],St).
これは同時にジェネレーターとチェックの両方であり、要素がそのようなセットにあることを示し、その後徐々にチェックを課し、このセットが狭められます。 さらに、何かが残っており、「マーク」することができます。 すべての制約の合計を満たす整数値を設定します。 ラベリング（[down]、FX2）を呼び出すと、強制的に塗りつぶされます （連絡先） 変数 特定の値では不明であり、そのようなオプションがいくつか存在する可能性がありますが、すべての変数は上限から下に移動すると言われているため、常に最初のオプションを使用します。これらは[down]検索オプションです。
16.2.1。 変数選択戦略
変数選択戦略では、Varのどの変数に次にラベルを付け、次のいずれかを指定できます。
leftmost-変数にVarで発生する順序でラベルを付けます。 これがデフォルトです。
ff最初に失敗します。 実行不可能性を早期に検出するために、次に左端の変数に最小ドメインのラベルを付けます。 これは、最初の変数が選択されたときに後続の変数の小さなドメインがある場合に、多くの場合、優れた戦略です。
ffc最小のドメインを持つ変数のうち、ほとんどの制約に関与する左端の変数が次にラベル付けされます。 制約を適用するにはサブツリーを削除する必要があるため、これは良い戦略になります。
min下限が次に低い左端の変数にラベルを付けます。 これは、ソリューションソリューションを決定するmin / 1とは異なるmin / 0であり、前のセクションで説明したことに注意してください。 これは、さまざまな変数が低い場合に低くなる可能性のあるグローバル値を最小化しようとする場合の優れた戦略です（たとえば、最小コストのソリューション）。
max上限が次に高い左端の変数にラベルを付けます。 これもmax / 1とは異なります。 また、グローバル値を最大化しようとする場合、minのアドバイスはmaxに適用されます。
16.2.2。 値順
値の順序は次のいずれかです。
up選択した変数のドメインの要素を昇順で試してください。 これがデフォルトです。
downドメイン要素を降順で試してください。
明らかに、上で効率的にラベルを付ける方法で説明したように、非対称分布がある場合は、最も一般的な最初の順序で要素を試してください。
16.2.3。 分岐戦略
分岐戦略は次のいずれかです。
step各変数Xについて、X = VとX＃\ = Vの間で選択が行われます。ここで、Vは値の順序付けオプションによって決定されます。 これがデフォルトです。
enum変数Xごとに、Xのドメインのすべての値V_iについて、X = V_1、X = V_2などの間で選択が行われます。順序は、値の順序付けオプションによって決定されます。
bisect各変数Xについて、X＃= <MおよびX＃> Mの間で選択が行われます。ここで、MはXのドメインの中間点です。多くの変数が整数の範囲、値、列挙された値のセットのうちの1つではなく（たとえば、パーセンテージ、v = a、b = 1、c = 2）
実際に「バランスが取れている」のは、注がれた水がセルからセルに溢れないときです。 これは、要素の元の順序の対応です。 セルを埋めると元の風景の形状が維持されると考えるかもしれません。つまり、壁があった場合、その上を水で覆うことができ、そのためすべての隣人と等しくなるか、水で覆われた壁ではない場合...
バランスの取れた状況を考慮してください。
-セルが浸水している場合、それらの隣は同じかさらに高くなります（突然壁になります）。
-セルが隣接セルと等しい場合、新しい隣接セルと等しくなければなりません。
-そして極端な場合、セルはその意味を変えず、それでも彼女はどんな隣人を持っていました：
% balns([],[]). balns([_],[_]). balns([_,_],[_,_]). balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :- blevel(B1,B2,B3,R1,R2,R3), balns([B2,B3|Tb],[R2,R3|T]). % , 33 blevel([],[],[],[],[],[]). blevel([_],[_],[_],[_],[_],[_]). blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]). blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb], [_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):- equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]), blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb], [U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]). % , % equ(C0,_,C,[U,L,R,D]):-C#>C0,C#=<U,C#=<R,C#=<L,C#=<D. equ(_,[],_,[]). equ(C0,[C0|T0],C,[C|T]):-equ(C0,T0,C,T). equ(C,_,C1,_):-C1#=C.
これにより、タスクに対する態度をプログラムに移すことができます。 ソリューションアルゴリズムについて考える必要はありません。結果の正しい説明を提供し、すべての初期制約（値のセット）を正しく設定することが重要です。 このアプローチは、Prolog固有のリターンと再帰を使用した通常の検索と単純に「混合」できます。 これは、 従来の Prologメソッドを使用するよりもさらに宣言 的なプログラムを作成する方法です。
一連のテストで、得られたソリューションを提供します。
:- use_module(library(clpfd)). checks(X0,X2):- flatten(X0,FX), max_list(FX,Max),checks(Max,X0,X2), balns(X0,X2), flatten(X2,FX2), labeling([down],FX2). checks(_,[],[]). checks(_,[X],[X]). checks(_,[X,Z],[X,Z]). checks(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!, R21 in R2..V, checks(V,[R21,R3|T],St). checks(V,[R1,R2,R3|T],[R1|St]) :- checks(V,R2,R21),checks(V,[R21,R3|T],St). % balns([],[]). balns([_],[_]). balns([_,_],[_,_]). balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :- blevel(B1,B2,B3,R1,R2,R3), balns([B2,B3|Tb],[R2,R3|T]). % , 33 blevel([],[],[],[],[],[]). blevel([_],[_],[_],[_],[_],[_]). blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]). blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb], [_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):- equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]), blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb], [U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]). % , % equ(C0,_,C,[U,L,R,D]):-C#>C0,C#=<U,C#=<R,C#=<L,C#=<D. equ(_,[],_,[]). equ(C0,[C0|T0],C,[C|T]):-equ(C0,T0,C,T). equ(C,_,C1,_):-C1#=C. diffall(L0,L2,S):- flatten(L0,F0),sum_list(F0,S0), flatten(L2,F2),sum_list(F2,S2), S is S2-S0. sums(X,S):-checks(X,X1),!,diffall(X,X1,S). %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). :-assert_are_equal(sums([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]],4),true). :-assert_are_equal(sums([[1,3,3,1,3,2],[3,2,1,3,2,3],[3,3,3,2,3,1]],4),true). :-assert_are_equal(sums([[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]],14),true). :-assert_are_equal(sums([[2,3,4],[5,6,7],[8,9,10],[11,12,13],[14,15,16]],0),true). :-assert_are_equal(sums([[18,2,3],[4,5,6],[7,8,9]],0),true). :-assert_are_equal(sums([[3,5,5],[5,4,5],[5,5,5]],1),true). :-assert_are_equal(sums([[5,5,5,1],[5,1,1,5],[5,1,5,5],[5,2,5,8]],3),true). :-assert_are_equal(sums([[2,2,2],[2,1,2],[2,1,2],[2,1,2]],0),true). :-assert_are_equal(sums([[17,2,3,4,5,6,7,8,9,10]],0),true). :-assert_are_equal(sums([[9,9,9,9,9],[9,2,1,2,9],[9,2,8,2,9],[9,2,3,2,9],[9,9,9,9,9]],57),true). :-assert_are_equal(sums([[78,16,94,36],[87,93,50,22],[63,28,91,60],[64,27,41,27],[73,37,12,69],[68,30,83,31],[63,24,68,36]],44),true). :-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true). :-assert_are_equal(sums([[5,5,5],[5,1,5],[5,5,5]],4),true). :-assert_are_equal(sums([[5,5,5],[5,1,5],[5,1000,6]],4),true). :-assert_are_equal(sums([[5,8,7,7],[5,2,1,5],[7,1,7,1],[8,9,6,9],[9,8,9,9]],12),true). :-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true). :-assert_are_equal(sums([[3,3,4,4,4,2],[3,1,3,2,1,4],[7,3,1,6,4,1]],5),true). :-assert_are_equal(sums([[14,17,18,16,14,16],[17,3,10,2,3,8],[11,10,4,7,1,7],[13,7,2,9,8,10],[13,1,3,4,8,6],[20,3,3,9,10,8]],25),true). :-assert_are_equal(sums([[14,17,12,13,20,14],[12,10,5,8,9,5],[16,1,4,7,2,1],[17,4,3,1,7,2],[16,6,5,8,7,6],[17,10,4,8,5,6]],12),true).
:-assert_are_equal(sums([[13,16,15,18,15,15],[14,1,8,9,7,9],[19,5,4,2,5,10],[13,1,7,9,10,3],[17,7,5,10,6,1],[15,9,8,2,8,3]],36),true). :-assert_are_equal(sums([[18,13,13,17,12,11],[17,2,6,10,5,10],[11,10,2,8,8,2],[12,6,10,8,8,7],[18,4,7,6,7,4],[20,5,9,2,3,10]],18),true). :-assert_are_equal(sums([[14,20,11,19,19,16],[11,10,7,4,9,6],[17,2,2,6,10,9],[15,9,2,1,4,1],[15,5,5,5,8,7],[14,2,8,6,10,7]],11),true). :-assert_are_equal(sums([[19383,10886,12777,16915,17793,18335,15386,10492,16649,11421],[12362,27,8690,59,7763,3926,540,3426,9172,5736],[15211,5368,2567,6429,5782,1530,2862,5123,4067,3135],[13929,9802,4022,3058,3069,8167,1393,8456,5011,8042],[16229,7373,4421,4919,3784,8537,5198,4324,8315,4370],[16413,3526,6091,8980,9956,1873,6862,9170,6996,7281],[12305,925,7084,6327,336,6505,846,1729,1313,5857],[16124,3895,9582,545,8814,3367,5434,364,4043,3750],[11087,6808,7276,7178,5788,3584,5403,2651,2754,2399],[19932,5060,9676,3368,7739,12,6226,8586,8094,7539]],79058),true). :-assert_are_equal(sums([[10795,10570,11434,10378,17467,16601,10097,12902,13317,10492],[16652,756,7301,280,4286,9441,3865,9689,8444,6619],[18440,4729,8031,8117,8097,5771,4481,675,709,8927],[14567,7856,9497,2353,4586,6965,5306,4683,6219,8624],[11528,2871,5732,8829,9503,19,8270,3368,9708,6715],[16340,8149,7796,723,2618,2245,2846,3451,2921,3555],[12379,7488,7764,8228,9841,2350,5193,1500,7034,7764],[10124,4914,6987,5856,3743,6491,2227,8365,9859,1936],[11432,2551,6437,9228,3275,5407,1474,6121,8858,4395],[16029,1237,8235,3793,5818,4428,6143,1011,5928,9529]],68900),true). :-assert_are_equal(sums([[18776,12404,14443,15763,14613,14538,18606,16840,12904,14818],[15128,688,7369,7917,9917,6996,3324,7743,9470,2183],[18490,5499,9772,6725,5644,5590,7505,8139,2954,9786],[17669,8082,8542,8464,197,9507,9355,8804,6348,8611],[13622,7828,9299,7343,5746,5568,4340,5422,3311,3810],[17605,1801,5661,3730,4878,1305,9320,8736,9444,8626],[18522,3465,6708,3416,8282,3258,2924,7637,2062,5624],[12600,2036,3452,1899,9379,5550,7468,71,973,7131],[13881,4930,8933,5894,8660,163,7199,7981,8899,2996],[12959,3773,2813,9668,7190,1095,2926,6466,5084,1340]],61413),true). :-assert_are_equal(sums([[12090,17684,13376,15542,15936,19107,17445,19756,19179,18418],[16887,9412,3348,2172,1659,2009,2336,5210,6342,7587],[18206,9301,7713,7372,5321,1255,4819,4599,7721,9904],[15939,9811,3940,5667,1705,6228,1127,9150,5984,6658],[13920,9224,2422,7269,1396,4081,5630,84,9292,1972],[17672,3850,7625,5385,1222,9299,6640,6042,3898,713],[12298,6190,524,2590,8209,8581,8819,9336,7732,1155],[15994,8004,379,4769,5273,1776,8850,7255,1860,8142],[15579,5884,1993,3205,7621,9567,2504,613,1961,2754],[11326,4259,8944,8202,3202,3506,6784,2021,2842,868]],89383),true). :-assert_are_equal(sums([[19528,15189,18872,19908,19958,10498,18036,18808,17753,16248],[13303,3333,2133,1648,2890,9754,7567,1746,368,9529],[14500,8046,3788,9797,6249,6990,3303,3033,5363,2497],[10253,4892,7686,9125,1152,3996,5975,9188,9157,3729],[15436,2460,3414,3921,460,6304,28,8027,8050,6748],[17556,8902,4794,7697,8699,1043,1039,2002,428,6403],[14500,681,7647,8538,6159,5151,2535,2134,4339,1692],[12215,6127,504,5629,49,964,8285,6429,5343,6335],[13177,2900,5238,7971,6949,289,5367,7988,2292,5795],[10743,3144,2829,8390,1682,5340,3541,569,3826,4232]],100439),true).
これらはサイトからのテストで、最初の30個のみでした。 結果は素晴らしく、問題は解決され、さらには1秒まですべての時間で解決されます。
結論として
宣言型プログラミングでは、タスクの詳細な形式化が行われ、ソルバーは条件を満たせる最も効果的なソリューションを探します。
トピックをもう少し詳しく見てみると、このパラダイムが組み込まれているプログラミング言語であるminizincを開くことができます。 彼らは多くの意味を定式化し、制限を示し、答えをほのめかしました。 彼らは、 数独 、マップの色付けタスク、 スケジューリング作業 、リソースの問題、スケジューリングを解決します。 私は訓練することをお勧めします...