⚒️

経路の破壊と再構成をGPTと一緒に実装してみた (数理最適化 Advent Calendar 2025)

に公開
Python
数理最適化
llm
tech

はじめに

Twitter芸人名@cocomoffです。最近は経路探索やLLM活用を考える日々です。

Advent Calendar界隈というか、インターネットでは1年から1.5年に1回ぐらい、数理最適化っぽい小ネタをブログに書いています。

今日は最近聞いてきた話をベースにして、GPTを活用して一緒にヒューリスティック計算に必要な部分を実装してみたという話を書きます。

前提

まずGPTを活用して実装してみたものを紹介します。

問題

聞いてきた話はこれです（中身はプロシーディングスなどにアクセスください）。

特定範囲の経路長を達成する多様な経路集合の生成
○武藤慧，天野雄樹，今井桂子（中大）
https://www.ipsj.or.jp/event/taikai/87/WEB/data/pdf/7K-01.html

多様な部分は置いといて、今年のGPTおまかせのAC実装では「特定の経路長を達成する」の部分を考えます。通常、2点間の最短経路は（実用上、そこそこ）高速に計算できます。ただし

経路pの長さw(p)が範囲 [W_\mathrm{min}, W_\mathrm{max}]に入っておいてほしい

などの特定の制約を課す場合、めんどくさくなる傾向があります（とはいえDFSを使えば力技で実行可能解は出ますが）。適当に探索すると大変そうですが、Destroy-and-Repair という一般的な方策（解の破壊と修復）でこれを達成するという話があったので、それが題材です。

Destroy-and-Repair の操作イメージ

今回は式は使わず、操作の概念だけ紹介します。まず、通常のs-t経路のDestory-and-repairはこういうイメージの操作です。適当にPythonのlistをイメージしてもらって、ある部分パスを切断するとこういう操作ができます。切断して途切れているところに別の経路を何か足せば、新しい解が得られます（あとは、制約を満たすまで頑張るなどのアプローチをとります）。

ある経路 Destroy Repair

いい感じのつなぎ方

足す部分にいい感じのつなぎ型を考えたいです。聞いてきた話を理解した限りだと、切断した部分（これは s'-t' とします）の周辺から最短経路木をつくり、活用するというアイデアが使えそうです。似たようなアプローチ（最短経路木）はたまに見ることがありますね。

T_{s'}とT_{t'}でGを分割 2つの木の境界辺を出す 境界辺を選んでつなぐ

このアプローチが良いところは、非常に膨大なパターンがあるs'-t'のつなぎ方を、辺の選択問題で誤魔化すことができることでしょうか。もちろん辺の選択問題にすることで一定の制限が出ます（辺まで最短経路木で移動することになる）が、高速に処理ができそうです。概ね操作イメージはつかめたので、あとはGPTにご相談して実装してもらうパートをやります。

やったこと

上の処理を描かれたスライドが手元にあったので、それを入力し、適当に会話しながらGPTと実装しました。

GPT初期実装

まず資料を見てGPTくんに適当に実装してもらった謎の実装の結果です。中身を見るとDestory-and-repairはまったくしてなくて没なのですが、とりあえずいろんな経路を計算してくれることはわかりました。

格子 道路

上で説明した Destroy-and-Repair のGPT完全おまかせ

処理を丸ごとお任せすると、どうもイマイチ期待通りに動作しません。そこでヒューリスティックをちゃんと説明して、Destroy-and-Repair を実装させてみます。すると、何か出力してくれました。しかしまだ問題があります。

例えば上の図だとs'-t'と探索のトリック（著者さんのネーミングだと仮想根ノード）によるとうまくグラフが分かれそうなのですが、例えば格子グラフで再現させると、下の図のように領域（頂点）がうまく分割されず、境界辺が計算できていませんでした。

s'からの木（T_{s'}）とt'からの木（T_{t'}）がうまく形成できていないな？となり、調べていると、GPTが実装に使っていた networkx_bfs_tree が悪さをしている（うまく外向木と内向木、つまりT_{s'}とT_{t'}を形成できていない）様子でした。

GPTログ→解読→修正指示

そこで実装を修正します。具体的に内向木と外向木をちゃんと計算させるように指示します。指示さえすれば世の中によく使われている実装なので、GPTくんも書いてくれます（効率的かどうかは別ですが）。

そこそこ動くのが確認できたので、研究毎度おなじみOSMnxくんを使って東京駅周辺の適当なサイズの道路ネットワークを持ってきて、双方向有向化してから使いました。

結果は、うまく頂点が赤色と青色に分割されるようになりました。コンセプト通り動いていそうで、2つの領域に分割できていそうです。

ここまで来たら、後は

  • 境界の辺を選ぶ（これをu-vとする）
  • s-s'-u-v-t'-t 経路を構築する

という処理を書けばいいです。GPTに任せなくても簡単に書ける気がしますが、このままGPTに任せて実装してもらいました。

s,tの可視化が見づらくて適当ですが、得られた何本かの経路を可視化します。

代替経路が得られている様子がわかりました。

まとめ

最初に説明した経路探索問題について、GPTを使っていろいろアプローチしました。

結果としては、全体でチョコチョコ他のことをやりながら取り組んで、0.5日ほどでそれらしい可視化までできるようになりました。以下、時系列です。

  • 初期git登録（全自動まで）
    • 2025/11/25 21:51
  • GPTが重くて作業に飽きる
    • (つ∀-)ｵﾔｽﾐｰ
  • 内向・外向ができていないことに気づいてやり直す。そこそこ動くようになる。
    • 2025/11/26 13:13
  • 他の部分を仕上げる
    • 2025/11/26 13:56

もちろん真面目な実装としては足りない部分が山程ありますが、なかなか悪くないなという感じです。本当は内向木・外向木の実装までたどり着ける気がしますが、指示が適当過ぎましたかね…。

今年のネタはこれで終わりです。来年は全部GPTがやってくれるようになっているはずなので、引退してるかもしれませんが、もし来年も書いたらよろしくお願いします。

Discussion