用分支限界法求解问题时应该先干什么

分支限界法是一种基于树的搜索算法，用于在一组可能的解中寻找最优解。在使用分支限界法解决问题时，我们应该先选择一个合适的数据结构来表示问题的解空间，然后确定问题的约束条件和目标函数。接着，我们需要创建一个活结点表，用于存储待扩展的节点。在活结点表中，我们需要按照某种启发式规则对节点进行排序，以便优先扩展最有可能得到最优解的节点。接着，我们可以从根节点开始，不断扩展活结点表中的节点，直到找到最优解或者所有节点都被扩展完毕。在扩展每个节点时，我们需要根据约束条件和目标函数来判断当前节点的子节点是否需要被扩展。如果一个子节点不满足约束条件或者其目标函数的下界已经低于当前已知的最优解，则可以剪枝，不必再扩展该子节点。最终，当所有节点都被扩展完毕时，我们就能得到问题的最优解。

相关问题

用分支限界法求解TSP问题的相关函数设计思想

分支限界法求解TSP问题需要设计以下几个函数：

1. 主函数：该函数是程序的入口，负责读取输入数据以及调用其他函数求解TSP问题。

2. 初始化函数：该函数负责初始化程序中需要用到的数据结构，例如邻接矩阵、已访问节点集合、未访问节点集合等。

3. 计算下界函数：该函数负责计算当前状态下的最优解下界，即当前路径长度加上剩余节点之间的最短路径长度。该函数需要通过调用最短路径算法来计算剩余节点之间的最短路径长度。

4. 扩展节点函数：该函数负责扩展当前节点，即将当前节点的所有未访问邻居节点加入到候选节点集合中，并计算候选节点对应的状态下界。

5. 选择节点函数：该函数负责从候选节点集合中选择一个节点作为下一步的扩展节点，通常选择状态下界最小的节点作为扩展节点。

6. 更新状态函数：该函数负责更新已访问节点集合、未访问节点集合以及当前路径长度等状态信息。

7. 回溯函数：该函数负责回溯到上一级节点，并更新相关状态信息。

以上这些函数是分支限界法求解TSP问题的核心函数，它们需要协同工作，才能达到求解TSP问题的目的。

c语言用分支限界法求解批处理作业调度问题

批处理作业调度问题是指在一台计算机上，有若干个作业需要完成，同时计算机有多个处理器可供使用。每个作业需要一定的处理时间，并且只能在某些特定的处理器上运行。如何安排作业的运行顺序和分配处理器，使得所有作业的完成时间最短，是批处理作业调度问题的核心。

分支限界法是一种常用的求解批处理作业调度问题的算法。具体步骤如下：

1. 定义状态空间。作业调度问题的状态可以表示为一个三元组 (j, Tj, Pj)，其中 j 表示当前正在处理的作业，Tj 表示已经处理完成的作业集合，Pj 表示尚未处理的作业集合。

2. 定义扩展规则。对于一个当前状态 (j, Tj, Pj)，可以扩展出若干个子状态。具体地，枚举尚未处理的作业集合 Pj 中的作业 i，将其加入到已经处理的作业集合 Tj 中，并计算当前正在处理的作业 j 和作业 i 的完成时间。然后将状态 (i, Tj ∪ {i}, Pj - {i}) 加入到状态空间中。

3. 定义优先队列。分支限界法需要维护一个优先队列，按照每个状态的完成时间从小到大排序。这样，每次从队首取出的状态，就是当前最优的状态。

4. 迭代搜索。不断从优先队列中取出队首状态，扩展出新的子状态，并将其加入到优先队列中。直到找到一个可行解或者优先队列为空为止。

5. 输出最优解。如果找到了可行解，输出最优解。否则，输出无解。

在具体实现时，可以使用 C 语言的优先队列数据结构和 STL 库中的 set、vector 等容器进行实现。