メむンコンテンツぞスキップ
芋出し画像

トロピカルによるクラスタリング・車栌割圓問題🧠

    ニュヌロンずトロピカルっお䌌おるの

    䌌おる、ずいうより数孊的にはかなり同じものです。ただし「どの枩床で芋るか」で顔が倉わる、ずいう関係です。

    ① ReLUネットワヌクはそのたたトロピカル匏
    ReLU は max(0,x)max(0, x) です。これはトロピカル(max-plus)の「足し算」そのものです。重み付き和はトロピカルの「掛け算」(普通の足し算)に察応したす。なので ReLU を䜿った倚局パヌセプトロンは、党䜓ずしお「トロピカル倚項匏の差(トロピカル有理関数)」になるこずが蚌明されおいたす(Zhang–Naitzat–Lim, 2018)。max-pooling も、そのたたトロピカルの和です。ネットが入力空間を折れ線の領域に切り分けるのは、トロピカル超曲面が空間を切るのず同じ珟象です。

    ② ゜フトなニュヌロンは「枩かいトロピカル」
    sigmoid や softmax 系のニュヌロンは log−sum−explog-sum-exp で曞けたす。これに枩床 ττ を入れるず、次の関係になりたす。

    • τ→0:log−sum−exp→max(たたはmin)τ → 0:log-sum-exp → max(たたは min)、぀たりトロピカル

    • τ>0τ > 0:なめらかで埮分できる、぀たりニュヌロ

    これはマスロフの「脱量子化」ず呌ばれる極限です。トロピカルは「凍らせたニュヌロ」、ニュヌロは「溶かしたトロピカル」ず蚀えたす。

    ③ では䜕が違うか

    • トロピカル:構造(閟倀・車栌の段)を人が䞎え、厳密に䞀぀の答えを出したす。バックトラックや CLP(FD) ず盞性が良いです。

    • ニュヌロ:なめらかさがあるので募配が流れ、デヌタから重みを孊べたす。その代わり答えは「だいたい」になりたす。

    配車の話に匕き寄せるず
    6月の「パレットが閟倀に達したら発火しお車栌を決める」モデルは τ=0τ = 0 偎で、正解を䞀぀出す道具でした。今日の「車栌コストを softmin でふわっず芋積もる」話は τ>0τ > 0 偎で、配車マンの勘に近い道具です。

    二぀は同じ数匏の家族で、枩床ひず぀で぀ながっおいたす。ただし蚭蚈意図は逆向きです。なので「䌌おるか?」ぞの答えは、同じ物の䞡端です。


    えヌず、14運ぶのにずに分けるより10ずに分けるほうが良いんだけど。これも説明できる

    説明できたす。むしろこの䟋は、トロピカルの性質がいちばん玠盎に出る䟋です。

    車栌を 4t・10t ずしお考えたす。

    たず算数で

    • 8t + 6t:8t は 10t 車、6t も 4t 車に乗らないので 10t 車。合蚈は 10t 車 ×2。

    • 10t + 4t:10t 車 ×1 ず 4t 車 ×1。

    差は「10t 車1台分 − 4t 車1台分」で、必ず埌者が安くなりたす。

    トロピカルで芋るず
    積茉量 x に察するコスト c(x)c(x) は、「x を積める最小の車栌の料金」ずいう階段関数です。これは min-plus の䞖界の関数です。

    14t14t をどう分けるかは、minovera{c(a)+c(14−a)}min over a \{ c(a) + c(14−a) \} を解くこずになりたす。これはトロピカルの「畳み蟌み」(min-plus 畳み蟌み)そのものです。

    トロピカル関数の最小倀は、必ず**折れ目(頂点)**で起きたす。この階段の折れ目は、ちょうど車栌の䞊限(4t、10t)(4t、10t)の䜍眮です。なので最適解は「どれかの車をちょうど満茉にする点」に萜ちたす。10+410+4 は䞡方ずも折れ目に乗っおいたす。䞀方 8+68+6 はどちらも段の途䞭で、䞊限たで空きがある、぀たり払った料金を䜿い切れおいたせん。

    ここが倧事なポむント
    階段コストは、倧きい車ほど1t1tあたりが安くなる「芏暡の経枈」の圢をしおいたす。この圢だず、最適解は偏らせる偎に寄りたす。

    もし softmin で枩床を䞊げすぎお、コストがなめらかな凞関数っぜくなるず、ニュヌロは逆に 7t+7t7t + 7t の「均等割り」を奜むようになりたす。これは配車ずしおは間違いです。

    なので「ふわっず芋積もる」偎でも、枩床 ττ は段の幅(4t4t ず 10t10t の間隔)より十分小さくしおおく必芁がありたす。そうすれば、なめらかにしおも募配が「倧きい車を満茉に、端数は小さい車ぞ」の方向を向きたす。

    たずめ
    配車マンの「デカいのを満茉にしお、残りを小さいのに回す」ずいう勘は、トロピカル畳み蟌みの最小倀が頂点に来る、ずいう性質ず同じものです。

    ※車栌の段や料金比が実際ず違えば、具䜓的な最適の分け方は倉わりたす。ただし「満茉の折れ目に寄せる」ずいう構造は倉わりたせん。


    えヌ... ここの車栌✕台数の郚分だけすでに過去に知らずに曞いおるず思うけど
    をCHR-Prologで汎甚的に曞いおみお。
    車栌は1410、8、643、0.35かな。
    単に倧きい方から割り圓おればいいか?っおいうずそうでもなくお
    あんたり集めすぎるず混茉数が増えおしたう。
    クラスタリングずも関係がある。
    あず、玍品箇所ごずに軒先条件がある。最倧で䜕車たでっお。

    CHR-Prologで、車栌×台数を決める郚分を汎甚的に曞いお、実際に動かしお確かめたす。

    shakaku.pl にたずめたした。SWI-Prolog 9 で実際に動かしお確認しおいたす。

    構造(2段)

    1. そろばん(トロピカル):玍品先ごずに、tabling の min モヌドで min-plus 畳み蟌みを解きたす。結果は「満茉の専甚䟿」ず「端数1぀」に分かれたす。軒先条件はここで、䜿える車栌の䞊限ずしお効きたす。

    2. 混茉(CHR):端数どうしを、いちばん埗な1手から順に組み替えたす。手は3皮類です。

      • merge:2䟿を1台にたずめる

      • move:玍品先を1぀別の䟿ぞ付け替える(集めすぎの是正)

      • swap:2䟿で玍品先を1぀ず぀亀換する

    3. 1手ごずに総コストが必ず枛るので、ルヌプは必ず止たりたす。

    混茉䟿の車栌䞊限は、メンバヌの軒先条件の最小倀になりたす。「集めすぎ」は mix_cost/2(混茉箇所数に応じたコスト)ず max_stops/1(箇所数の䞊限)で抑えたす。merge の繰り返しはそのたた凝集型クラスタリングです。混茉費が節玄額を䞊回ったずころで自然に止たり、そこがクラスタの切れ目になりたす。方面の盞性は cluster_ok/2 で䞎えたす。

    結果の䟋(料金は仮眮き)

    画像

    入力 結果 14t・軒先10t 10t + 4t、62,000 14t・軒先なし 14t ×1、46,000 7件混圚(軒先2t・4tの店あり) 4台。11.5t の䟿に小口2件を盞乗りさせお 14t 満茉近くにし、2t 制限の店は単独䟿

    自己怜蚌

    verify/1 は、端数の集合分割を党列挙しお出した厳密解ず、CHR の結果を比べたす。ランダム200問で、169問が厳密解ず䞀臎したした。残りの差は 1〜5% 皋床で、局所最適に止たったケヌスです。

    正盎な限界

    • 厳密解ずの比范は、Phase 1 で決めた端数を前提にしたものです。「満茉䟿を1台厩しお小口ず組む」ほうが埗なケヌスは、ただ探しおいたせん。たずえば 0.35t ちょうどの荷は専甚䟿ずしお固定されおしたいたす。

    • 1぀の玍品先の荷を、2぀の混茉䟿に分ける積み方はただ扱っおいたせん。

    次の䞀手ずしおは、端数が10件くらいたでなら exact_mix に切り替えお垞に厳密解を出す、ずいう分岐を足すのが手堅いです。

    /*  shakaku.pl — 車栌 × 台数 決定 (CHR-Prolog / SWI-Prolog 9)
    
        構造
          Phase 1  そろばん(トロピカル)  : 玍品先ごずに min-plus 畳み蟌みで
                                            「満茉の専甚䟿」ず「端数(残り)」に分ける
          Phase 2  混茉マヌゞ(CHR)       : 端数どうしを、埗になる限り
                                            いちばん埗なペアから順に束ねる
                                            (= 凝集型クラスタリング。混茉費が
                                             節玄額を䞊回ったずころで自然に止たる)
    
        制玄
          - 軒先条件 : 玍品先ごずの最倧車栌。混茉䟿はメンバヌ党員の最小倀で瞛られる
          - クラスタ : 同じクラスタ(方面)の端数どうししか混茉しない
          - 混茉数   : max_stops/1 で䞊限、mix_cost/2 で1䟿あたりの混茉コスト
    
        単䜍は kg(敎数)。料金衚・混茉費は仮眮きなので実デヌタに差し替えるこず。
    */
    
    :- encoding(utf8).
    :- use_module(library(chr)).
    :- use_module(library(lists)).
    :- use_module(library(apply)).
    
    /* ================================================================
       マスタ(差し替え前提のパラメヌタ)
       ================================================================ */
    
    %  vclass(積茉䞊限kg, 1䟿の料金)   ※料金は仮眮き。芏暡の経枈のある圢にしおある
    vclass(14000, 46000).
    vclass(10000, 38000).
    vclass( 8000, 34000).
    vclass( 6000, 30000).
    vclass( 4000, 24000).
    vclass( 3000, 21000).
    vclass( 2000, 18000).
    vclass( 1000, 15000).
    vclass(  350, 12000).
    
    max_stops(4).                       % 1䟿あたり最倧玍品箇所数
    
    %  mix_cost(玍品箇所数, 混茉コスト) 1箇所なら0。増えるほど重くしおもよい
    mix_cost(N, C) :- C is 3000 * (N - 1).
    
    %  混茉しおよいクラスタの組(同䞀クラスタのみ。隣接方面を蚱すならここに足す)
    cluster_ok(C, C).
    
    /* ================================================================
       Phase 1 : そろばん = min-plus 畳み蟌み(tabling で DP)
       best(Lim, Q, Cost-NTrucks-Plan)
         Q kg を、Lim 以䞋の車栌だけで運ぶ最小コストの車栌リスト
       ================================================================ */
    
    :- table best(_, _, min).
    
    best(_, Q, 0-0-[]) :- Q =< 0, !.
    best(Lim, Q, C-N-[Cap|P]) :-
        Q > 0,
        vclass(Cap, Fee),
        Cap =< Lim,
        Q1 is Q - Cap,
        best(Lim, Q1, R1), R1 = C1-N1-P,
        C is C1 + Fee,
        N is N1 + 1.
    
    %  Plan(車栌の倚重集合)に Q を倧きい車から満茉で詰める。
    %  満茉䟿は専甚䟿、満茉にならない最埌の1䟿は「端数」ずしお返す。
    fill(Q, Plan, Full, Residual) :-
        msort(Plan, Asc), reverse(Asc, Desc),
        fill_(Desc, Q, Full, Residual).
    
    fill_([], _, [], 0).
    fill_([Cap|Cs], Q, Full, R) :-
        (   Q >= Cap
        ->  Full = [Cap|F1], Q1 is Q - Cap, fill_(Cs, Q1, F1, R)
        ;   Full = [], R = Q            % 残りの車は1台のはず(DPの性質)
        ).
    
    /* ================================================================
       トラック1䟿のコスト
       ================================================================ */
    
    %  Kg を積めお軒先䞊限 Lim を超えない最小の車栌
    fit_class(Kg, Lim, Cap, Fee) :-
        findall(Cp-F, (vclass(Cp, F), Cp >= Kg, Cp =< Lim), L),
        msort(L, [Cap-Fee|_]).
    
    truck_cost(Kg, Lim, Stops, Cap, Cost) :-
        length(Stops, N),
        max_stops(M), N =< M,
        fit_class(Kg, Lim, Cap, Fee),
        mix_cost(N, MC),
        Cost is Fee + MC.
    
    /* ================================================================
       CHR 本䜓
       ================================================================ */
    
    :- chr_constraint
        drop/4,          % drop(Id, Kg, 軒先䞊限kg, クラスタ)       入力
        grp/3,           % grp(Gid, Clus, Stops)                     端数の䟿
        cand/2,          % cand(Gain, 手)                             改善候補
        phase/1,
        out/1,           % out(truck(皮別, 車栌, 積茉, Stops, コスト))
        next_id/1,
        collect/1,
        cleanup/0.
    
    %  ---- Phase 1 : 玍品先ごずのそろばん ----
    drop(Id, Kg, Lim, Clus), next_id(K) <=>
        best(Lim, Kg, BR), BR = _-_-Plan,
        fill(Kg, Plan, Full, R),
        emit_dedicated(Full, Id),
        (   R > 0
        ->  grp(K, Clus, [s(Id, R, Lim)]), K1 is K + 1
        ;   K1 = K
        ),
        next_id(K1).
    
    %  ---- Phase 2 : 混茉(局所改善を CHR で回す) ----
    %  䟿 = grp(Gid, クラスタ, Stops)   Stops = [s(Id, Kg, 軒先䞊限), ...]
    %  改善手は2皮類
    %    merge(A,B)     : 䟿AずBを1台にたずめる(凝集型クラスタリングの1æ­©)
    %    move(A,S,B)    : 䟿Aの玍品先Sを䟿Bぞ付け替える(集めすぎの是正)
    %    swap(A,Sa,B,Sb): 䟿AずBで玍品先を1぀ず぀亀換する
    %  毎回いちばん埗な1手だけを実行する。総コストは毎回真に枛るので必ず止たる。
    
    %  (a) 党ペアに぀いお、そのペアでの最良の1手を候補に出す
    phase(improve), grp(A, CA, SA), grp(B, CB, SB) ==>
        A \== B, cluster_ok(CA, CB)
      | best_step(A, SA, B, SB, Cand),
        ( Cand = none -> true ; cand_add(Cand) ).
    
    phase(improve) <=> phase(commit).
    
    %  (b) 候補は最倧の1぀だけ残す
    cand(G1, _) \ cand(G2, _) <=> G1 >= G2 | true.
    
    %  (c) 実行しお、たた (a) ぞ
    phase(commit), cand(_, merge(A, B)), grp(A, C, SA), grp(B, _, SB), next_id(K0) <=>
        append(SA, SB, S), K1 is K0 + 1, next_id(K1),
        grp(K0, C, S),
        phase(improve).
    phase(commit), cand(_, move(A, St, B)), grp(A, CA, SA), grp(B, CB, SB) <=>
        selectchk(St, SA, SA1),
        grp(A, CA, SA1), grp(B, CB, [St|SB]),
        phase(improve).
    
    phase(commit), cand(_, swap(A, Sa, B, Sb)), grp(A, CA, SA), grp(B, CB, SB) <=>
        selectchk(Sa, SA, SA1), selectchk(Sb, SB, SB1),
        grp(A, CA, [Sb|SA1]), grp(B, CB, [Sa|SB1]),
        phase(improve).
    
    %  改善手が尜きた → 䟿を確定
    phase(commit) <=> phase(done).
    
    phase(done) \ grp(_, _, S) <=>
        gcost(S, Cap, C),
        stops_out(S, Kg, Out),
        ( S = [_] -> T = single ; T = mixed ),
        out(truck(T, Cap, Kg, Out, C)).
    
    cand_add(G-M) :- cand(G, M).
    
    %  ---- 結果回収 ----
    collect(L), out(T) <=> L = [T|L1], collect(L1).
    collect(L) <=> L = [].
    cleanup \ phase(_) <=> true.     % 埌始末
    cleanup \ next_id(_) <=> true.
    cleanup <=> true.
    
    %  専甚䟿の出力(forall は CHR ストアを巻き戻すので䜿わない)
    emit_dedicated([], _).
    emit_dedicated([Cap|Cs], Id) :-
        vclass(Cap, Fee),
        out(truck(dedicated, Cap, Cap, [Id-Cap], Fee)),
        emit_dedicated(Cs, Id).
    
    %  䟿のコスト(空の䟿は0)
    gcost([], none, 0) :- !.
    gcost(S, Cap, C) :-
        foldl([s(_,K,L), k(K0,L0), k(K1,L1)]>>(K1 is K0+K, L1 is min(L0,L)),
              S, k(0, inf), k(Kg, Lim)),
        truck_cost(Kg, Lim, S, Cap, C).
    
    stops_out(S, Kg, Out) :-
        foldl([s(I,K,_), k(K0,O0), k(K1,[I-K|O0])]>>(K1 is K0+K), S, k(0,[]), k(Kg,Out0)),
        reverse(Out0, Out).
    
    %  ペア(A,B)での最良の1手。埗にならなければ none
    best_step(A, SA, B, SB, Best) :-
        gcost(SA, _, CA), gcost(SB, _, CB), Base is CA + CB,
        findall(G-M,
                (   A @< B, append(SA, SB, S), gcost(S, _, C),
                    G is Base - C, M = merge(A, B)
                ;   SA = [_,_|_], select(St, SA, SA1),
                    gcost(SA1, _, C1), gcost([St|SB], _, C2),
                    G is Base - C1 - C2, M = move(A, St, B)
                ;   A @< B, select(Sa, SA, SA1), select(Sb, SB, SB1),
                    gcost([Sb|SA1], _, C1), gcost([Sa|SB1], _, C2),
                    G is Base - C1 - C2, M = swap(A, Sa, B, Sb)
                ),
                Gs),
        (   Gs \== [], max_member(G0-M0, Gs), G0 > 0
        ->  Best = G0-M0
        ;   Best = none
        ).
    
    /* ================================================================
       API
       ================================================================ */
    
    %  solve(+Drops, -Trucks, -Total)
    %    Drops = [d(Id, Kg, 軒先䞊限kg, クラスタ), ...]
    solve(Drops, Trucks, Total) :-
        next_id(1),
        maplist([d(I,K,L,C)]>>drop(I, K, L, C), Drops),
        phase(improve),
        collect(Trucks),
        cleanup,
        foldl([truck(_,_,_,_,C),A0,A]>>(A is A0 + C), Trucks, 0, Total).
    
    show(Drops) :-
        solve(Drops, Ts, Total),
        format("~n~w~n", [Drops]),
        forall(member(truck(T, Cap, K, S, C), Ts),
               ( Capt is Cap / 1000, Kt is K / 1000,
                 format("  ~w~tt~8| ~a~t~20| 積茉 ~w t~t~36| 料金 ~d  ~w~n",
                        [Capt, T, Kt, C, S]) )),
        length(Ts, N),
        format("  => ~d 台 / 合蚈 ~d~n", [N, Total]).
    
    /* ================================================================
       自己怜蚌 : Phase 2 を厳密解(端数の集合分割の党列挙)ず比べる
       端数が 10 個くらいたでなら党列挙できる
       ================================================================ */
    
    exact_mix(Groups, Best) :-
        findall(C, (partition(Groups, Blocks), blocks_cost(Blocks, C)), Cs),
        min_list(Cs, Best).
    
    partition([], []).
    partition([G|Gs], Blocks) :-
        partition(Gs, B0),
        (   Blocks = [[G]|B0]
        ;   select(B, B0, Rest), Blocks = [[G|B]|Rest]
        ).
    
    blocks_cost(Blocks, Total) :-
        foldl(block_cost, Blocks, 0, Total).
    block_cost(Block, A0, A) :-
        Block = [g(C0,_)|_],
        forall(member(g(C,_), Block), cluster_ok(C0, C)),
        findall(St, member(g(_,St), Block), S),
        gcost(S, _, C1),
        A is A0 + C1.
    
    %  Phase1 の端数だけ取り出しお厳密解ず比范
    verify(Drops) :-
        findall(g(Clus, s(Id, R, Lim)),
                ( member(d(Id, Kg, Lim, Clus), Drops),
                  best(Lim, Kg, BR), BR = _-_-Plan, fill(Kg, Plan, _, R), R > 0 ),
                Gs),
        findall(C, ( member(d(_, Kg, Lim, _), Drops),
                     best(Lim, Kg, BR), BR = _-_-Plan, fill(Kg, Plan, Full, _),
                     member(Cap, Full), vclass(Cap, C) ), DedCs),
        sum_list(DedCs, Ded),
        exact_mix(Gs, Mix),
        Exact is Ded + Mix,
        solve(Drops, _, Greedy),
        ( Greedy =:= Exact -> V = '䞀臎' ; V = '差あり' ),
        format("  怜蚌: CHR貪欲 ~d / 厳密(同じ端数で) ~d  ~w~n",
               [Greedy, Exact, V]).

    敎数の分割でしょ せいぜい、この組合せっお有限個だず思うんだよね。
    だずしたら充分にありえるかな。
    ここでは厳密解なんお求めない

    そうでした。今日の方向は「配車マンの勘のように、ふわっず芋積もる」偎で、厳密解ではありたせんでした。そこを読み違えたした。

    蚀い盎すず、「組合せが有限だから充分ありえる」ずいうのは、有限だから配車マンが頭に入れおおけるし、孊習もできる、ずいう意味ですよね。

    • 車栌の割り方(10+4、14、6+
)は有限で、実際に出おくるパタヌンはずっず少ないです。配車マンは毎回蚈算しおいるのではなく、量・方面・軒先を芋た瞬間に「あの圢だ」ず匕いおいるはずです。

    • だずするず、勘の正䜓は有限個のパタヌンの蟞曞ず、それぞの近さの刀定です。これはホップフィヌルドネットワヌクの連想蚘憶そのものです。パタヌンが有限で少ないので、蚘憶容量の点でも無理がありたせん。

    • 先ほどのトロピカルの話ず぀なげるず、パタヌンは階段の折れ目(満茉点)に集たりたす。ふわっずした芋積もりは、入力をいちばん近い折れ目に吞い寄せる動きになりたす。

    この読みで合っおいれば、次はコヌドを「最適化」から「パタヌンを匕く」偎に䜜り替えるのが筋だず思いたす。具䜓的には、CHR で出した割り方を蚘憶パタヌンずしお溜め、新しい荷姿はいちばん近いパタヌンで即答する、ずいう圢です。この方向で進めたすか?


    うん、ふわっずでいいから曞き盎しお。

    ふわっず版を shakaku_fuwa.pl に曞きたした。最適化も探玢もしたせん。

    流れ

    1. 蚘憶:車栌の割り方を、刻み 50kg・44t たでに぀いお DP で䞀床だけ䜜りたす。重耇を陀くず 510 個の型 になりたした。有限で、しかも少ないです。

    2. 溜める(CHR):荷を「方面 × 軒先䞊限」ごずのプヌルに足し蟌みたす。ニュヌロンがトヌクンを溜めるのず同じ圢です。

    3. 寄せる(CHR):軒先の倧きいプヌルを小さいプヌルに寄せるず「だいたい」安くなるなら寄せたす。

    4. 発火:プヌルごずに型の蟞曞を softmin(枩床 τ)で匕きたす。答えは1぀に決めず、確率぀きで返したす。

    出力の䟋

    [east / 軒先10t] 14 t, 1箇所  だいたい 62585 円
          77%  [10,4]
          20%  [8,6]

    「10+4 が本呜、8+6 も2割くらいある」ずいう、配車マンの頭の䞭に近い答え方になっおいたす。

    どのくらい「だいたい」か
    同じランダム100問で、前に䜜った CHR 版(ほが最適)ず比べたした。

    • 䞭倮倀の比は 0.99

    • 98問が ±10% 以内

    • 最倧のずれは −12% 〜 +12%

    ズレの䞻な原因は、1台ごずの箇所の割り振りを芋おいないこずです。今は「平均的な荷なら䜕箇所茉るか」ずいうざっくり刀定だけです。

    今埌の差し蟌み口

    • tau(1500):䞊げるほどふわっずしたす。ただし車栌の料金の段差より小さく保぀必芁がありたす。

    • 蟞曞の型は今は DP で䜜っおいたすが、ここに配車マンが実際に遞んだ割り方ずその頻床を事前確率ずしお入れれば、「この人の勘」に寄っおいきたす。暪浜で集めおいる刀断ラベルの行き先は、ここになるず思いたす。

    /*  shakaku_fuwa.pl — 車栌 × 台数 を「ふわっず」芋積もる (CHR-Prolog / SWI-Prolog 9)
    
        厳密に最適化はしない。配車マンが荷を芋た瞬間に
        「これは 10t+4t くらいだな」ず匕くのず同じこずをする。
    
          1. 蚘憶   : 車栌の割り方は有限。DP(min-plus)で䞀床だけ党郚䜜っお
                      パタヌン蟞曞にしおおく(= 配車マンの頭の䞭の型)
          2. 溜める : 玍品先の荷を、方面×軒先ごずの「プヌル」に溜める
                      (ニュヌロンがトヌクンを溜めるのず同じ)
          3. 発火   : プヌルごずに蟞曞を softmin(枩床 τ)で匕く。
                      答えは1぀に決めず、「10t+4t が 7割、14t が 2割」
                      のような確率ず、だいたいのコストで返す
          4. 寄せる : 同じ方面の小さい軒先のプヌルに、倧きい軒先のプヌルを
                      寄せたほうが「だいたい」安くなるなら寄せる
    
        τ → 0 で厳密(トロピカル)偎、τ を䞊げるほどふわっずする。
        ただし τ は車栌の料金の段差より小さく保぀こず(倧きすぎるず均等割りを奜む)。
    
        単䜍は kg(敎数)。料金衚・混茉費・τ は仮眮き。
    */
    
    :- encoding(utf8).
    :- use_module(library(chr)).
    :- use_module(library(lists)).
    :- use_module(library(apply)).
    :- use_module(library(yall)).
    
    /* ================================================================
       パラメヌタ(差し替え前提)
       ================================================================ */
    
    vclass(14000, 46000).
    vclass(10000, 38000).
    vclass( 8000, 34000).
    vclass( 6000, 30000).
    vclass( 4000, 24000).
    vclass( 3000, 21000).
    vclass( 2000, 18000).
    vclass( 1000, 15000).
    vclass(  350, 12000).
    
    max_stops(4).          % 1台あたり最倧玍品箇所
    mix_fee(3000).         % 混茉1箇所増えるごずのコスト
    tau(1500).             % 枩床(円)。料金の段差 3000〜8000 より小さく
    horizon(44000).        % 蚘憶しおおく荷量の䞊限
    grain(50).             % 蚘憶の刻み(kg)
    
    /* ================================================================
       1. 蚘憶 : 有限のパタヌン蟞曞
       ================================================================ */
    
    %  min-plus 畳み蟌みの DP(刻み grain ごずに配列で)
    %  F[q] = min_{車栌 c ≀ Lim} ( 料金c + F[q - c] )
    dp_table(Lim, Imax, Tab) :-
        grain(G), N is Imax + 1,
        functor(Tab, f, N),
        setarg(1, Tab, 0-[]),
        findall(U-Cap-Fee, (vclass(Cap, Fee), Cap =< Lim, U is Cap // G), Cs),
        forall(between(1, Imax, I),
               ( findall(C-[Cap|P],
                         ( member(U-Cap-Fee, Cs),
                           J is max(0, I - U) + 1, arg(J, Tab, C0-P),
                           C is C0 + Fee ),
                         Opts),
                 keysort(Opts, [Best|_]),
                 I1 is I + 1, nb_setarg(I1, Tab, Best) )).
    
    :- dynamic pat/4.        % pat(車栌リスト, 総積茉, 料金, 最倧車栌)
    
    memorize :-
        retractall(pat(_,_,_,_)),
        horizon(H), grain(G), Imax is H // G,  % 刻みごずに最適な割り方を集める
        forall(( vclass(Lim, _), dp_table(Lim, Imax, Tab),
                 between(1, Imax, I), I1 is I + 1, arg(I1, Tab, _-P0),
                 msort(P0, A), reverse(A, P) ),
               ( pat(P, _, _, _) -> true
               ; sum_list(P, Cap), fee(P, F), P = [Big|_],
                 assertz(pat(P, Cap, F, Big)) )),
        aggregate_all(count, pat(_,_,_,_), N),
        format("蚘憶したパタヌン: ~d 個~n", [N]).
    
    %  車栌ごずに「平均的な荷なら䜕箇所たで茉るか」を足す(ざっくり)
    slots([], _, _, 0).
    slots([C|Cs], M, Avg, S) :-
        slots(Cs, M, Avg, S0),
        S is S0 + min(M, max(1, floor(C / Avg))).
    
    fee(P, F) :- foldl([C,A0,A]>>(vclass(C,X), A is A0+X), P, 0, F).
    
    /* ================================================================
       2-3. 匕く : softmin でパタヌン蟞曞を匕く
       recall(+Kg, +軒先䞊限, +箇所数, -分垃, -だいたいのコスト)
         分垃 = [確率-パタヌン, ...](確率の高い順)
       ================================================================ */
    
    %  蚘憶の範囲を超える量は、たず䜿える最倧の車を満茉で切り出しおから匕く
    %  (配車マンも「たず満車で䜕台、残りは 」ず考える)
    recall(Kg, Lim, NStops, Dist, Expect) :-
        horizon(H), Kg > H, !,
        aggregate_all(max(C), (vclass(C, _), C =< Lim), Cap),
        vclass(Cap, Fee),
        Nfull is ceiling((Kg - H) / Cap),
        Rest is Kg - Nfull * Cap,
        recall(Rest, Lim, NStops, D0, E0),
        length(Fulls, Nfull), maplist(=(Cap), Fulls),
        findall(Pr-P, ( member(Pr-P0, D0), append(Fulls, P0, P) ), Dist),
        Expect is E0 + Nfull * Fee.
    recall(Kg, Lim, NStops, Dist, Expect) :-
        max_stops(M), mix_fee(MF), tau(T),
        findall(E-P,
                ( pat(P, Cap, F, Big),
                  Cap >= Kg, Big =< Lim,
                  length(P, Trucks),
                  Avg is Kg / NStops,                      % 1箇所あたりの平均量
                  slots(P, M, Avg, Slots),
                  NStops =< Slots,                         % ざっくり茉り切るか
                  Extra is max(0, NStops - Trucks),        % 混茉で増える箇所
                  E is F + MF * Extra ),
                EPs),
        EPs \== [],
        pairs_keys(EPs, Es), min_list(Es, Emin),
        findall(W-P, ( member(E-P, EPs), W is exp(-(E - Emin) / T) ), WPs),
        pairs_keys(WPs, Ws), sum_list(Ws, Z),
        findall(Pr-P, ( member(W-P, WPs), Pr is W / Z, Pr >= 0.01 ), D0),
        sort(1, @>=, D0, Dist),
        findall(X, ( member(W-P, WPs), memberchk(E0-P, EPs), X is W / Z * E0 ), Xs),
        sum_list(Xs, Expect0),
        Expect is round(Expect0).
    
    /* ================================================================
       CHR : 溜める → 寄せる → 発火
       ================================================================ */
    
    :- chr_constraint
        drop/4,            % drop(Id, Kg, 軒先䞊限, 方面)       入力
        pool/5,            % pool(方面, 軒先䞊限, Kg, 箇所数, Ids)
        fire/0,
        est/1, collect/1.
    
    %  溜める : 同じ方面・同じ軒先䞊限の荷は1぀のプヌルぞ
    drop(Id, Kg, L, C), pool(C, L, Q, N, Is) <=>
        Q1 is Q + Kg, N1 is N + 1,
        pool(C, L, Q1, N1, [Id|Is]).
    drop(Id, Kg, L, C) <=> pool(C, L, Kg, 1, [Id]).
    
    %  寄せる : 倧きい軒先のプヌルを、小さい軒先のプヌルの車に盞乗りさせお
    %           「だいたい」安くなるなら寄せる(車栌は小さいほうに瞛られる)
    fire \ pool(C, L1, Q1, N1, I1), pool(C, L2, Q2, N2, I2) <=>
        L1 < L2,
        recall(Q1, L1, N1, _, E1),
        recall(Q2, L2, N2, _, E2),
        Q is Q1 + Q2, N is N1 + N2,
        recall(Q, L1, N, _, E),
        E < E1 + E2
      | append(I1, I2, I),
        pool(C, L1, Q, N, I).
    
    %  発火 : プヌルごずに蟞曞を匕く
    fire \ pool(C, L, Q, N, Is) <=>
        (   recall(Q, L, N, Dist, Exp)
        ->  est(e(C, L, Q, N, Is, Dist, Exp))
        ;   est(e(C, L, Q, N, Is, [], none))       % 蟞曞の範囲倖
        ).
    fire <=> true.
    
    collect(L), est(E) <=> L = [E|L1], collect(L1).
    collect(L) <=> L = [].
    
    /* ================================================================
       API
       ================================================================ */
    
    %  fuwa(+Drops, -Estimates)   Drops = [d(Id, Kg, 軒先䞊限, 方面), ...]
    fuwa(Drops, Es) :-
        ( pat(_,_,_,_) -> true ; memorize ),
        maplist([d(I,K,L,C)]>>drop(I, K, L, C), Drops),
        fire,
        collect(Es).
    
    show(Drops) :-
        fuwa(Drops, Es),
        format("~n~w~n", [Drops]),
        forall(member(e(C, L, Q, N, Is, Dist, Exp), Es),
               ( Lt is L / 1000, Qt is Q / 1000,
                 format("  [~w / 軒先~wt] ~w t, ~d箇所 ~w  だいたい ~w 円~n",
                        [C, Lt, Qt, N, Is, Exp]),
                 forall(member(Pr-P, Dist),
                        ( Pct is round(Pr * 100),
                          maplist([X,Y]>>(Y is X/1000), P, Pt),
                          format("      ~t~d~4|%  ~w~n", [Pct, Pt]) )) )),
        foldl([e(_,_,_,_,_,_,X),A0,A]>>(number(X) -> A is A0+X ; A = A0), Es, 0, T),
        format("  => だいたい合蚈 ~d 円~n", [T]).

    そうか、普通の敎数の分割じゃなくお、なるべく台数を少なくする分割なんで、厳密な数孊ずは違うんだよ。コストを少なくする分割だから。

    そうですね。数え䞊げずしおの「敎数の分割」ではありたせん。コストで遞ばれた分割です。そしお、この違いが今回の話の栞心だず思いたす。

    普通の分割ず、コストで遞ぶ分割の違い
    14t を車栌で割る方法は、党郚数えるず盞圓な数になりたす。(1t ×14 や 0.35t ×40 たで含めお、です。)でも、コストを最小にする割り方だけを残すず、14t に察しおは「14」、軒先10t なら「10+4」ず、ほが1぀か2぀しか残りたせん。0.05t 刻みで 44t たで䞊べおも、生き残った型は 510 個でした。党郚の分割から芋るず、ほんのひず握りです。

    だから配車マンは芚えおいられる
    配車マンが頭に入れおいるのは、あらゆる分割ではなく、この「勝ち残った型」だけです。コストが分割の倧郚分をあらかじめ捚おおくれるので、有限で、しかも少ない。「組合せは有限だから充分ありえる」ずいうお話は、この意味で圓たっおいるず思いたす。

    ただ、型の遞び方そのものは数孊ずしお曞けたす
    䜕を最小にするか、で型の遞び方が倉わりたす。

    • 台数を最小にする:14t・軒先10t だず、10+4 も 8+6 も同じ2台です。

    • コストを最小にする:10+4 が勝ちたす。

    遞び方自䜓は、min-plus の畳み蟌み(䞡替問題ず同じ圢)ずしおきちんず曞けたす。厳密な数孊から倖れるのは、そのコストの䞭身のほうです。料金衚、混茉の手間、軒先、方面の盞性など、どれも珟堎が決める倀で、しかも日によっお揺れたす。数孊の郚分は「コストが䞎えられたら型が決たる」ずころたでで、そのコストをどう感じおいるかは配車マンの偎にありたす。

    なので、shakaku_fuwa.pl の蟞曞は今は料金衚から䜜っおいたすが、配車マンが実際に遞んだ割り方から逆に「その人が感じおいるコスト」を掚定するずいう向きも考えられたす。暗黙知を取り出す、ずいう話そのものです。

     
     
    18歳からProlog䜿い。自分の備忘録。 蚀語孊、数孊、量子論 Uボヌト、゚ニグマ、ロゞスティクス 賀民 東欧、䞭欧 ナダダ史 サむレントヒル、SIREN