パルスアルゴリズム

一瞬パルスアルゴリズムに目移りしましたが、以下の通りの弱点があるので採用しませんでした。

なお、パルスアルゴリズムの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. 資源制約による枝刈り

累積資源 $r$ が上限を超えたら即終了。

2. 下界（Lower Bound）による枝刈り

ノード v からゴールまでの最良下界 LB(v) を事前計算しておき，

$$\text{current\_cost}+LB(v)\ge UB$$

なら探索を止める。

3. 支配（Dominance）による枝刈り

同じノードに到達した過去のパスより劣っていれば枝刈り。

4. サイクル（Cycle）除去

DFS なので，訪問済みノードを再訪しない。

⚙️ パルスの流れ（擬似コード）

pseudo

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 参照の多発

• 支配判定のランダム性

が重なるため、キャッシュ効率は悪くなるのが宿命です。