20260929_MicrosoftDataAnalyticsDay_最短経路と最長経路，そしてオントロジーへ－Fabric Appsで作る「日本全国 駅間経路探索」と意味の世界への応用－

© 2026 NTT West, Inc. All Rights Reserved. 最短経路と最長経路， そしてオントロジーへ Fabric Appsで作る「日本全国 駅間経路探索」と意味の世界への応用 2026/9/29 高須賀 将秀

© 2026 NTT West, Inc. All Rights Reserved. 2 /26 自己紹介 たかすか まさひで 高須賀 将秀 博士（情報学）（2023/3） 研究分野：組合せ最適化，数理最適化，オペレーションズ・リサーチ（OR），グラフ理論 高須賀将秀のホームページ 所属：NTT西日本 デジタル改革推進部（2021/8～）， 法政大学 デザイン工学部 兼任講師（2024/4～），個人事業（Udemy講師等）（2024/6～） 業務：データドリブン経営を牽引する立場 ・データ活用基盤のシステム開発 ・データ分析手法の研究 ・データ分析活用事例の提案 ・デジタル人材育成 New! 資格：クラウド資格（AWS全冠，Azure/AppliedSkills全冠，GCP全冠， Snowflake全冠）， 受賞：AWS Top Engineers（’26） ，AWS Community Builders（’26），AWS All Certifications Engineers（’24/’25/’26）， Microsoft Top Partner Engineer Award（’24, ‘26），Microsoft Innovative Educator Experts 2025-2026， Google Cloud Partner Top Engineer（’26），Google Cloud Partner All Certification Holders（‘25）， Jagu‘e’r Award 優秀賞（’25），Snowflake Squad（’24, ‘25）， Microsoft Certified Trainer（MCT）

© 2026 NTT West, Inc. All Rights Reserved. 3 /26 本日お話しすること 1 原点 3年前に設定したテーマ「データトリガーのユースケース発掘」 2 理論 最短経路と最長経路は似て非なる2つの最適化問題 3 実装 Fabric Apps で作る 日本全国駅間経路探索アプリ 4 展望 グラフアルゴリズムでオントロジーの質を高める

© 2026 NTT West, Inc. All Rights Reserved. 4 /26 3年前に設定したテーマ：データ活用のユースケース発掘の自律化 2023年当時の資料．課題起点ではなく，データ構造の抽出からユースケースそのものを発掘する構想． MSIISM2023の発表抜粋

© 2026 NTT West, Inc. All Rights Reserved. 5 /26 課題起点の分析からデータ起点の発掘へ 現状：課題起点のデータ分析 目指した姿：データ起点の発掘 ■ 実業務で見えている課題から出発し，必要なデータ ■ 基盤上の全データからデータ構造を抽出する を集めて分析する ■ 構造の中から潜在的・複合的なユースケースを機械 ■ 見えている課題しか扱えず，活用シーンが限定される が提案する ■ 基盤に眠る大量のデータが活かされない ■ 分析のハードルを下げ，施策横断的なデータ活用を 推進する 当時の壁は，機械が「業務コンテキスト」を持てなかったこと．データの意味構造は人手で抽出するしかなかった．

© 2026 NTT West, Inc. All Rights Reserved. 6 /26 この2ヶ月の発表の系譜 2026.07 2026.08 2026.09 データの共有から コンテキストの共有へ セマンティックモデルと オントロジーの自動生成 グラフアルゴリズムで オントロジーの質を高める Fabric × Snowflake．単一コピーの Icebergで両プラットフォームをつなぎ，データだ けでなくカタログやエージェントを共有する話 業務概念(Entity・Relationship)の層を，人 手ではなく自動で立ち上げる話 本日．生成されたオントロジーを「測り，鍛える」 ための数理最適化の視点 セマンティックモデルやオントロジー技術の発展で，業務コンテキストをある程度自動生成できる時代が来た．3年前の思想が実現する日は着 々と近づいている．

© 2026 NTT West, Inc. All Rights Reserved. 7 /26 意味層のスタックが揃ってきた Data Agent オントロジーとセマンティックモデルを参照し，自然言語で回答する ここでのポイント ■ オントロジーは実質，知識グラフとして 扱われる Fabric IQ 組織で共有するビジネスコンテキスト層 ■ AIの回答品質は，この意味層の「質」 に強く依存する オントロジー Entity Type・Property・Relationship による業務概念のグラフ ＝ 知識グラフ セマンティックモデル テーブル・メジャー・リレーションの意味付け → 本日のポイントは，数理最適化問題の「最長経路問題」 ■ では、その質はどう測り，どう高めるの か？

© 2026 NTT West, Inc. All Rights Reserved. 8 /26 今回の題材：日本全国駅間経路探索アプリ ■ 実際の鉄道網(ekidata.jp)を題材に，任意の2駅間の経路を計算す るWebアプリをMicrosoft Fabric Appsで実装 ■ 最短経路(ダイクストラ法)と最長経路(単純経路・営業キロ最大)を同 時に計算し，地図上に色分け表示 ■ 計算結果はFabric Lakehouse / SQL Databaseに保存 10,465 9,920 1,699 駅(営業中) 路線内区間 乗り換え辺 データ出典：駅データ.jp (ekidata.jp)．営業中の駅のみ抽出．

© 2026 NTT West, Inc. All Rights Reserved. 9 /26 最短経路問題と最長路問題の違い 最短経路 最長経路(近似解) 4ホップ / 3.2 km 498ホップ / 1290.2 km 江古田 → 桜台 → 練馬 → 新江古田 関東平野から信越・東北を一周して戻る 起点と終点は徒歩10分の隣駅(江古田と新江古田)．距離の差は約400倍．ただし本当に違うのは計算の難しさ

© 2026 NTT West, Inc. All Rights Reserved. 10 /26 最短経路問題：ダイクストラ法(1959) ■ 定義：2点間を結ぶ経路のうち，辺の重み(距離)の総和が最小のものを求める ■ ダイクストラ法は，始点から「距離が確定した駅」を波紋のように広げていく貪欲法 ■ 重みが非負なら，一度確定した駅の最短距離は二度と更新されない A 4 計算量 3 S 7 C 2 3 B S→B→C→T ＝ 7 (最短) 2 T O(E log V) 多項式時間．全国10,465駅ならミリ秒単位で， 100万ノード規模でも実用的に解ける．

© 2026 NTT West, Inc. All Rights Reserved. 部分構造最適性 最短経路の部分経路は，それ自体が最短経路．S→Tの最短路が駅Xを通るなら，そのS→X区間も必ずS→Xの最短路になっている． 1 だから途中の駅ごとに「ここまでの最短距離」だけ覚えればよい(経路の組合せを列挙しなくてよい) 2 だから一番近い駅から順に確定してよい(貪欲法の正しさが保証される) 3 この性質を使う設計図が動的計画法(DP)．最短経路はDPと相性が最高に良い問題 この「当たり前に見える性質」が，最長経路では成り立たない． 11 /26

© 2026 NTT West, Inc. All Rights Reserved. 12 /26 最長経路問題：「同じ駅を二度通らない」が本質 ■ 定義：同一の駅を二度通らない単純経路(simple path)のうち，営業キロの総和が最大のものを求める ■ 「単純経路」の制約がなければ，環状線を無限に回れて答えが発散する．制約こそが問題を定義する ■ 鉄道での実例は，改札を出ずに乗れる「最長片道きっぷ」の世界．旅客営業規程にも同じ制約がある 見た目は最短経路の「max版」なのに 目的関数をminからmaxに変えただけで，問題の性質は一変 する．単純経路制約が「どの駅を使ったか」という組合せ的な記 憶を要求するため． 環状線は「一周まで」．二周目は同じ駅を再訪してしまう．

© 2026 NTT West, Inc. All Rights Reserved. NP困難となる理由 最長経路の部分経路は，最長経路とは限らない．途中で「寄り道」した方が全体は長くなるが，寄り道に使った駅は後で使えなくなる． 1 「ここまでの最長距離」だけでは足りず，「どの駅を使い済みか」まで覚える必要がある．状態数が2のn乗に爆発する 2 全駅を一度ずつ通る経路(ハミルトン路)の存在判定がそのまま帰着される，古典的なNP困難問題 3 一般グラフでは，多項式時間の厳密解法は(P≠NPなら)存在しない．近似すら困難なクラス 最短経路は「距離」というスカラーの記憶で足りる．最長経路は「集合」の記憶を強いられる． 13 /26

© 2026 NTT West, Inc. All Rights Reserved. 14 /26 計算量の対比 問題 代表的な解法 計算量 全国10,465駅での現実感 最短経路 ダイクストラ法 O(E log V) ミリ秒．100万ノードでも実用的 最長経路(一般グラフ) 厳密な全探索 指数時間 (NP困難) そのままでは事実上，解けない 最長経路(DAG) トポロジカル順のDP O(V + E) 一瞬．閉路がなければ簡単になる (参考)巡回セールスマン 実務はGurobi等で近似 O(n!) (NP困難) 50駅の巡回でも厳密解は非現実的 閉路のない有向グラフ(DAG)なら，最長経路はO(V+E)で解ける．この性質が第4部のオントロジーの話で効いてくる．

© 2026 NTT West, Inc. All Rights Reserved. 15 /26 先行事例：東京メトロの「改札内最長片道」問題 モバイルファクトリー社 Tech Blog (2018) 全国規模では？ ■ 改札を出ずに営業キロの和が最長になる迂回経路を，旅客営業規 ■ 駅数10,465，区間11,619．メトロ 程に基づいて定式化 の約60倍のノード数 ■ グラフ問題ライブラリGraphillion(ZDDベース)で全経路を列挙し， ■ ZDDによる厳密全列挙は，現実的な 重み最大の経路を厳密に取得 時間で終わらない可能性が高い ■ 改札内乗り換え駅(赤坂見附と永田町など)は距離0の辺で接続し， ■ そこで鉄道網の「構造」を利用した独 並行路線は路線別ノードに分離 自の分解アルゴリズムを設計(第3部) ■ 結果は 和光市 → 西船橋 の78.8km(東京メトロ全179駅の規 模) 出典：モバイルファクトリー Tech Blog「Graphillionで東京メトロの最長経路問題を考える」(2018)．問題定義は本記事に準拠．

© 2026 NTT West, Inc. All Rights Reserved.

16 /26

Microsoft Fabric Apps(プレビュー)とは
■ TypeScriptでデータモデルを宣言するだけで，アプリの基盤一式がFabric上に自動生成される新機能
■ デプロイは npx rayfin up の1コマンド．ビルドしたReactアプリがそのままFabricにホスティングされる

↓ ここから自動生成されるもの

// rayfin/data/schema.ts
@entity()
@authenticated('*')
export class Station {
@uuid() id!: string;
@text({ unique: true }) stationCd!: string;
@text() name!: string;
@decimal() lat!: number;
@decimal() lon!: number;
}

出典：Microsoft Learn の Fabric Apps overview(Rayfin SDK、プレビュー機能)

GraphQL API

Data API Builder互換のクエリ/ミューテー
ション

Fabric SQL Database

スキーマから自動生成(dbo.Stationsなど)

静的ホスティング

*.webapp.fabricapps.net で即公開

Fabric SSO認証

Entra IDベースのサインインが標準装備

© 2026 NTT West, Inc. All Rights Reserved. 17 /26 全体アーキテクチャ 駅データ.jp CSV シードスクリプト Fabric SQL Database Reactアプリ (Fabric Apps) station / join (10,963行 / 10,189行) mssqlパッケージで 一括bulk INSERT Stations / StationEdges / LongestPathRuns 起動時に全件取得し グラフを構築 ブラウザ内で完結する計算エンジン(TypeScript移植) ダイクストラ法(二分ヒープ) / Tarjan橋検出 / block-cut tree分解 / 枝刈りDFS / Color-Coding近似 → Leaflet + OpenStreetMapで経路を描画 計算結果は「この結果をLakehouseに保存」ボタンからGraphQL mutationで書き込む．Python版パイプライン (Fabric Notebook 3本)も別途構築済み．

© 2026 NTT West, Inc. All Rights Reserved. 18 /26 分解アルゴリズム：NP困難を局所的なブロックに限定する ■ 鉄道網は大部分が支線・盲腸線の「ほぼ木構造」．複数経路があるのは都市部など局所的な範囲だけ ■ Tarjanのアルゴリズムで橋と二重連結成分をO(V+E)で検出する．橋は「必ず通る強制辺」になる ■ ブロック内だけ最長単純路を解き、橋でつなぐ．関節点は二度通れないため，ブロック毎の最適の連結が全体最適になる 橋(強制辺) 橋(強制辺) S T ブロック1：環あり → 探索 ブロック2：環あり → 探索 指数的な難しさは赤いブロックの内部にだけ残る．全国規模でも現実的な時間で解ける． ブロック3：環あり → 探索

© 2026 NTT West, Inc. All Rights Reserved. 19 /26 ブロック内部の解き方：厳密解と近似解の二段構え 厳密解 ノード数24以下のブロック ■ 枝刈り付き深さ優先探索(DFS)で全探索 ■ 枝刈りその1：残りのグラフで出口に到達できなければ 打ち切り ■ 枝刈りその2：現在距離と残り辺重みの上界の和が 既知の最良解以下なら打ち切り 近似解 大きなブロック(都心部など) ■ Color-Coding法(Alon, Yuster & Zwick 1995) にフォールバック ■ 駅をランダムにk色に塗り，「色の集合」ごとの最大重 みをDPで追跡する．集合の記憶を色数分に圧縮できる ■ 時間予算内のランダム化DFSヒューリスティックも併用 アプリの結果表示にも「解法：厳密解 / 近似解(Color-Coding)」を明示し，保証の有無を伝えている．

© 2026 NTT West, Inc. All Rights Reserved. 20 /26 最短(緑)と最長(赤)を一画面で対比 地図表示 Leaflet + OpenStreetMap．APIキ ー不要 オートコンプリート 1万件超の駅名から上位50件を軽量表 示 色分け描画 最短は緑，最長は赤の複数経路レイヤ 都心部を埋め尽くす最長経路(赤)．起点と終点の江古田/新江古田． Fabric Apps 構築用のリポジトリ https://github.com/mshdtksk/fabric-longest-path-problem 計算はすべてブラウザ内， 保存はFabricへ

• https://github.com/mshdtksk/fabric-longest-path-problem

© 2026 NTT West, Inc. All Rights Reserved. 21 /26 オントロジーは「点と辺のグラフ」である ■ 点は概念(Entity)，辺は関係(Relationship)．近い点は意味が似ており、遠い点は意味が遠い ■ つまり駅とまったく同じ土俵で，グラフアルゴリズムがそのまま適用できる ■ そして，このグラフの構築の仕方そのものが，オントロジーの質を決める Order Customer Route Shipment Truck 意味的に遠い(概念距離が大きい) Invoice Subscriber 意味的に近い(概念距離が小さい)

© 2026 NTT West, Inc. All Rights Reserved. 22 /26 最短経路 × オントロジー：「意味の近さ」を測る 説明可能性 「CustomerとInvoiceはどう繋がる？」に，最短の説明経路で答える．Data Agentが『なぜその回答か』を根拠付きで 示せる 類似概念検索 概念距離が小さいことは，意味が似ていることを表す．CustomerとSubscriberを同義候補として提示できる．セマンテ ィック検索の土台 メタデータ探索 「売上」という概念から最短で到達できるテーブル・カラム・レポートを提示する．データカタログの動線設計に使える 例：顧客売上を教えて → Customer → Order → OrderLine → Revenue という最短の参照経路が、回答の「説明」になる

© 2026 NTT West, Inc. All Rights Reserved. 23 /26 最長経路 × オントロジー：「意味の深さ」を測る 概念階層の深さ Customer → Premium → Corporate → Strategic のような階層の最長経路長がOntologyDepth．複雑度や 粒度の設計レビュー指標になる 依存チェーン分析 OneLake → Lakehouse → Table → Semantic Model → Report → Data Agent の最長依存鎖は，変更 影響や障害波及の最大経路を表す RAGの優先検索 深いノードほど具体的で専門的．「ASR9000について教えて」という質問には，階層の深い概念を優先的に検索対象に できる 概念階層や依存関係は通常DAGになる．鉄道網ではNP困難だった最長経路が，ここではO(V+E)で解ける．

© 2026 NTT West, Inc. All Rights Reserved. 24 /26 2つを組合せる：オントロジー品質の定量化 Ontology Health Score ＝ α × LongestDepth ＋ β × AvgShortestPath LongestDepthは知識の「深さ」，AvgShortestPathは知識の「つながりやすさ」を表す Critical Path分析 PERT/CPMの発想を流用し，深さ×利用頻度×Agent参照回数で「重要概念」を特定する 中心性との併用 PageRankや媒介中心性を加えて，AIエージェントにとっての要衝概念を発見する 実装イメージ オントロジーをNetworkXのDAGへ変換し，dag_longest_path()などで算出．Power BIでOntology Health Dashboardにする グラフの張り方を「測れる」ようになれば，オントロジーは設計レビューと継続改善の対象になる

© 2026 NTT West, Inc. All Rights Reserved. 25 /26 当初の思想からの道しるべ 経路アルゴリズム オントロジーの質向上 AIの推論品質向上 ユースケースの自動発掘 最短経路は意味の近さ， 最長経路は意味の深さを測る 測る，見直す，鍛える． Health Score / Critical Path Fabric IQとData Agentが 深く正確に業務を辿れる データ構造から潜在的で 複合的な活用シーンを提案 3年前に描いた「データ活用のユースケース発掘の自律化」 オントロジーが業務コンテキストを担い，グラフアルゴリズムがその質を支える

© 2026 NTT West, Inc. All Rights Reserved. まとめ 最短と最長は似て非なる問題 1 minとmaxの一字違いで，多項式時間とNP困難に分かれる．ただしDAGや分解といった「構造」を見抜けば戦える． Fabric Apps は，アルゴリズムを「動くアプリ」にする最短経路 2 TypeScriptのスキーマ定義とrayfin upだけで，DB・API・ホスティング・認証が揃う． オントロジーはグラフであり，経路アルゴリズムがその質を高める 3 意味の近さ(最短)と深さ(最長)を測ることが，ユースケース自動発掘の未来につながる． 26 /26