Max-Plus+離散モースによる断片ブレイド復元（Claude）③🧠
なんだか、離散モース理論使うと面白そうだと思ったんだけど。
面白いです。しかも当てずっぽうじゃなくて、T がすでに離散モース関数だから、というのが理由になっている気がします。フォアマンの理論は要するに複体の上の高さ関数の話で、あの板は縦軸が最初から高さです。持ち込むというより、もともとそう作られていた。
ただ最初に正直に線を引いておくと、１次元のままだと、新しい定理は出ません。 順に見ます。
第一段：そろばんはすでにモース・マッチング
離散ベクトル場の定義は「ハッセ図の上のマッチング＋非輪状性」です。そろばんでやっていたことを訳すと、
モース そろばん セルの対を組む 玉を取って次の断片に繋ぐ 臨界セル（組めなかったもの） 新規投入した車両 非輪状性 T が単調増加なので自動的に成立 初等崩壊 断片２本を１本の鎖に潰す
臨界セルの最小化＝車両数の最小化。そのまま重なります。しかも非輪状性がタダで手に入るのが良くて、一般の複体だとここが一番面倒なところです。時間軸があるので考えなくていい。
ただ１次元複体上の最適モース・マッチングは全域木を取るだけで、König の定理を言い換えただけになります。ここまでは語彙の獲得であって、計算は増えない。Joswig–Pfetsch が示したように最適モース・マッチングは２次元以上で NP 困難なので、次元を上げると今度は壊れる。だから普通はここで止まる。
第二段：可換な組に２-セルを貼る
止まらない道があって、それが可換律です。σ₁ と σ₄ が可換だというのは、四角形が閉じるということです。
●─────σ₁────→●
│ │
σ₄ ここを σ₄
│ 貼る │
↓ ↓
●─────σ₁────→●前に「交換律で商を取る」と言った操作は、位相的にはこの面を貼って、二つの経路をホモトピックにすることです。商を取るのではなく、次元を上げて同一視する。
貼ると立方体複体になります。そしてここが本題で、この種の複体は CAT(0) になることが知られています。 Abrams–Ghrist の「状態複体」がまさにこれで、グラフ上を複数のロボットが動く配置空間 ── N台の車両がエリア間を動く、と読み替えられます。可換な動作を並行実行できることが立方体の面に対応する。
CAT(0) だと何が嬉しいか。局所最適が大域最適になる。測地線が一意に存在して、貪欲に降りれば必ず最短に着く。
つまり ── そろばんが効く理由が、そろばんの外から説明できる。 「最小でなくてもいい」と言っていた貪欲法が、実は幾何のおかげで思ったより良い、という保証の出所になります。Ardila–Owen–Sullivant が CAT(0) 立方体複体の測地線を多項式時間で求める算法を出していて、経路計画への応用も既にある。NP 困難のはずのものが、CAT(0) 性のおかげで逃げられる構図です。
第三段：釘＝臨界セル
そしてここが、たぶん一番言いたかったことに繋がります。
モース理論の主張は「臨界セルだけが位相を担い、残りは潰れる」です。これは前に話していた区別そのものですよね。
潰れる ＝ 見かけの制約。並べ方の産物
臨界 ＝ 本物の制約。どう変形しても消えない
ライデマイスターで解ける／解けない、も、釘か詰まりか、も、全部「崩壊可能か臨界か」の一語で書ける。 しかも判定が「担当者に訊く」ではなく「マッチングを組んでみて余るか」になる。申告に依らない、という要件が満たされます。
そして最初のカラーボックスの「板を抜く」── フォアマンの相殺定理は、臨界セル２つが唯一の勾配道で繋がっているときに、両方消せると言っています。板を抜いて長い対角線を引く操作が、まさにそれに見えます。
計算できる数
貼った複体のオイラー標数が、トレースモノイドのメビウス関数として閉じた形で出ます。
μ = Σ (−1)^|C| C は「互いに可換な操作の集合」全体を走る板の上で言えば、同時に走れる断片の組を全部数えて交互和を取る。包除原理そのもので、機械的に計算できます。前に「計数半環で代替案の数＝頑健性」と言っていた量の、位相側の正体がこれだと思います。b₁ が独立な「あちらでもこちらでもよい」の本数＝真の自由度になる。
危ないところも一つ。立方体複体が CAT(0) になるには、リンクがフラッグ複体である必要があります（Gromov の条件）。三つの操作が対ごとに可換なら三つ同時に可換、が要る。配車で成り立つかは自明ではなくて、二台ずつは独立でも三台同時だと駐車場が足りない、みたいな容量制約が入ると破れます。ここは実データで確かめる価値がありそうです。破れていたら、そこが「三体問題的に効いている制約」の在処ということになる。
コードに落とすなら、いま comm 規則で書き換えている場所が、書き換えではなく面として記録される形に変わります。潰す代わりに、次元を上げて残す。意味論を残したいという話だったので、むしろそちらが本筋かもしれません。
%% -*- Mode: Prolog -*-
%% n2n_soroban.pl N対N配車「そろばん」の意味論 (rev.2 離散モース層を追加)
%% SWI-Prolog + library(chr)
%%
%% 板 = 時間展開ネットワーク (T x Area)
%% T = 離散モース関数 (最初から高さ軸になっている)
%% 断片 = 1-セル
%% 玉を繋ぐ = 勾配ベクトル場のペアリング
%% 新規投入 = 臨界セル
%% 可換な組 = 2-セル (貼る。潰さない)
%%
%% rev.1 との違い: 可換律を書き換え規則で消していたのをやめ、
%% 面として記録する。商を取るのではなく次元を上げて同一視する。
:- module(n2n, [run/0, solve/0, report/0]).
:- use_module(library(chr)).
:- dynamic job/5.
:- dynamic maxconc/1.
%% ===========================================================
%% 制約
%% ===========================================================
:- chr_constraint
%% --- そろばん (下段: 何台) ---
frag/5, % frag(Id, From, To, Ts, Te) 未処理の断片
bead/4, % bead(Veh, Area, T, LastFrag) 空き玉
assign/2,
fleet/1,
%% --- 熱帯 (上段: いつ) ---
prec/3, asap/2, alap/2, slack/2,
nail/2, infeasible/2,
%% --- 離散モース層 ---
cell/1, % cell(Id) 1-セル
vpair/2, % vpair(I, J) 勾配ベクトル場
critical/1, % critical(Id) 臨界セル
face/2, % face(I, J) 2-セル
cube/1, % cube([I,J,K]) 3-立方体
link_break/1. % link_break(S) フラッグ条件の破れ
%% ===========================================================
%% (1) そろばん本体 -- 玉の移動 = モース・マッチング
%% ===========================================================
%% 玉を取る = ハッセ図上でペアを組む。臨界セルは増えない。
take @ bead(V, A, T, P), frag(Id, From, To, Ts, Te)
<=> reach(A, T, From, Ts)
| assign(Id, V),
vpair(P, Id),
bead(V, To, Te, Id).
%% 組めない = 臨界セル。ここだけが台数を増やす。
put @ fleet(N), frag(Id, _From, To, _Ts, Te)
<=> N1 is N + 1,
assign(Id, N1),
critical(Id),
bead(N1, To, Te, Id),
fleet(N1).
reach(Area, Tavail, From, Tstart) :-
dh(Area, From, D),
Tavail + D =< Tstart.
%% 非輪状性は T の単調性からタダで手に入る。念のため検査だけ置く。
acyc @ vpair(I, J) ==> job(I,_,_,_,TeI), job(J,_,_,TsJ,_), TeI > TsJ
| infeasible(J, cyclic(I)).
%% ===========================================================
%% (2) 熱帯半環 (+) = max / (x) = +
%% ===========================================================
asap_join @ asap(I, T1) \ asap(I, T2) <=> T2 =< T1 | true.
asap_prop @ asap(I, T), prec(I, J, D) ==> T1 is T + D, asap(J, T1).
alap_join @ alap(I, T1) \ alap(I, T2) <=> T1 =< T2 | true.
alap_prop @ alap(J, T), prec(I, J, D) ==> T1 is T - D, alap(I, T1).
slack_of @ slack(I, _) \ slack(I, _) <=> true.
slack_new @ asap(I, Te), alap(I, Tl) ==> S is Tl - Te, slack(I, S).
%% ===========================================================
%% (3) 釘 (固定X) -- 伝播と検査の境目
%% ===========================================================
%% 下からの押しは積になる (伝播)。上からの蓋は積にならない (ガード)。
%% 釘は代数の外ではなく、この境目に居る。
nail_down @ nail(I, T) ==> asap(I, T).
nail_up @ nail(I, T) ==> alap(I, T).
nail_late @ nail(I, T), asap(I, T2) ==> T2 > T | infeasible(I, late(T2, T)).
nail_dup @ infeasible(I, R) \ infeasible(I, R) <=> true.
%% ===========================================================
%% (4) 立方体複体 -- 可換な組を面として貼る
%% ===========================================================
%% 独立性 (Mazurkiewicz): 資源 (エリア) を共有しなければ可換。
%% 時刻ではなく資源で決まる。これが遠隔交換律 |i-j| >= 2 の実体。
indep(I, J) :-
job(I, F1, T1, _, _),
job(J, F2, T2, _, _),
sort([F1,T1], S1), sort([F2,T2], S2),
intersection(S1, S2, []).
mkface @ cell(I), cell(J) ==> I @< J, indep(I, J) | face(I, J).
%% 対ごとに可換な三つ組 -> 3-立方体
mkcube @ face(I,J), face(J,K), face(I,K) ==> I @< J, J @< K | cube([I,J,K]).
cubedup @ cube(S) \ cube(S) <=> true.
%% Gromov のフラッグ条件。破れたら CAT(0) 性が失われ、
%% 「局所最適 = 大域最適」の保証が消える。
%% 破れの場所 = 三体的に効いている制約の在処。
flagchk @ cube(S) ==> \+ simultaneous_ok(S) | link_break(S).
lbdup @ link_break(S) \ link_break(S) <=> true.
simultaneous_ok(Set) :-
length(Set, N),
( maxconc(K) -> N =< K ; true ).
%% ===========================================================
%% (5) 下界 -- ディルワース (反鎖)
%% ===========================================================
conflict(I, J) :- \+ chainable(I, J), \+ chainable(J, I).
chainable(I, J) :-
job(I, _, ToI, _, TeI),
job(J, FromJ, _, TsJ, _),
dh(ToI, FromJ, D),
TeI + D =< TsJ.
lower_bound(LB, Witness) :-
findall(Ts-I, job(I,_,_,Ts,_), L0),
keysort(L0, L1), pairs_values(L1, Ids),
greedy_antichain(Ids, [], Witness),
length(Witness, LB).
greedy_antichain([], Acc, Acc).
greedy_antichain([I|Rest], Acc, Out) :-
( forall(member(J, Acc), conflict(I, J))
-> greedy_antichain(Rest, [I|Acc], Out)
; greedy_antichain(Rest, Acc, Out)
).
%% ===========================================================
%% (6) 相殺 (Forman) -- 臨界セル二つを唯一の勾配道で消す
%% ===========================================================
%% first-fit 貪欲が正しく走っていれば、候補は空になるのが正常。
%% 出たら実装のバグか、制約の見落とし。自己検証として使う。
tail_of(V, Area, T) :-
findall(Te-Id, (assigned(Id,V), job(Id,_,_,_,Te)), L),
max_member(T-Id, L), job(Id,_,Area,_,_).
head_of(V, Area, T) :-
findall(Ts-Id, (assigned(Id,V), job(Id,_,_,Ts,_)), L),
min_member(T-Id, L), job(Id,Area,_,_,_).
assigned(Id, V) :- find_chr_constraint(assign(Id, V)).
cancel_candidate(V1, V2) :-
tail_of(V1, A1, Te),
head_of(V2, A2, Ts), V1 \== V2,
dh(A1, A2, D), Te + D =< Ts,
findall(V, ( head_of(V, FA, TS), V \== V1,
dh(A1, FA, D2), Te + D2 =< TS ), [V2]).
%% ===========================================================
%% (7) メビウス関数 -- 独立性グラフのクリークの交代和
%% ===========================================================
%% mu = sum over C (-1)^|C|, C は互いに可換な断片の集合
%% 前に「計数半環 = 頑健性」と言っていた量の位相側の姿。
subclique([], []).
subclique([X|Xs], [X|C]) :- subclique(Xs, C), forall(member(Y,C), indep(X,Y)).
subclique([_|Xs], C) :- subclique(Xs, C).
mobius(Mu, Profile) :-
findall(I, job(I,_,_,_,_), Ids0), sort(Ids0, Ids),
findall(C, subclique(Ids, C), Cs),
foldl([C,In,Out]>>( length(C,N), S is (-1)**N, Out is In + S ), Cs, 0, Mu),
msort_profile(Cs, Profile).
msort_profile(Cs, Profile) :-
findall(N, (member(C,Cs), length(C,N)), Ns),
msort(Ns, Sorted), clumped(Sorted, Profile).
%% ===========================================================
%% データ
%% ===========================================================
area_idx(a,1). area_idx(b,2). area_idx(c,3). area_idx(d,4).
area_idx(e,5). area_idx(f,6). area_idx(g,7).
dh(A, B, D) :- area_idx(A,I), area_idx(B,J), D is abs(I-J).
jobs :-
retractall(job(_,_,_,_,_)),
assertz(job(j1, a, c, 7, 9)),
assertz(job(j2, c, e, 9, 11)),
assertz(job(j3, b, d, 7, 10)),
assertz(job(j4, a, b, 8, 10)),
assertz(job(j5, d, a, 11, 14)),
assertz(job(j6, e, c, 12, 14)),
assertz(job(j7, b, e, 11, 15)),
assertz(job(j8, f, g, 7, 10)), % j1, j3 と三つ組で独立
retractall(maxconc(_)),
assertz(maxconc(2)). % 同時稼働の上限 -> フラッグ条件を破る
%% ===========================================================
%% 駆動
%% ===========================================================
solve :-
fleet(0),
findall(I, job(I,_,_,_,_), Ids0), sort(Ids0, Ids),
forall(member(I, Ids), cell(I)), % 複体を組む
findall(Ts-Id, job(Id,_,_,Ts,_), L0),
keysort(L0, L1), pairs_values(L1, Order),
forall(member(Id, Order), % そろばんを走らせる
( job(Id,F,T,Ts,Te) -> frag(Id,F,T,Ts,Te) ; true )).
report :-
find_chr_constraint(fleet(UB)),
lower_bound(LB, W),
findall(I, find_chr_constraint(critical(I)), Cr),
findall(P, find_chr_constraint(vpair(_,_)), Vp),
findall(F, find_chr_constraint(face(_,_)), Fc),
findall(Q, find_chr_constraint(cube(Q)), Cu),
findall(B, find_chr_constraint(link_break(B)), Lb),
length(Cr,NCr), length(Vp,NVp), length(Fc,NFc), length(Cu,NCu),
mobius(Mu, Prof),
findall(V1-V2, cancel_candidate(V1,V2), Can),
format("~n== 台数 ==~n"),
format(" 上界 (玉の投入数) : ~w~n", [UB]),
format(" 下界 (反鎖) : ~w 証拠 ~w~n", [LB, W]),
( UB =:= LB -> format(" -> 一致。最適確定。~n")
; D is UB-LB, format(" -> 差 ~w。改善余地あり、または下界が緩い。~n",[D]) ),
format("~n== モース ==~n"),
format(" 臨界セル : ~w ~w~n", [NCr, Cr]),
format(" ペア : ~w~n", [NVp]),
format(" 検算 : 臨界 ~w = 台数 ~w~n", [NCr, UB]),
format("~n== 立方体複体 ==~n"),
format(" 2-セル : ~w~n", [NFc]),
format(" 3-立方体 : ~w ~w~n", [NCu, Cu]),
( Lb == [] -> format(" フラッグ条件 : OK (CAT(0) 期待可)~n")
; format(" フラッグ条件 : 破れ ~w~n", [Lb]),
format(" -> 局所最適 = 大域最適 の保証は無い~n") ),
format("~n== 不変量 ==~n"),
format(" メビウス mu : ~w~n", [Mu]),
format(" クリーク分布: ~w~n", [Prof]),
format("~n== 自己検証 ==~n"),
( Can == [] -> format(" 相殺候補なし (正常)~n")
; format(" 相殺候補 ~w <- 見落としの疑い~n", [Can]) ).
run :- jobs, solve, report.