民國114年 高考三級 統計 資料處理
第3題
BOM 表為一棵樹的結構，描述一產品P 的製作過程，其每一節點N 描 述P 之某一零組件C 的製程；而其所連結之子樹，描述組合該零組件 C，所需的所有零組件之製…
題目
BOM 表為一棵樹的結構，描述一產品P 的製作過程，其每一節點N 描 述P 之某一零組件C 的製程；而其所連結之子樹，描述組合該零組件 C，所需的所有零組件之製程。如圖範例所示，零組件 Ｃ是由零組件 C C C 、 及 所組合製作而成；零組件 C 是由零組件 C C 及 所組合製 作而成。而零組件 C C 及 何者先製作完成是無所謂；同樣地零組件 C C C 、 及 何者先製作完成也是無所謂。但在製作過程中，需先製作完 成零組件 C C 及 後，才能製作零組件 C ；且需先製作完成零組件 C C C 、 及 後，才能製作零組件 Ｃ。（每小題10 分，共20 分） 圖BOM 之範例 試寫一最快速演算法，列印出某一BOM 表所對應之產品P 之零組件 製程的製作順序。列印之順序為需先被生產之零組件的製程，需先被 列印出來。例如對範例圖所示，零組件 C C C 、 及 ，皆需比零組件 Ｃ 早被列印出來；而零組件 C C 及 ，皆需比零組件 C 早被列印出來。 若每一節點N，都有紀錄欲生產一件產品P 時，所需該節點之零組件 的製程時間Tc。且假設有充足機器及原物料，可供其隨時生產該節點 之零組件；即可忽略等待機器及原物料的準備時間。請寫一最快速演 算法，以計算當欲生產完一件產品P 之最快生產時間。
參考解答（AI 生成，非官方）
- （一）BOM 為樹，欲使子件先於父件列印，採 postorder（後序）DFS：從根 P 出發，遞迴走訪每一子節點，待所有子樹列印完再列印目前節點。每節點僅訪問一次，時間 O(V+E)=O(n)，已是樹狀 BOM 的最快演算法；兄弟順序不影響正確性。以題示 C0 由 C11、C12、C13 組成、C11 由 C21、C22 組成，可輸出 C21,C22,C11,C12,C13,C0。
- （二）虛擬碼：printBOM(N){ for each child C of N do printBOM(C); print(N); }，由 printBOM(P) 呼叫。若以 parent→child 儲存，後序即子先父後；若只存 child→parent，應先反轉邊或改用拓撲排序。若 BOM 不是樹而是共用零組件的 DAG，應改用 Kahn 拓撲排序，以 indegree 佇列輸出，複雜度同為 O(V+E)。遞迴過深時可用顯式堆疊模擬，避免 stack overflow。
- （三）設 Tc(N) 為節點 N 的製程時間，機器與物料充足可平行生產，則 N 的最早完工時間 T(N)=Tc(N)+max{T(C)|C 為 N 的子節點}；葉節點 T(N)=Tc(N)。父件須等所有子件完成才開始，故取最慢子件而非加總。由根後序計算，答案 T(P) 即 critical path（關鍵路徑）的加權長度：T(P)=max over root-to-leaf paths ΣTc（含根節點）。
- （四）虛擬碼：time(N){ if N is leaf return Tc(N); m=0; for each child C do m=max(m,time(C)); return Tc(N)+m; }。時間 O(n)、空間 O(h)。若題目的 Tc 不含組裝時間，應再加組裝時間；若機器或物料有限，平行假設不成立，問題變成資源受限排程，需以優先順序或整數規劃求解。題目未給各 Tc 數值，故只能列公式與步驟，無法算出唯一數值。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。