該如何學好 “寫程式” #3. 進階應用 - 資料結構 + 問題分析

摘要提示

• 問題定義: 以台灣高速公路為題，從起終點找出「最低總成本」的建議路線。
• 資料結構選型: 採用圖(Graph)為核心模型，以節點(Node)與連線(Link)表達交流道與路段。
• 類別設計: Node 含名稱/過路費/相鄰連線，Link 含距離/端點/所屬公路。
• 資料載入: 以 Map 類別包裝節點/連線，透過 AddNode/AddLink 建置子集路網。
• 成本模型: 油錢以每公里2元估算，總成本=累計油費+節點過路費。
• 演算法選擇: 以堆疊與遞迴的深度優先搜尋(DFS)走迷宮，枚舉所有可行路徑取最小值。
• 複雜度思考: 對比更高效的擴散式最短路徑演算法，示範「易寫與可讀性」的權衡。
• 效能優化: 由 Stack.Contains 的 O(n) 改為 HashSet 的 O(1) 檢查，顯著降低查找成本。
• 學習重點: 程式=資料結構+演算法；基礎不紮實，無法正確建模與選擇工具。
• 架構觀點: 效能與架構難以兼顧，先求演算法/資料結構正確，再談可讀性與擴充性。

全文重點

本文延續系列主題，從更貼近實務的「高速公路路徑規劃」問題，示範如何以資料結構與演算法解決複雜需求。作者以「總成本最小」作為最佳路線的判準，成本由過路費與油費（以每公里兩元估算）構成。為了正確建模，採用圖(Graph)結構：交流道/收費站作為節點(Node)，節點間路段為連線(Link)，並在類別中封裝必要屬性（名稱、過路費、距離、所屬公路、相鄰連線）。接著以 Map 類別集中管理節點與連線，示範如何載入部分路網資料（北部國道一/三與機場支線），提供查詢連線與後續路徑搜尋所需的基礎。

在演算法策略上，作者先點出可用「由起點向外擴散、逐步鬆弛成本」的典型最短路徑思路（接近 Dijkstra 類型），但為兼顧教學清楚與實作簡易，實作上改採「深度優先搜尋（DFS）+ 堆疊/遞迴」的迷宮走法：從起點出發，沿分支遞迴前進，使用堆疊紀錄走過的路徑避免回訪，當到達終點即計算總成本並更新全域最佳解。此法能枚舉所有可行路徑，雖然效率較差，但邏輯簡單、可讀性佳，適合教學與小規模資料。實作展示了核心流程：維護目前路徑與成本、遇終點更新最佳解、對相鄰節點遞迴探索並避開已走節點。

完成初版後，作者進一步檢視效能瓶頸，指出以 Stack.Contains 檢查回訪會造成 O(n) 線性成本，隨路徑增長效能劣化。對症下藥的改善是改採 HashSet 追蹤已訪節點，將查找降為 O(1)，以空間換時間，對大型圖尤具意義。作者藉此重申：小幅的程式碼層級優化（如少幾行指令）難以比擬演算法與資料結構選擇帶來的「倍數級」效能提升。

文末總結學習觀，回應常見質疑（如「都在談架構、封裝、資料庫，何必學資料結構/演算法」）：若基礎薄弱，既不知如何正確描述資料（如將地圖拆成點與線），也難以在現有工具中做出正確取捨（如挑選合適的集合型別）。資料庫效能議題亦與資料結構觀念息息相關。作者自述在架構與效能間偏向可讀性/擴充性，但絕不犧牲演算法與資料結構的正確性，因其影響常為數倍甚至數量級。系列下一階段將從「把程式寫對」進一步走向「把程式寫好」，切入 software engineer 的視角。

段落重點

問題引言與系列脈絡

作者承接前兩篇，將焦點從簡單資料搜尋擴展至複雜度更高的實務題：在台灣國道（中山高、北二高、國道二號）上，為使用者指定的起點與終點找出「最佳路徑」。為避免過度簡化，明確定義最佳準則為總成本最小（過路費＋油費，以每公里兩元假設），強調此問題不僅關乎資料存放，更仰賴適當演算法。並提出三道關卡：如何存放地圖資訊（資料結構）、如何設計路徑搜尋演算法（演算法）、如何組織程式（架構與工具運用）。指出這三者次序相依，先有正確的資料模型，才談得上有效率且正確的求解方法，最後才是程式結構與可用庫的選擇與整合。

建模：以圖(Graph)表示高速公路

為了抽象化高速公路網路，作者採用圖(Graph)的標準建模方式：節點（Node）對應交流道或收費站，連線（Link）對應兩交流道間的路段。此模型的好處在於能自然表達多條路同時存在的實況（如國道1/3互通）、支線/系統交流道等非線性拓撲，並可進一步承載權重（距離/費用）以支援成本計算。相較於單純把資料「塞進記憶體查找」，圖模型提供面向路徑與遍歷的能力，為最短路徑、最小成本等優化問題提供結構基礎。作者點出：若不理解圖這類核心資料結構，後續演算法就無從談起，資料表設計也將失去依據。

類別設計：Node/Link 與屬性

Node 類別包含 Name、TollFee 與 Links（相鄰路段），Link 類別包含 Distance、FromNode、ToNode 與 Road（所屬公路枚舉）。此設計將成本要素拆分至恰當層級：過路費屬於節點（經過時收費），行駛成本屬於連線（距離對應油費），同時藉由 Node.Links 提供鄰接關係，便於遍歷。這種微調的欄位布局，關乎之後成本累加與路徑判定的正確性與簡潔度。作者並保留道路名稱枚舉，以利在結果或策略上呈現路線所屬幹線，強化可讀性與未來擴充（如不同道路權重）。

地圖資料建置：Map 類別與載入

Map 類別以 Dictionary<string, Node> 管理節點，提供 AddNode/AddLink 方法，將資料輸入與連線建立封裝；FindLink 則支援按名查找兩點間路段。為示範重點，作者只輸入北部國道一/三與機場國道的部分資料。這一步凸顯了資料準備的重要性：演算法再好也需可靠的資料基礎；同時展現以名稱做鍵值快速定位節點的實用性。AddLink 使雙向連線對稱加入兩端節點的 Links，形成鄰接表（Adjacency List）的典型表示，這是圖演算法常見且高效的落地方式。

路徑搜尋策略：暴力法、擴散法與 DFS

作者先概述兩類思路：一是暴力枚舉所有路徑後取最小；二是由起點向外擴散、逐步淘汰較差路徑（對應最短路徑演算法，如 Dijkstra）。在教學考量下，選用邏輯直觀、易於上手的 DFS「走迷宮」法：以堆疊紀錄麵包屑，無路可走時回退，遍歷所有可能到達終點的路徑。圖不同於樹，存在回環，因此必須避開已訪節點以免陷入循環。此策略雖在大圖上效率不如專門最短路徑演算法，但實作成本低，能清楚展演路徑搜尋、成本累加、最佳解更新等核心概念，適合作為進階應用的入門示例。

遞迴實作：FindBestPath/Search 程式流程

核心包含兩部分：FindBestPath 作為入口，初始化狀態（_cost、_path）後呼叫遞迴 Search；Search 以當前節點入棧，若抵達終點則比較與更新全域最佳成本與路徑；否則枚舉相鄰連線，對尚未在路徑中的下一節點遞迴探索，並在返回時出棧。成本模型在遞迴傳遞的 current_cost 中累計，包含下一節點過路費與路段距離×每公里成本。這樣的實作利用呼叫堆疊隱式管理回溯狀態，使程式簡潔；同時用 _best_path 保存目前最優路徑。此範型可廣泛應用於組合搜尋、路徑規劃、走迷宮等問題。

結果與效能觀察

示例以「機場端→基金」為查詢，程式能輸出成本最低的路線與總成本。作者未以大規模資料壓測，但藉機說明效能優化的優先順序：與其糾結於微幅的程式層級優化（如少幾行、縮短10%時間），不如先從演算法與資料結構下手，因為後者常帶來「倍數級」的改善，遠超過硬體升級或細微微調。回扣前文例子，也強調不同集合型別（如 List vs SortedList/Hash 結構）在查找成本上的巨大差異。在此脈絡下，作者鎖定本實作中的主要瓶頸點，準備進行針對性優化。

進一步優化：用 HashSet 降低查找複雜度

瓶頸在於用 Stack.Contains 檢查是否已在路徑中，屬 O(n) 線性掃描，路徑越長越慢。替代方案是同步維護一個 HashSet 追蹤已訪節點：新增 O(1) 攤銷、查找 O(1)，只需在入棧時加入、出棧時移除即可。雖然多耗一份空間，但在圖節點與分支數增大時極為划算。作者也援引 MSDN 對 HashSet 在集合運算（交集/聯集）上的效率說明，強化其作為「訪問檢查」與「集合操作」利器的定位。此改動充分體現「以正確資料結構解決問題」的關鍵影響。

小結：為何仍要紮實學資料結構與演算法

作者回覆常見質疑（只談架構、封裝、資料庫即可？）：若缺乏資料結構/演算法基礎，可能無法正確描述資料（如不會把地圖拆成點與線），也不會在現成工具間做出正確選擇（如集合型別、索引策略）。資料庫效能本質上也可視為更龐大的集合與索引管理，與資料結構觀念一脈相承。作者個人雖偏好程式可讀性與擴充性，但堅持不犧牲演算法與資料結構的正確性，因其影響往往是數倍的差距。此觀點回到開場名言「程式=資料結構+演算法」，強調學習的地基。

展望：從寫對到寫好

本系列第一部分聚焦「把需求正確轉化為程式」的 Programmer 能力：正確建模、選擇合適資料結構、挑對演算法、完成可靠實作。接下來作者預告將進入 Software Engineer 角色——不僅寫對，還要寫得好：包含更完善的架構設計、模組化與封裝、可測試性與可維護性、面對變更的擴充策略、以及在效能與可讀性間的拿捏。對讀者而言，這是從「解出問題」邁向「優雅而健壯地解問題」的進階之路，呼應本篇反覆強調的基礎與取捨意識，為後續內容鋪墊方向。

資訊整理

知識架構圖

1. 前置知識：學習本主題前需要掌握什麼？
   • 程式語言基礎（以 C#/.NET 為例：類別、集合、泛型、例外處理）
   • 基本資料結構（陣列、List、Dictionary、Stack、Set）
   • 演算法與時間複雜度概念（Big-O：O(1)、O(n)、O(log n)）
   • 圖論入門（節點 Node、邊/連線 Link、加權圖）
   • 遞迴思維與呼叫堆疊（call stack）
2. 核心概念：本文的 3-5 個核心概念及其關係
   • 圖的資料建模：以 Node/Link 表達交流道與路段，附加費用、距離、道路別等屬性
   • 路徑搜尋演算法：以遞迴+Stack 的 DFS 走迷宮，列舉所有路徑後取最小成本
   • 成本函數定義：油耗成本（距離→油價）+ 過路費 → 最佳化目標
   • 時間複雜度與資料結構選擇：Contains 的 O(n) 問題與 HashSet 的 O(1) 改善
   • 架構與效能的取捨：可讀性/擴充性 vs. 極致效率，先確保正確的資料結構與演算法
3. 技術依賴：相關技術之間的依賴關係
   • Node/Link 類別 → 組成 Map（Dictionary<string, Node> 管理節點）
   • Map → 提供 FindBestPath/Search 進行 DFS 遍歷
   • Stack 用於路徑記錄；搭配遞迴形成回溯
   • 成本計算依賴 Link.Distance、Node.TollFee、油價/油耗換算
   • Contains 檢查走訪狀態 → 以 HashSet 優化（避免 O(n) 線性搜尋）
4. 應用場景：適用於哪些實際場景？
   • 導航/路線規劃（公路、鐵路、航空轉乘）
   • 迷宮/地圖探索、遊戲 AI 的路徑尋徑雛形
   • 網路路由與連通性分析
   • 資料庫 schema 設計：以圖觀點拆解實體與關聯
   • 大型資料處理時的集合運算（交集/聯集）與索引策略

學習路徑建議

1. 入門者路徑：零基礎如何開始？
   • 熟悉 C# 類別、方法、List/Dictionary/Stack 基本操作
   • 了解 Big-O 與常見集合的時間複雜度
   • 用小型圖資料手刻 Node/Link，能以 DFS 列舉所有路徑
   • 練習遞迴與回溯（走迷宮、全排列）
2. 進階者路徑：已有基礎如何深化？
   • 將 DFS 加上成本函數，找出最小成本路徑
   • 採用 HashSet 優化走訪狀態查詢，量測效能差異
   • 導入更有效率的最短路徑演算法（Dijkstra、A*）並比較複雜度
   • 設計可擴充的 Map 載入介面（由檔案/資料庫載入）
3. 實戰路徑：如何應用到實際專案？
   • 以實際地圖資料（如 OpenStreetMap）建模，實作最短/最便宜路徑
   • 寫單元測試覆蓋多起訖點、封路、費率變動等案例
   • 做效能剖析（Profiler），定位 O(n) 熱點並以適當結構替換
   • 分層架構：資料層（Map/Node/Link）、演算法層（PathFinder）、應用層（API/UI）
   • 若資料量巨大，導入圖資料庫或離線索引、快取策略

關鍵要點清單

• 圖的資料建模：以 Node/Link 表達點與邊並加上權重（距離、費用）(優先級: 高)
• 成本函數設計：把商業規則（油價、油耗、過路費）轉為可計算的權重 (優先級: 高)
• DFS + 回溯：用遞迴與 Stack 列舉所有可行路徑 (優先級: 高)
• 走訪狀態管理：避免重複拜訪（避免回圈），需記錄 visited 集合 (優先級: 高)
• 資料結構選擇：用 HashSet 取代 Stack/List 的 Contains 以獲得 O(1) 查詢 (優先級: 高)
• 時間複雜度意識：辨識 O(n) 熱點與可改為 O(1)/O(log n) 的機會 (優先級: 高)
• Dictionary 的應用：以鍵快速定位節點，簡化 Map 操作 (優先級: 中)
• 遞迴 vs. 顯式 Stack：理解兩者等價性與呼叫堆疊的記憶體影響 (優先級: 中)
• 更佳演算法：認識 Dijkstra/A*，在大圖上勝過暴力枚舉 (優先級: 高)
• 集合運算：HashSet 的 Intersect/Union 等高效集合操作 (優先級: 中)
• 可擴充設計：將資料載入、演算法、成本規則解耦，利於維護 (優先級: 中)
• 測試與驗證：以小圖手算驗證正確性，再擴大資料集 (優先級: 中)
• 效能與架構取捨：先保證正確的資料結構與演算法，再做微優化 (優先級: 高)
• 資料庫思維：把 DB 當大型集合，索引/結構選擇等同於資料結構選擇 (優先級: 中)
• 實務資料品質：真實地圖不完美（封路、權重變動），需設計可更新的模型 (優先級: 低)