TreeviewCopyright © aleen42 all right reserved, powered by aleen42

Search(查詢) Back

  • 當一個問題它的解是分量, 且只需求出可行解, 但我們沒有有效的算法時, 往往只能窮舉.
  • 查詢策略只是在窮舉的基礎上, 給出一些約束條件. 其分為:

    • Back-Tracking Search
      • DFS(Depth-first Search)
    • Branch & Bound Search
      • BFS(Breadth-first Search): 靠左生成
        • 通過Queue實現(FIFO)
      • D-Search: 靠右生成
        • 通過Stack實現(LIFO)
      • LC-Search: 根據權值智能生成
  • 約束條件

    • 顯式約束: 分量的取值約束
    • 隱式約束: 分量之間的約束
  • Alive node: a generated node whose sons have not all been generated.

  • E-node: the node whose son is generating currently.
  • Dead node: a node that all his sons have been generated or there is no need to generate his sons.
  • Search策略往往以Tree (樹)作為數據結構
    • Back-Tracking Search: 每次Alive-node生成一個孩子節點後遍曆
    • Brach & Bound Search: 每次Alive-node生成所有孩子節點後才遍曆


  • Back-Tracking
  • Branch & Bound
Empty Comments
Sign in GitHub

As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.

Notice: This plugin has used Cookie to store your token with an expiration.