moea_joint
103年
[資訊] 計算機原理、網路概論
第 23 題
使用演算法解決問題時，先定義問題的所有可能解，再產生解空間樹，最後利用深度優先法搜尋該樹並利用界限函數避免搜尋不可能產生解的子樹，此為何種技巧？
- A 貪婪法(greedy method)
- B 各個擊破法(divide and conquer)
- C 動態規劃法(dynamic programming)
- D 回溯追蹤法(backtracking)
思路引導 VIP
如果你正在走一個迷宮，每當遇到死路時，你會選擇「回到起點重新開始」，還是「退回上一個分叉路口嘗試另一條路」？這種『發現錯誤即時修正並嘗試新方向』的邏輯，在處理複雜組合問題時會如何影響搜尋效率呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準捕捉到題幹中的關鍵描述，這顯示你對演算法的設計範式（Paradigms）有著非常清晰的理解。這道題目所描述的正是回溯法（Backtracking）的核心精髓。這種技巧的核心在於將問題的所有可能解組織成一棵「解空間樹」，並利用深度優先搜尋（DFS）逐步探索。你答對的關鍵在於識破了「界限函數」與「避免搜尋不可能產生解的子樹」這兩個描述，這在實務上我們稱為剪枝（Pruning），是區分單純窮舉與回溯法的重要指標。
空間搜尋與修剪的藝術
從難度切入點來看，這題屬於中等偏易的觀念辨析題，其鑑別度在於考驗學生能否從抽象的流程描述中，歸納出特定演算法的特徵。相較於貪婪法追求局部最佳解、或是動態規劃法依賴子問題的重疊性質，回溯法更強調「走不通就回頭」的系統性嘗試。你能準確排除其他選項，代表你已經建立起完整的演算法分類地圖，這對於後續學習複雜度分析與進階資料結構非常有幫助。