學習目標：

• 掌握算法入門知識

學習內容：

• 分支限界的定義
• 例題詳細步驟講解（找牛）

---

1. 分支限界的定義

分支限界法是一種用于求解 組合優化問題 的算法框架，通過 系統性地搜索解空間樹，并結合 剪枝策略 來避免無效搜索，從而高效地找到最優解（如最小化代價或最大化收益）。其核心思想是：

• 分支（Branch）：將當前問題分解為若干子問題（即擴展解空間樹的分支）。例如：在旅行商問題（TSP）中，從一個城市出發，分支為所有可能的下一站城市。

• 限界（Bound）：計算每個子問題的 代價下界（對于最小化問題） 或 收益上界（對于最大化問題）。若某分支的當前界限 差于已知最優解，則直接剪枝，不再繼續搜索該分支。

隊列式分支限界法：將活結點表組織成一個隊列，并按照隊列先進先出（FIFO）原則選取下一個結點為擴展結點。步驟如下：

（1）將根結點加入活結點隊列。
（2）從活結點隊中取出隊頭結點，作為當前擴展結點。
（3）對當前擴展結點，先從左到右地產生它的所有孩子結點，用約束條件檢查，把所有滿足約束條件的孩子結點加入活結點隊列。
（4）重復步驟（2）和（3），直到找到一個解或活結點隊列為空為止。

2. 例題詳細步驟講解（找牛）

農夫知道一頭牛的位置，想要抓住它。
農夫和牛都位于數軸上，農夫起始位于點N(0<=N<=100000)，牛位于K(0<=K<=100000)。假設牛沒有意識到農夫的行動，站在原地不動。農夫最少要花多少時間才能抓住牛？
農夫有兩種移動方式：
<1> 從X移動到X-1或X+1，每次移動花費一分鐘
<2> 從X移動到2*X，每次移動花費一分鐘

假設農夫起始位于點2，牛位于7。即N=2，K=7。最右邊是8。 如何搜索到一條走到7的路徑？

思路：分支限界法采用廣度優先搜索。
初始化Queue = [ (2, 0) ]（初始位置 2，步數 0），visited = [0, 0, 1, 0, 0, 0, 0, 0, 0]（2 已訪問）

（1）當前位置 為2，可能的移動：2 → 1（左移）2 → 3（右移）2 → 4（跳躍）
更新隊列：Queue = [ (1,1), (3,1), (4,1) ]，visited 標記 1,3,4 為已訪問
（2）當前位置 = 1，可能的移動：1 → 0（左移）1 → 2（右移，2 已訪問）1 → 2（跳躍，2 已訪問）
更新隊列：Queue = [ (3,1), (4,1), (0,2) ]，visited 標記 0 為已訪問
（3）當前位置 = 3，可能的移動：3 → 2（左移，2 已訪問）3 → 4（右移，4 已訪問）3 → 6（跳躍）
更新隊列：Queue = [ (4,1), (0,2), (6,2) ]，visited 標記 6 為已訪問
（4）當前位置 = 4，可能的移動：4 → 3（左移，3 已訪問）4 → 5（右移）4 → 8（跳躍）
更新隊列：Queue = [ (0,2), (6,2), (5,2), (8,2) ]，visited 標記 5,8 為已訪問
（5）當前位置 = 0，可能的移動：0 → -1（左移，超出范圍，忽略）0 → 1（右移，1 已訪問）0 → 0（跳躍，無意義）
無新位置可擴展，隊列更新：Queue = [ (6,2), (5,2), (8,2) ]
（6）當前位置 = 6，可能的移動：6 → 5（左移，5 已訪問）6 → 7（右移）6 → 12（跳躍，12 > 8，超出范圍（限界））
發現 7 是目標！當前步數：2（從 2→4→6） + 1（從 6→7） = 3 分鐘

得到最優路徑：2 → 4 → 6 → 7（共 3 分鐘）

代碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define MAXN 100000int N, K;
int visited[MAXN + 10]; // 判重標記數組，visited[i]=1表示位置i已經訪問過// 定義結構體表示每一步的狀態
typedef struct {int x;      // 當前位置int steps;  // 到達當前位置所需的步數
} Step;// 隊列結構定義
typedef struct {Step data[MAXN + 10]; // 隊列數據存儲int front;           // 隊首指針int rear;            // 隊尾指針
} Queue;// 初始化隊列
void initQueue(Queue *q) {q->front = 0;q->rear = -1;
}// 判斷隊列是否為空
int isEmpty(Queue *q) {return q->front > q->rear;
}// 入隊操作
void enqueue(Queue *q, Step s) {if (q->rear < MAXN + 9) { // 防止隊列溢出q->data[++(q->rear)] = s;}
}// 出隊操作
Step dequeue(Queue *q) {return q->data[(q->front)++];
}int main() {// 輸入農夫和牛的位置scanf("%d %d", &N, &K);// 初始化訪問標記數組memset(visited, 0, sizeof(visited));Queue q;initQueue(&q);// 將初始狀態加入隊列enqueue(&q, (Step){N, 0});visited[N] = 1; // 標記初始位置已訪問while (!isEmpty(&q)) {Step current = dequeue(&q);// 如果當前位置就是牛的位置，輸出步數并結束if (current.x == K) {printf("%d\n", current.steps);return 0;}// 嘗試三種可能的移動方式// 1. 向左移動一步if (current.x - 1 >= 0 && !visited[current.x - 1]) {enqueue(&q, (Step){current.x - 1, current.steps + 1});visited[current.x - 1] = 1; // 標記已訪問}// 2. 向右移動一步if (current.x + 1 <= MAXN && !visited[current.x + 1]) {enqueue(&q, (Step){current.x + 1, current.steps + 1});visited[current.x + 1] = 1; // 標記已訪問}// 3. 跳躍到兩倍位置if (current.x * 2 <= MAXN && !visited[current.x * 2]) {enqueue(&q, (Step){current.x * 2, current.steps + 1});visited[current.x * 2] = 1; // 標記已訪問}}return 0;
}