Max-Plusによる断片ブレイド復元（Claude）②🧠
今度はClaudeに聞いてみる。方向性はいいみたいだね。
あー、そういうことか。組み紐だったんですね。
えーとね。 配送によっては、時間自由なのがある。
それは、ライデマイスターが自由っていうか、 上下に移動できるんだよ。
あ、それは別種の自由ですね。区別すべきものが二つあった。
ライデマイスター的自由 … 交差そのものが偽物。消せる。制約が実在しない。
上下移動の自由 … 交差は本物だが、その時刻が決まっていない。制約は実在するが、位置が浮いている。
前者は「無かったことにできる」、後者は「必ず起きるが、いつ起きるかは未定」。全然違う。
代数的にはこれ、遠隔交換律 σᵢσⱼ = σⱼσᵢ（|i−j| ≥ 2）そのものです。ここが効くところで、これはライデマイスター移動ですらない。ただの平面イソトピー ── つまり紐を持ち上げも潜らせもせず、板の上でビーズをずらしただけ。図として同一なんです。
A B C D E
T= 8 | \ / | | σ₂ ← 上の壁（B を共有）
T= 9 | / \ | |
T=10 | | | | | ┐
T=11 | | | \ / │ σ₄ は無関係、すり抜ける
T=12 | | | / \ │ σ₁ はこの帯を自由に滑る
T=13 | | | | | ┘
T=14 | \ / | | σ₂ ← 下の壁（B を共有）滑れる範囲は無限ではなく、位置を共有する交差にぶつかったら止まる。しかもその壁は当の配送の属性ではなく、隣に何が居るかで決まる。時間余裕が案件の性質ではなく構造から出てくる、というのが良いところです。
で、ここからが実務側に刺さると思うんですが。
配車実績は過剰に書きすぎている。 記録には全順序が入っているのに、実在するのは半順序だけ。σ₁σ₄ と書いた記録と σ₄σ₁ と書いた記録は同じ事象なのに、生データ上は別の事例に見える。このまま ILP に食わせると、差でないものを説明する規則を誘導してしまう。②のコスト差帰納で偽の因果が湧く経路がここにある。
前処理として交換律で商を取る。
それだけで仮説空間がかなり落ちるはずです。
枠組みとしては トレースモノイド（Mazurkiewicz）、幾何的には Viennot の heaps of pieces が素直に効きます。時間自由な配送＝まだ着地していない駒で、落として何かに乗るまで下がる。全部落としきった形が Cartier–Foata 正規形＝ASAP、逆向きが ALAP、その差が余裕（フロート）。クリティカルパスが群論側から勝手に出てくる格好です。
模型のほうも、これで一段上がりますね。固定クランプと滑るビーズを混ぜる。 時間指定ありは T の棚に留める、自由なやつは紐に通すだけ。で、板を立てて叩く。落ち着いた形が ASAP 解。物理リラクゼーションソルバとして動く。
あと ── 熟練者の腕は、滑る駒をどこに置くかなんじゃないですか。固定の駒は誰が組んでも同じ。自由な駒を緩衝材としてどこに配るかで、乱れが来たときの吸収量が変わる。板が硬く見えるのは滑る駒を使い切った状態で、そこから先は切断（ペンチ）しかない。
十月以降の話とも繋がりそうです。滑り代が先に食い潰され、可換な組が残っていない状態で外乱が来る。
そうそう。それで、恒等置換の部分なら、「足せる」「かぶせる」ことができるんだ。
そこが要ですね。「積の連結なし」の逆条件が出てきた。
写真の板には積の連結なしと書いてありましたが、あれは無条件の禁止じゃなく、繋げる場所が限られているという話だったわけですね。任意の時刻で切ったら両端の置換が食い違うから繋げない。でも恒等置換のところなら端が揃っているので、そこだけは合成が定義できる。継ぎ目です。
A B C D E
T= 9 | \ / | |
T=10 | / \ | |
T=11 | | | | | ┐
T=12 | | | | | │ ← 恒等置換の帯 ＝ 継ぎ目
T=13 | | | | | ┘
T=14 | | | \ / |
T=15 | | | / \ |で、「足せる」と「かぶせる」は別方向ですね。
足すは縦方向。帯を広げて、そこに新しい組み紐を挿入する。T=11〜13 に何を入れても、T=14 以降は一切影響を受けない。純組み紐群 P_n が正規部分群だからで、下流の置換が変わらないことが代数的に保証されている。再計画不要という主張が、ここでは定理として出る。
かぶせるは奥行き方向。これが効いてくるところで ── 最初の「奥は役に立たないね 笑」が、ここで裏返る。
射影で奥行きが完全に潰れるということは、奥行きには組み紐の情報が一切ないということです。情報がないから、そこに何を置いても図が変わらない。つまり奥行きは幾何としては死んでいるが、容量としては生きている。同じ帯に何本重ねてもブレイド語は不変。積み合わせが「順序を触らずに載せられる」操作である理由が、これで構造から出てきます。
32ケースの話に直結しますよね。閾値に届かせるために積み合わせたいが、経路や順序は崩したくない。探すべきは恒等置換の帯で、そこは定義上いくらでも載る。しかも記録から自動で検出できる。
一点だけ、混ぜると危ない区別があります。
自明な組み紐（交差ゼロ）… 紐が並行に降りているだけ。何を入れても何を載せても自由。
恒等置換（純組み紐）… 位置は元に戻っているがその間に絡んでいる。
後者は「T=11 と T=13 で車両配置は同一」なのに、間に相互制約が生きている状態です。端が揃っているので連結はできるが、挿入は自由じゃない。載せたものが既存の絡みを引き継ぐ。
実務語だと「配置は戻っているように見えるが、その区間で車両同士が拘束し合っている」。伝票上は空きに見えて、実際には積めない帯。ベテランが説明しにくいのはたぶんこの区別で、板の上では純組み紐か自明かは一目で分かるが、表では両方とも同じ空白に見える。
そうすると前回の「滑る駒をどこに置くか」がもう一段はっきりしますね。
時間自由な配送を滑らせると、恒等置換の帯は作れるし潰せる。ASAP に全部落とすと下が詰まって上に長い空白、ALAP なら逆。どちらも継ぎ目としては使いにくい。熟練者が中途半端な位置に置いているように見えるとしたら、それは継ぎ目を意図的に開けているんじゃないですか。明日の飛び込みを縫い込む場所として。
だとすると、これは規則としては絶対に言語化されない類のものです。「なぜここに置いたか」を訊いても本人は答えられない。まだ存在しない仕事のために空けているので。
板の上でなら見える。ILP に食わせるなら、継ぎ目の残量を特徴量にする手はありそうです。
通じてるかな
｜ ｜ X
X ｜ ｜
を足す？重ねることはできるの
X
X
になる
通じてます。読み方はこうですね。
【元の２つ】 どちらも σ₁（同じレーン、時刻だけ違う）
braid P braid Q
T=1 | | T=1 X ← 先に交差
T=2 X T=2 | | ← 後は素通り
↑遅れて交差互いの空き段に相手の交差が落ちるので、２段に収まる。
【重ねた結果】
T=1 X
T=2 X = σ₁²できます。 ただし前回の「かぶせる」とは別物です。ここを分けないと危ない。
◆ 別レーン（σ₁ と σ₃） ◆ 同レーン（σ₁ と σ₁）
T=1 X | | T=1 X
T=2 | | X T=2 X
↓ 重ねる ↓ 重ねる
T=1 X X T=1 X
← １段に収まる T=2 X ← ２段のまま別レーンは段数が減る。奥行き方向に本当に同居している。同レーンは減らない。並べているのではなく、ただ縦に積んだだけです。
得たものは圧縮ではなく 実行可能性 ── ２つの仕事が２段の窓に収まった。失ったものは、両方が持っていた１段ぶんの遊びです。窓は満杯になり、もうどちらも滑れない。
そして σ₁²。置換としては恒等（入れ替えて、戻った）。でも組み紐としては自明じゃない。
つまり前回の「伝票上は空きに見えるが実際には積めない帯」を、重ねる操作そのものが作り出している。空き段を使い切ると、非自明な恒等帯が生まれる。
ここで向きが効きます。
同じ向きに２回 ２回目を逆に
\ / \ /
\ \
/ \ / \
\ / \ /
\ / ← over/under が逆
/ \ / \
σ₁² ほどけない σ₁σ₁⁻¹ = 1 消える段数も、始点も終点も、置換も全部同じ。違うのは交差点の１ビットだけ。それで結果が正反対になる。
最初の「奥行きは潰れて、残るのは over/under の１ビット」が、ここで初めて仕事をしましたね。あのビットは、重ねた結果が恒久的な拘束になるかきれいに消えるかを決めている。
実務側の対応物が何かは僕には判断がつきませんが、構造としてはこう読めます。同じ組を２回触るとき、２回とも同じ側を通せばその２台は以後セットとして拘束され続け、逆側に戻せば独立に戻る。記録上はどちらも「入れ替えて戻した」としか残らない。
詰め込むほど硬くなる理由が二段構えになりますね。遊びが減るのが一段目、ほどけない絡みが溜まるのが二段目。後者は詰め込みをやめても自然には戻らない。
なるほど。よくわからんが（笑）
でね、Xには縦に自由に動かせるXと、動かせないXがあるの。
それで釘が打たれるわけですね。動かない X が二種類あるはずで、ここは分けたほうがいいと思います。
釘の X … 時間指定。外から打ち込まれている。周りが何であろうと動かない。
詰まっている X … 本当は自由だが、隣が邪魔で動けない。周りが空けば動く。
板の上ではどちらも「動かない」に見えるけど、性質は正反対です。前者は交渉の余地なし、後者は場所を空ければ解ける。
A B C D E
T= 7 | | | | |
T= 8 | \ / | | ★釘（B-C 指定）
T= 9 | / \ | |
───────────────── ← B と C にとっては壁
T=10 | | | | |
T=11 | | | | | ☆自由X はこの帯の中だけ滑る
T=12 | | | | |
─────────────────
T=13 | \ / | | ★釘
T=14 | / \ | |釘が効くのは自分のレーンだけで、D・E の X はこの壁を素通りします。だから釘の重みは本数じゃなく、どのレーンに、板のどのへんに打たれたか。端に近い釘はほぼ無害、真ん中の釘は上下両方の滑り代を殺す。同じ「時間指定１件」でも被害額が全然違う。
で、釘は動かせないけど、その隙間のどこに継ぎ目を開けるかは選べる。自由な X を上に寄せるか下に寄せるかで、恒等帯の位置が変わる。釘が骨格を決めて、自由な X が肉付けをして、その結果として継ぎ目がどこに開くか決まる、という三層構造ですね。
繁忙期に硬くなるのは、釘の密度が上がって帯が細切れになるからです。帯が２段を切ると、そこにはもう何も挿せない。積み合わせも縫い込みもできない。32ケースに届かせようにも、載せる場所が構造的に消えている。滑り代を使い切るより前に、そもそも帯が無くなる。
一番おいしそうなのはここで。
記録上「時間指定」になっている X のうち、本当に釘なのはどれか。 これはデータに書いてない。伝票は全部同じ顔をしている。でも実務では、絶対に動かせない指定と、電話一本で前後する指定がありますよね。ベテランは後者を見分けて、そこを最後の逃げ場に取ってある。
前に話した「絡んで見えるが解ける／解けない」は横方向の判定でした。これはその縦版です。
横 … 見かけの交差か、本物の交差か
縦 … 見かけの釘か、本物の釘か
どちらも「申告された制約 vs 実在する制約」の切り分けで、しかも実績を見れば分かる。過去に動いたことのある釘は釘じゃない。動いたことがない釘は、本物か、あるいは誰も試したことがないだけか。この二つが残る。
後者、けっこう混じってる気がしませんか。
よし。これがN対N配車。
各Tでの上段の点は発地エリアを表す。
各Tでの下段は着地
どのXが固定なのか、自由なのかは明確。
最初は紐が断片的に張られている。
どの紐どうしを結んでいけば、
少ない本数になるか（最小でなくてもいい）を
即座に計算するそろばんを作りたい。
こういう計算が可能な代数体系を探している。
名前がついています。最小パス被覆、そして実務名では最小フリート問題。
歴史的にはこれ、Dantzig と Fulkerson が 1954 年にタンカー配船で解いた問題そのものです。「決められた運航スケジュールを満たす最小隻数」──断片的な航海を繋いで何隻で回るか。RAND 時代の初期 OR で、しかも当時すでに「解ける」と分かっていた。70年前に片がついている問題の上に立てるのは、たぶん朗報です。
板はすでにネットワークになっている
T × エリアの格子は、OR でいう時間展開ネットワークそのものです。作図の都合でそうなったのではなく、この問題の正準形がそれです。
節点 = セル (T, エリア)
断片（紐）= 下限１のアーク。必ず１台通さねばならない
縦の空白 = 手待ちアーク。容量無限、下限ゼロ
回送 = 斜めのアーク
で、**最小フロー（下限付き）**を流す。流量 = 台数。これで終わりです。
そろばんの玉
計算の実体はこうなります。
A B C D E
T= 7 ●● ● ─ ● ─ ● = そのセルで空いている車両
T= 8 ● ─ ●● ● ─
T= 9 ● ●● ● ─ ●
T=10 ●● ● ─ ●● ●断片が１本来たら、
発地セルに玉があるか見る
ある → 取る。着地セルに置く。台数は増えない
ない → 新しい玉を投入する。台数 +1
投入した玉の総数が答えです。全体を解き直さない。触るのは２セルだけ。これがそろばんの機構で玉の物理的な移動がそのまま計算になっています。
最小でなくてもいい という条件がここで効きます。この貪欲法は一般には最適ではありませんが、開始時刻順に処理すればエリアが単一のとき最適、回送時間が三角不等式を満たす範囲では実用上かなり良い上界を出します。
読みは二つある
そろばんの価値は、上界と下界を別々に読めることにあると思います。
上界 = 玉の投入数（貪欲の結果）
下界 = 最大反鎖 ── どの二本も繋げない断片の最大集合
下界のほうが本質的です。ディルワースの定理で、最小の鎖被覆数 = 最大反鎖の大きさ。つまり答えは解かなくても読める。時間的に重なっているか、空間的に届かないか、どちらかで繋げない断片を数え上げるだけ。板の上なら横に一本線を引いて、その線を跨いでいる紐を数える作業になります。
そして両者の差が、そのまま改善余地の見積もりになる。一致していれば最適が確定していて、それ以上考える必要がない。ベテランの案が最適かどうかを、最適解を求めずに判定できます。
探している代数体系
半環上の行列代数です。同じ一枚の行列を、三通りの半環で読みます。
半環 積の意味 読めるもの
ブール (∨, ∧) 繋げるか 到達可能性。推移閉包で多段
熱帯 (max, +) いつなら繋げるか 最早時刻、ASAP
熱帯 (min, +) 逆向き 最遅時刻、ALAP
計数 (+, ×) 何通りか 代替案の数＝頑健性
行列は一つ、半環を差し替えるだけで違う量が出てくる。しかもどれも同じ積の規則で走るので、そろばんとしては一種類の操作しか要りません。
そして ASAP と ALAP の差が、そのまま滑り代です。前に話した自由 X の可動範囲は、熱帯半環で二回評価した引き算として出ます。クリティカルパスは差がゼロの断片。
台数の勘定だけはフロー側（ホフマンの循環定理／ディルワース双対）で、これは半環では出ません。ここは別建てになります。
自由な X の扱い
固定の X から先に打ち込んで骨格を決め、自由な X は未確定のまま玉を待たせる。他の断片が来たときに、その玉が使えるなら滑らせて合わせる。
これが良いのは、自由な X が投入判断を先送りできる点です。玉がないときにすぐ +1 せず、「近くに自由な X があれば滑らせて間に合わせる」を一手挟める。継ぎ目の残量が、そのまま吸収余力として読めます。
効かなくなる条件
一点だけ、はっきり線を引いておいたほうがいいと思います。
積み合わせを入れた瞬間に、この構造は壊れます。 一台が同時に複数の断片を持てるようになると、フロー問題ではなくなって配送計画問題（NP困難）に落ちます。そろばんは動かなくなる。
写真の板の「積の連結なし」は、だからたぶん制限ではなく設計判断ですね。それを外していないからこの板は計算装置たりうる。
32ケースの閾値は本来この外側の話なので、混ぜないほうがいい。まず積み合わせなしで最小台数を出し、その解の上で、恒等帯（玉のあるセル）に載せられるものを後から探すという二段構えなら、両方とも計算可能なまま保てます。玉の数がそのまま「載せられる場所」の在庫になっているので、二段目の入力は一段目の出力がそのまま使えます。
そろばんを作る順序としては、玉の移動だけの貪欲を先に組んで、次に横線を引く下界読み、最後に不一致箇所だけ増加道で直す、が素直だと思います。三つ目は板の上でも手でできます ── 繋ぎ替えの連鎖を一本たどるだけなので。
えーと、つまり... トロピカルで組めるのーーー？不思議だなぁ
組めます。しかも理由はほとんど拍子抜けするくらい単純で、待ち合わせが max、所要時間が + だから、それだけです。
断片B の開始可能時刻 =
max( 断片Aの終了, 断片A'の終了, ... ) + 回送時間
└──── 全部揃うまで待つ ────┘ └ 足す ┘現場語なら「揃ったら出る」。これを式として書いた瞬間、もう (max, +) 半環です。人間が選んだのではなく、待ち合わせという行為がその代数を持っている。
不思議さの正体はたぶん「なぜ分配法則が成り立つのか」で、これは絵にすると当たり前に見えます。
max(a, b) + c = max(a+c, b+c)
a ──────┐
├─ 遅いほう ── +c ──→ 出発
b ──────┘
a ── +c ──┐
├─ 遅いほう ──→ 出発
b ── +c ──┘全員に同じ時間を足しても、どっちが遅いかは変わらない。 分配法則の中身はこれだけです。時間を平行移動しても順序が壊れない、という物理的にごく当然の事実が、代数の骨格になっている。
逆に言うと、これが崩れる状況では熱帯半環は使えません。たとえば「遅れると回送ルートが変わって所要時間も変わる」なら c が a, b に依存してしまい、分配法則が死ぬ。使える条件がはっきりしているのは良いところだと思います。
もう一段、面白いところがあって。
通常の代数 Σ (経路上の Π) → 経路の本数を数える
熱帯代数 max(経路上の Σ) → いちばん遅い経路を選ぶ
↑ ↑
足し算 掛け算 の位置は同じ行列の積の書き方は完全に同一で、+ と × に何を入れるかだけが違う。だから前に挙げた四つの半環が、同じそろばんの上で走るわけです。玉の動かし方は一種類、読み方だけ差し替える。
むしろ驚くべきは、普通の掛け算と足し算のほうも「経路を辿る」という同じ骨格の一例にすぎなかったことかもしれません。熱帯が変なのではなく、算数のほうが特別扱いされすぎていた。
実用の裏付けもあります。この分野は Cuninghame-Green が1960年代に確立していて、離散事象システムとして鉄道ダイヤやパリの地下鉄の運行解析に実際に使われています。フランス（INRIA）の研究者たちが max-plus 代数として体系化した流れで、乗り継ぎのある時刻表はまさに「揃ったら出る」の塊なので、ど真ん中の応用先です。
そして固有値が周期になります。定常運行のサイクルタイムが行列の固有値として出てくる。配車で言えば回転率の理論限界です。ダイヤが破綻するかどうかを、シミュレーションではなく固有値の比較で判定できる。
念のため、効かない場所も。
時刻 → 熱帯で出る（ASAP, ALAP, 滑り代, 臨界断片）
台数 → 出ない。ここはフロー／ディルワース側
前回の分担のままです。そろばんとしては、**上段が熱帯（いつ）、下段がフロー（何台）**の二階建てになる。
一つ気になっているのは、固定 X が熱帯半環では素直に書けないことです。max(...) は「これ以降」しか言えないので、「T=10 ちょうど」という指定は下からの押しとして入れられても、上からの蓋が入らない。ここは (min, +) 側を同時に走らせて挟むか、あるいは別の扱いが要りそうです。釘の代数的な居場所は、まだ僕にも見えていません。
ディルワースって？
1950年、Robert Dilworth の定理です。半順序集合についての、たった一行の主張。
最小の鎖被覆数 ＝ 最大反鎖の大きさ
配車に翻訳すると、こうなります。
半順序 … 断片 a ≺ b ＝「a の後に b を同じ車がやれる」
鎖 … 一列に繋がる断片の並び ＝ 一台の一日
反鎖 … どの二つも繋げない断片の集合 ＝ 必ず別々の車が要る
鎖被覆 … 全断片を鎖に分ける ＝ 配車案
つまり 最小台数 ＝ 「どの二つも繋げない断片」の最大個数。
片方は当たり前です。互いに繋げない断片が７本あるなら、７台要る。下界として誰でも納得する。
Dilworth が言っているのは、その下界が必ず達成できるということ。「７本の互いに繋げない断片が最大」なら、必ず７台で組める。余分は一台も要らない。
これが非自明なところで、普通この手の下界は緩いものです。ここでは常に一致する。
A B C
T= 7 ●━━━┓
T= 8 ● ┃ ●━━━┓
T= 9 ┗━━● ┃ ●━━━┓
T=10 ● ┗━━● ┃
T=11 ┗━━●これは一本の鎖 ＝ 一台で回れる。
T= 8 ●━━┓ ●━━┓ ●━━┓
T= 9 ┗━● ┗━● ┗━●これは反鎖。時間が丸かぶりで、どれも繋げない。３本あるから３台。
実務的にいちばん効くのは、証明書が出ることだと思います。
「７台必要です」と言うと、必ず「本当か、もっと詰められるだろう」と返ってくる。Dilworth は反論不能の答えを持っています ── この７本を見てください、どの二つも同じ車ではできません。相手が自分で確かめられる形で、最適性が示せる。
そして貪欲解が８台で反鎖が７本なら、差は１。まだ縮む余地がちょうど１台ぶんある、と分かる。どこを直せばいいかは分からなくても、探す価値があるかどうかは判定できます。これは計算量的にも安い判定です。
注意点を二つ。
推移律が要ります。 a→b が可能、b→c が可能なら、a→c も可能でなければ半順序になりません。回送時間が三角不等式を満たさない（A→B→C より A→C のほうが遠い）と成立が崩れます。実地の道路網ならたいてい大丈夫ですが、確認は要ります。
単一エリアなら、反鎖は「横線を跨ぐ本数」ですが、複数エリアだと足りません。 時間が重なっていなくても、遠すぎて回送が間に合わなければ、繋げない。だから真の反鎖は横線の本数以上になります。前に「線を引いて数える」と言ったのは単純化しすぎでした。
系譜としては König の二部マッチング定理と等価で、そこから最大流最小カットに繋がります。だから前回の「フロー側」と別建てに見えたものは、実は同じ定理の別の顔です。
そろばんの上では、玉の投入数が上界、反鎖の大きさが下界。両端から挟んで、一致したら終わり。
まとめて。３行くらいで
板 ＝ 時間展開ネットワーク。断片を繋いで鎖にする問題で、正体は最小パス被覆（Dantzig–Fulkerson の最小フリート問題です。1954年に解決済み）。
そろばんの機構は玉の移動だけ。発地セルに玉があれば取って着地セルへ、なければ投入して +1。投入総数が台数。
読みは二階建て。時刻・滑り代は熱帯半環（max,+ と min,+ で挟む）、台数はフロー／ディルワースで上界と下界を挟んで一致したら最適確定。
未解決として残っているのは、固定 X（時刻ちょうどの指定）の代数的な居場所と、積み合わせを入れた瞬間にこの構造が壊れることの二点です。
逆にいうと、ここまで代数で処理できるから、細かいところはプログラム処理でいけそうだね
そうですね。しかも分担の線が「大きい/細かい」ではなく、**「不変量を決める側」と「それを壊さずに動く側」**に引けているのが効くと思います。
代数側が出しているのは仕様です。
何を保存すべきか（置換の整合、推移律、可換な組は同一視）
何を計算すれば足りるか（玉の在庫、ASAP/ALAP の差、反鎖の大きさ）
どこで止まってよいか（上界＝下界なら探索不要）
プログラム側は、この枠の中ではループで済みます。断片１本あたり定数時間で、ソルバが要らない。ILP も CP-SAT も呼ばずに即応する、という当初の「そろばん」要件がここで満たされる。
一番大きいのは、自己検証が入ることじゃないでしょうか。
貪欲解を出したあと、同じデータから反鎖を数えて下界を出す。一致すれば最適が確定、ずれていれば差の分だけ改善余地。正解データなしに、実行時に自分で答え合わせができる。
暗黙知の抽出みたいに「何が正しいか」を外から与えられない領域で、これはかなり珍しい性質です。バグと「そもそも最適じゃない解」を切り分けられる。テストが書ける。
もう一つ、可換な組を同一視してから ILP に渡せるので、②の帰納に入る前にノイズが落ちます。前処理の正当性が代数で保証されている、というのは実装上ありがたいはずです。
ただ、線の引きどころは注意が要ると思っていて。
積み合わせは「細かいところ」ではありません。 入れた瞬間に鎖でなくなりNP困難側に落ちる。ここだけはプログラムでどうにかなる話ではなく、前に話した二段構え（まず台数を確定し、その解の上で恒等帯に載せる）で外に出しておく必要があります。構造を守るための設計判断なので、実装者が良かれと思って一体化すると全部崩れます。
固定 X は逆に、実装では簡単です。上下の壁として区間を切ればいい。代数的な居場所が見つかっていないだけで、プログラム側では素直に書ける。ここは「代数で解けないからプログラムに落とす」という、正しい意味での分担になります。
結果的に、Prolog/CHR とかなり相性が良い形に収まった気がします。玉の在庫は制約ストア、断片の到着は制約の追加、繋ぎ替えは伝播。ライデマイスターや可換律は書き換え規則そのものです。前回の Fable の件と地続きになりますね。
では意味論として残しておきたいので、
CHR-Prologでサンプルコード書いて。
意味論を残す形なので、走らせて確かめられるものにしました。書きながら一つ分かったことがあります。
釘の居場所が見えました。 熱帯半環で書けなかったのは、上からの蓋が積の演算にならないからでした。CHR に落とすと、nail_down は伝播規則、nail_up も伝播規則、でも nail_late はガードになる。つまり釘は代数の外に落ちたのではなく、伝播と検査の境目に居る。半環が計算する側、ガードが「計算をやめて失敗する」側で、釘は後者にしか書けない量だった、ということだと思います。
CHR が (max,+) を素直に表現できるのも、書いてみると当たり前で、
asap_join @ asap(I,T1) \ asap(I,T2) <=> T2 =< T1 | true. % ⊕ = max
asap_prop @ asap(I,T), prec(I,J,D) ==> T1 is T+D, asap(J,T1). % ⊗ = +冪等和がそのまま simpagation です。値が単調増加で有界なので停止も保証される。半環を差し替えるなら、この二行を書き換えるだけで済みます。
意味論として残す観点で、線を引いておいた箇所を挙げておきます。
take と put の順序が全て。 テキスト順が優先度なので、take を先に書いてあることが「玉があれば使う」の意味です。ここを入れ替えると別のアルゴリズムになる。first-fit を best-fit にするなら take の前に一枚挟む形で、貪欲の質だけが変わり構造は変わりません。
job/5 を CHR ではなく plain Prolog にしてあります。 frag/5 は消費されるので下界計算の入力が残らなくなるためです。動く側と静的な側を分けておかないと上界と下界を同じデータから読むという肝心の性質が壊れます。
lower_bound/2 は証拠を返します。 数字だけでなく、どの断片が互いに繋げないかのリストが出る。「本当に７台要るのか」に対して相手が自分で確かめられる形になっているのが、この定理を使う理由でした。
seams/1 は残玉を列挙するだけにしてあります。積み合わせをここから先に進めると鎖でなくなるので、境界として意図的に浅くしてあります。
⑥ の可換律は独立したモジュールです。comm は「レーン番号の小さいほうを前に寄せる」向きなので、逆転数が単調減少して停止します。実績列を正規形に落としてから ILP に渡す前処理用。
まだ埋まっていないのは、prec/3 を実績からどう起こすかです。断片の連鎖から自動生成できますが、それは「実際にそう繋がっていた」であって「そう繋がねばならなかった」ではない。理想計画側と実績側で二本走らせて差を取る、という②の話に戻ってきます。
%% -*- Mode: Prolog -*-
%% n2n_soroban.pl N対N配車「そろばん」の意味論
%% SWI-Prolog + library(chr)
%%
%% 板 = 時間展開ネットワーク (T × Area)
%% 断片 = frag/5 下限1のアーク
%% 玉 = bead/3 そのセルで空いている車両
%% 繋ぐ = 玉を取って着地セルに置く
%% 投入 = 玉が無い → fleet +1
%%
%% 二階建て: 上段 = 熱帯半環 (いつ) 下段 = 玉の在庫 (何台)
:- module(n2n, [run/0, solve/0, report/0]).
:- use_module(library(chr)).
:- dynamic job/5. % 静的な断片表 (CHR ストアとは別に保持)
:- dynamic dh/3. % 回送時間
%% ===========================================================
%% 制約
%% ===========================================================
:- chr_constraint
frag/5, % frag(Id, FromArea, ToArea, Ts, Te) 未処理の断片
bead/3, % bead(Veh, Area, T) 空き玉
assign/2, % assign(Id, Veh)
fleet/1, % fleet(N)
nail/2, % nail(Id, T) 固定X (時刻指定)
prec/3, % prec(I, J, D) I の後 D 空けて J
asap/2, % asap(Id, T) (max,+) 前進
alap/2, % alap(Id, T) (min,+) 後退
slack/2, % slack(Id, S) 滑り代
infeasible/2.
%% ===========================================================
%% ① そろばん本体 ── 玉の移動だけ
%% ===========================================================
%% 発地セルに届く玉があれば取る。台数は増えない。
take @ bead(V, A, T), frag(Id, From, To, Ts, Te)
<=> reach(A, T, From, Ts)
| assign(Id, V),
bead(V, To, Te).
%% 無ければ投入。ここだけが台数を増やす唯一の規則。
put @ fleet(N), frag(Id, _From, To, _Ts, Te)
<=> N1 is N + 1,
assign(Id, N1),
bead(N1, To, Te),
fleet(N1).
reach(Area, Tavail, From, Tstart) :-
dh(Area, From, D),
Tavail + D =< Tstart.
%% 注: take が先に書いてあるので first-fit。
%% best-fit にするなら「Tavail 最大の玉」を選ぶ規則を一枚挟む。
%% 最小でなくてよい要件なので既定は first-fit。
%% ===========================================================
%% ② 熱帯半環 ── ⊕=max / ⊗=+ を規則として書く
%% ===========================================================
%% ⊕ = max : 同じ節点に来た値は大きいほうだけ残す (冪等和)
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).
%% 双対 (min,+)
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).
%% 滑り代 = ALAP - ASAP。0 なら臨界断片。
slack_of @ slack(I, _) \ slack(I, _) <=> true.
slack_new @ asap(I, Te), alap(I, Tl) ==> S is Tl - Te, slack(I, S).
%% ===========================================================
%% ③ 釘 (固定X) ── 半環では書けない部分
%% ===========================================================
%%
%% (max,+) は「これ以降」しか言えない = 下からの押し。
%% 上からの蓋は積にならないので、ガードとして入る。
%% 代数の外に落ちるのではなく、伝播と検査の境目に居る。
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.
%% ===========================================================
%% ④ 下界 ── ディルワース (反鎖 = 必ず別々の車)
%% ===========================================================
%% 衝突グラフのクリークは常に反鎖なので、貪欲クリークでも
%% 有効な下界になる (緩いことはあっても、間違うことはない)。
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)
).
%% ===========================================================
%% ⑤ 継ぎ目 ── 恒等帯の在庫
%% ===========================================================
%% 残った玉 = そのセルで空いている車両 = 積み合わせを載せられる場所。
%% 32ケース閾値の話は、ここから先の第二段。
seams(Seams) :-
findall(A-T, find_chr_constraint(bead(_, A, T)), Raw),
msort(Raw, Seams).
%% ===========================================================
%% ⑥ 前処理: 可換律による商 (組み紐側)
%% ===========================================================
%% 実績記録は全順序で書かれているが、実在するのは半順序。
%% |i-j| >= 2 の交差は入れ替えても同じ事象 → 正規形に落として
%% 「差でないもの」を ILP に食わせない。
:- chr_constraint sig/3. % sig(Seq, Lane, Sign) Sign = 1 / -1
comm @ sig(S1, I, A), sig(S2, J, B)
<=> S1 > S2, J - I >= 2
| sig(S2, I, A), sig(S1, J, B).
inv @ sig(S1, I, 1), sig(S2, I, -1)
<=> abs(S1 - S2) =:= 1
| true.
%% ===========================================================
%% データ
%% ===========================================================
facility :-
retractall(dh(_, _, _)),
forall(member(A, [a, b, c, d, e]), assertz(dh(A, A, 0))),
assertz(dh(a, b, 1)), assertz(dh(b, a, 1)),
assertz(dh(b, c, 1)), assertz(dh(c, b, 1)),
assertz(dh(c, d, 1)), assertz(dh(d, c, 1)),
assertz(dh(d, e, 1)), assertz(dh(e, d, 1)),
assertz(dh(a, c, 2)), assertz(dh(c, a, 2)),
assertz(dh(b, d, 2)), assertz(dh(d, b, 2)),
assertz(dh(c, e, 2)), assertz(dh(e, c, 2)),
assertz(dh(a, d, 3)), assertz(dh(d, a, 3)),
assertz(dh(b, e, 3)), assertz(dh(e, b, 3)),
assertz(dh(a, e, 4)), assertz(dh(e, a, 4)).
%% job(Id, 発地, 着地, 開始T, 終了T)
jobs :-
retractall(job(_, _, _, _, _)),
assertz(job(j1, a, c, 7, 9)),
assertz(job(j2, c, e, 9, 11)), % j1 から直結できる
assertz(job(j3, b, d, 7, 10)), % j1 と丸かぶり
assertz(job(j4, a, b, 8, 10)), % これも重なる
assertz(job(j5, d, a, 11, 14)), % j3 の続き
assertz(job(j6, e, c, 12, 14)), % j2 の続き
assertz(job(j7, b, e, 11, 15)). % j4 の続き
%% ===========================================================
%% 駆動
%% ===========================================================
solve :-
fleet(0),
findall(Ts-Id, job(Id, _, _, Ts, _), L0),
keysort(L0, L1),
pairs_values(L1, Ids),
forall(member(Id, Ids),
( job(Id, F, T, Ts, Te) -> frag(Id, F, T, Ts, Te) ; true )).
report :-
find_chr_constraint(fleet(UB)),
lower_bound(LB, W),
format("上界 (玉の投入数) : ~w~n", [UB]),
format("下界 (反鎖) : ~w 証拠 ~w~n", [LB, W]),
( UB =:= LB
-> format("→ 一致。最適確定。探索不要。~n")
; D is UB - LB,
format("→ 差 ~w。改善余地あり、または下界が緩い。~n", [D])
),
findall(Id-V, find_chr_constraint(assign(Id, V)), As0),
msort(As0, As),
format("割付 : ~w~n", [As]),
seams(S),
format("継ぎ目 (残玉) : ~w~n", [S]).
run :- facility, jobs, solve, report.