問題詳情

下列敘述何者為非?
(A) 在某圖的最小擴充樹(minimum spanning tree)中,一定包含加權最小的邊
(B) Topological Sort 可以用深度優先的搜尋方法(DFS)來實作
(C) 在某圖裡的某兩點之間的最短路徑中,一定包含加權最小的邊
(D) 最短路徑問題可以用動態規劃(dynamic programming)的演算法來求解

參考答案

答案:C
難度:適中0.428571
統計:A(17),B(19),C(60),D(18),E(0)

用户評論

【用戶】安身立命

【年級】國二下

【評論內容】動態規劃(Dynamic Programming)是指將一個較大的問題定義為較小的子問題組合,先處理較小的問題並將結果儲存起來(通常使用表格),再進一步以較小問題的解逐步建構出較大問題的解。

【用戶】william

【年級】大一下

【評論內容】Topological Sort 與 Topological Ordering「拓撲排序」是排序一張有向圖的點的方式。把圖上一條由 A 點連向 B 點的邊,想成是 A 必須排在 B 前方( B 必須排在 A 後方)。「拓撲排序」用來找出合理的排列順序,讓每一個點的先後順序,符合每一條邊所規定的先後順序。「拓撲順序」是指一張有向圖經過「拓撲排序」後,每一個點的先後順序。一張圖有許多種「拓撲順序」。只要不違背圖上每一條邊的先後規定,要怎麼排列圖上的點都行。