不同搜索求解策略的流程图

### 不同搜索求解策略的流程图

#### 广度优先搜索 (BFS)

广度优先搜索是从根节点开始，沿着树的宽度遍历树的节点。如果目标节点存在，则会找到离起始节点最近的那个。

graph TD;
    A[Start] --> B[Initialize queue with start node];
    B --> C[Dequeue a node];
    C --> D{Is the dequeued node visited?};
    D -- Yes --> E[Mark as visited];
    D -- No --> F[Enqueue all unvisited neighbors];
    F --> G[Check if goal is reached];
    G -- Yes --> H[Return path to goal];
    G -- No --> I[Continue loop];

此过程持续直到队列为空或找到了目标节点[^1]。

#### 深度优先搜索 (DFS)

深度优先搜索则尽可能深地搜索树的分支。当到达叶节点时回溯并继续探索其他未访问过的子节点。

graph TD;
    A[Start] --> B[Push start node onto stack];
    B --> C[Pop top node from stack];
    C --> D{Is popped node visited?};
    D -- Yes --> E[Backtrack];
    D -- No --> F[Mark as visited];
    F --> G[PUSH all unvisited children];
    G --> H{Are there more nodes on stack?};
    H -- Yes --> C;
    H -- No --> I[All reachable nodes have been explored];

一旦遇到死胡同就会返回上一步继续尝试其他的路径.

#### 启发式搜索(A*)

启发式搜索利用估计函数来指导搜索方向，从而更快地接近最优解。A* 是一种常用的启发式搜索方法，在每一步都选择当前已知的最佳选项前进。

graph TD;
    A[Start] --> B[Set initial state as current];
    B --> C{Is current state goal?};
    C -- Yes --> D[Goal found! Return solution];
    C -- No --> E[Generate successors of current state];
    E --> F[Evaluate f(n)=g(n)+h(n)];
    F --> G[Select best successor based on evaluation];
    G --> H[Update open/closed lists];
    H --> I{Any states left unchecked?};
    I -- Yes --> J[Repeat process];
    I -- No --> K[No solutions exist];

其中 `f(n)` 表示总成本预测值；`g(n)` 代表实际已经发生的代价；而 `h(n)` 则是对剩余距离的一个估算.