【預告】4/1起,頁面上方功能列以及下方資訊全面更換新版。 前往查看

教甄◆電腦科專業題庫下載題庫

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


答案:C
難度: 困難
1F
安身立命 國二下 (2016/04/16)
動態規劃(Dynamic Programming)是指將一個較大的問題定義為較小的子問題組合,先處理較小的問題並將結果儲存起來(通常使用表格),再進一步以較小問題的解逐步建構出較大問題的解。
2F
william 大三上 (2019/03/19)

Topological Sort 與 Topological Ordering

「拓撲排序」是排序一張有向圖的點的方式。把圖上一條由 A 點連向 B 點的邊,想成是 A 必須排在 B 前方( B 必須排在 A 後方)。「拓撲排序」用來找出合理的排列順序,讓每一個點的先後順序,符合每一條邊所規定的先後順序。

「拓撲順序」是指一張有向圖經過「拓撲排序」後,每一個點的先後順序。一張圖有許多種「拓撲順序」。只要不違背圖上每一條邊的先後規定,要怎麼排列圖上的點都行。

下列敘述何者為非? (A) 在某圖的最小擴充樹(minimum spannin..-阿摩線上測驗