mixiユーザー(id:1129685)

2026年04月01日15:27

40 view

乗換案内はNP完全、もしくはNP困難問題

前の日記(https://mixi.jp/view_diary.pl?id=1991895032&owner_id=1129685 )にも乗り換えをネットワーク、もしくはグラフのノードやアークとして処理しているかもと触れましたが。
やっぱりよく考えたらLLMベースのAIがわざわざ旅行のプランをネットワークとして処理しているわけないですね。そういうルートを取る人が多いとか、旅行会社のサイトとかのモデルコースがそういうルートが多いというところから採用されたコースなのではないかな。

一方で、駅すぱあととか、ジョルダンとかそういうのは、経路をネットワークのノードとして処理していると思うのですが。これは巡回セールスマン問題と同様にNP完全問題といって数学的に難問ですね。
重複したり無駄に乗り換えするような木を枝狩りして探索して実用的な時間内に回答を出していると思います。

実のところ東芝さんが、駅前探検倶楽部としてサービスしていた(2003年頃に分社化、2008年に駅探に名称変更して現在も�蟇愧気茲螢機璽咼昂兮鈎罅謀�時の資料があります。
やっぱりこういう仕組みでやっていたんですね。この資料の2.1項をみると、やはり路線図全体をネットワークNとして捉え、駅をノード、経路をアークとして処理しているんですね。
最近はジョルダンとかナビタイムとかばかりつかっていて、駅探はあまりつかってないなぁ。今度使ってみようかな。
https://www.global.toshiba/content/dam/toshiba/migration/corp/techReviewAssets/tech/review/2001/12/56_12pdf/a03.pdf
2 0

コメント

mixiユーザー

ログインしてコメントを確認・投稿する

<2026年04月>
日 月 火 水 木 金 土
   1234
567891011
12131415161718
19202122232425
2627282930  

最近の日記

もっと見る