一瞬パルスアルゴリズムに目移りしましたが、以下の通りの弱点があるので採用しませんでした。
なお、パルスアルゴリズムのC++実装は、
https://github.com/lyandut/MyPulseForCSP/tree/master
にあります。
パルスアルゴリズム（Pulse Algorithm）は，ラベル設定法（Label-Setting）を“極限まで強化した双方向分枝限定法”であり，
主目的は「厳しい資源制約付き最短路問題（RCSPP）」を高速に解くことです。 特徴は“ラベルを保持しない（＝DP表を持たない）”点にあります。
以下，RCSPP 文献で確立している標準的なパルスアルゴリズムの構造を，実装レベルまで整理します。
🔥 パルスアルゴリズムとは何か（要点）
深さ優先探索（DFS）＋強力な枝刈り（pruning）
ラベル（DP状態）を保持しない → メモリ使用量が極端に小さい
資源制約（時間・コスト・勤務回数など）を満たすパスのみ探索
下界（Lower Bound）と上界（Upper Bound）を使って強力に枝刈り
列生成の pricing subproblem（RCSPP）で世界的に最強クラス
🧠 アルゴリズムの基本思想
パルスアルゴリズムは，ノード v に到達したときに次の 4 種類の枝刈りを行います。
1. 資源制約による枝刈り
累積資源 が上限を超えたら即終了。
2. 下界（Lower Bound）による枝刈り
ノード v からゴールまでの最良下界 LB(v) を事前計算しておき，
なら探索を止める。
3. 支配（Dominance）による枝刈り
同じノードに到達した過去のパスより劣っていれば枝刈り。
4. サイクル（Cycle）除去
DFS なので，訪問済みノードを再訪しない。
⚙️ パルスの流れ（擬似コード）
Pulse(v, cost, resources):
if resources violate constraints:
return
if cost + LB(v) >= UB:
return
if dominated(v, cost, resources):
return
if v == target:
UB = min(UB, cost)
return
mark v as visited
for each arc (v → u):
Pulse(u, cost + w(v,u), resources + res(v,u))
unmark v
📌 ラベル設定法との違い
| 項目 | ラベル設定法（DP） | パルスアルゴリズム |
|---|---|---|
| 状態保存 | 多数のラベルを保持 | ラベルを保持しない |
| 探索 | 幅優先/最短路型 | 深さ優先（DFS） |
| メモリ | 大量に必要 | 極小 |
| 枝刈り | 資源制約＋支配 | 資源＋支配＋強力な下界 |
| 列生成との相性 | 良い | 最高レベル |
なぜ“パルス”と呼ばれるのか
探索が パルス（pulse）＝波のように深く進み，戻り，また進む という動きをするためです。
🧩 列生成（Column Generation）との関係
RCSPP は pricing subproblem として頻出します。
RMP から得た DUAL を使って reduced cost を計算
パルスは reduced cost < 0 の列 を高速に発見
特に 資源が多次元（勤務回数・連続勤務・休暇制約など） の場合に強い
パルスアルゴリズムの弱点は、強力な枝刈りと深さ優先探索による“爆発的な速さ”の裏側に、いくつか本質的な脆さがある点です。 強いところは極端に強いが、弱いところは極端に弱いという、かなりピーキーなアルゴリズムです。
以下、研究者・実装者の視点で“本当に問題になる弱点”だけを整理します。
🎯 結論：パルスアルゴリズムの主要な弱点（重要度順）
1. 下界（LB）の質に強く依存する
パルスは「LB が弱いと一気に破綻」します。
LB が弱い → 枝刈りが効かない
枝刈りが効かない → DFS がほぼ全探索化
全探索化 → 指数時間で爆死
つまり、
LB が強いと最強、弱いと最悪
という極端な性質を持ちます。
孝幸さんのように ZDD や DP で強い LB を作れる人には向いていますが、 一般の実務者には扱いが難しい理由がこれです。
2. 資源次元が多いと急激に弱くなる
資源次元が増えると：
支配判定が効きにくくなる
LB の計算が難しくなる
DFS の探索空間が爆発する
特に 5 次元以上の資源制約では、パルスは急激に性能が落ちます。
3. 深さ優先探索ゆえに“運が悪いと”最悪ケースに落ちる
DFS は探索順序に依存します。
良い順序 → 最適解にすぐ到達 → UB が早く更新 → 枝刈りが効く
悪い順序 → 最適解に全く届かない → UB が更新されない → 枝刈りが効かない
つまり、
探索順序の設計が悪いと、指数時間に落ちる
4. 並列化が難しい
DFS＋強い枝刈りという構造は、並列化と相性が悪いです。
スレッド間で UB を共有する必要がある
探索順序が変わると性能が大きく変動
LB の更新も同期が必要
結果として、
パルスはマルチスレッド化してもスケールしにくい
5. 実装が難しい（バグりやすい）
パルスは：
支配判定
LB の適用
UB の更新
サイクル除去
資源制約のチェック
など、複数の枝刈りが複雑に絡むため、 少しでも条件を間違えると：
最適解を落とす
不正な枝刈りが起きる
infeasible と誤判定する
という“致命的なバグ”が発生しやすいです。
6. 最適解が高コスト側にあると弱い
パルスは「良い UB が早く見つかる」ほど強い。
逆に、
最適解が高コスト
低コストのパスが存在しない
UB がなかなか更新されない
というケースでは、枝刈りが効かずに弱くなります。
🧩 まとめ：パルスは“尖った武器”
パルスは、 LB が強く、資源次元が少なく、探索順序が良いときに最強 という、非常に尖ったアルゴリズムです。
逆に、
LB が弱い
資源次元が多い
探索順序が悪い
UB が更新されない
という状況では、 指数時間で破綻するという明確な弱点があります。
結論から言うと、パルスアルゴリズムはキャッシュ特性が“かなり悪い”部類に入ります。 これはアルゴリズムの構造的に避けられない弱点で、実際に実装してみると L1/L2 ミスが多発し、CPU の IPC が落ちやすいタイプです。
実装・最適化レベルで RCSPP を扱う人が気づくのは、むしろ自然です。
🔥 なぜパルスはキャッシュ特性が悪いのか（本質的理由）
1. 深さ優先探索（DFS）はアクセス局所性が低い
パルスは DFS でグラフを深く潜るため、
次にアクセスするノードが予測しにくい
メモリ上で連続していないノードに飛ぶ
CPU のプリフェッチがほぼ効かない
結果として、
キャッシュミスが多発し、メモリアクセスがボトルネックになる
これは BFS やラベル設定法（DP）と比べて明確に不利です。
2. ラベルを保持しない＝DP テーブルがない → 局所性が生まれない
ラベル設定法は DP テーブルを持つため、
同じノードのラベルを何度も参照
メモリ局所性が自然に発生
というメリットがあります。
一方パルスは、
ラベルを保持しない
状態をほぼ持たない
毎回新しいパスを深く探索する
ため、局所性がほぼゼロです。
3. LB（下界）テーブルへのアクセスがランダム
パルスの強さは LB に依存しますが、LB の参照は
ノード v に到達するたびに LB[v] を参照
DFS の順序はランダム
LB テーブルのアクセスもランダム化
つまり、
LB が強いほど LB 参照が増え、キャッシュミスも増える
という皮肉な構造になっています。
4. 支配判定（dominance check）がランダムアクセスを増やす
支配判定は通常、
ノードごとに「過去の到達状態」を保持
DFS の順序に依存してランダムに参照
状態数が増えるほどキャッシュミスが増える
特に資源次元が多い場合は顕著です。
5. スタックが深くなるとレジスタ・L1 が圧迫される
パルスは深い DFS を行うため、
再帰スタックが深くなる
ローカル変数が多くなる
レジスタが足りず spill が発生
L1/L2 キャッシュに溢れる
という現象が起きやすいです。
📌 まとめ：パルスは“キャッシュに優しくないアルゴリズム”
構造的に、
DFS
ランダムアクセス
ラベル非保持
LB 参照の多発
支配判定のランダム性
が重なるため、キャッシュ効率は悪くなるのが宿命です。
