[TOC] # 概念 分支限界法類似于回溯法。分支界限法搜索解空間樹的方式是：**以廣度優先或者以最小耗費優先**。 * 搜索策略是：在擴展結點處生成，先生成其所有兒子結點（分支），然后再從當前活結點表中選擇下一個擴展結點。為了有效選擇下一個擴展結點，加速搜索的過程，在每個活結點處計算一個函數值（限界），并根據函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間上最優解的方向推進，以便盡快找到最優解。 # 基本思想 從活結點中選擇下一個擴展結點的不同方式，分支限界法分為兩種： * 隊列式（FIFO）分支限界法 隊列式分支限界法將活節點表組織成一個隊列，并按隊列先進先出的原則選取下一個結點為當前擴展結點。 * 優先隊列式分支界限法 將活節點表組織成一個優先隊列，并按優先隊列中規定的結點優先級選取優先級最高的下一個結點成為當前擴展結點。