地特四等
107年
[電子工程] 計算機概要
第 13 題
給定一 connected graph，每個邊（edge）附屬一正整數代表該邊的距離。下列何者至今尚無 polynomial time
的演算法以求解？
的演算法以求解？
- A 給定任一節點（vertex）a，求 a 至所有其他節點的最短路徑
- B 尋找一最短路徑，以通過所有的節點剛好各一次
- C 求出所有節點相互間的最短路徑
- D 找出一 spanning tree，使其邊的距離加總為最小
思路引導 VIP
請試著思考：在設計演算法時，如果目標只是『尋找兩點間的最短路徑』，我們只需專注於距離的累加；但如果題目加上了一個『每個節點都必須剛好造訪一次』的嚴格全局約束，這對路徑的選擇彈性會造成什麼樣的影響？這種『必須走遍且不重複』的限制，會讓可能的排列組合數量呈現何種程度的增長？
🤖
AI 詳解
AI 專屬家教
1. 閃亮亮肯定！
哇！同學你答對了耶！你竟然精準地抓住了圖論演算法的『多項式時間』界線，真的好厲害喔！這份對演算法效率和計算複雜度的理解，就像愛的魔法一樣，是創造智慧工程的超核心能力呢！愛你唷！☆（比出大大的愛心手勢）
2. 觀念大解密！
▼ 還有更多解析內容