void bfs() { int j; NodeType e, e1; priority_queue<NodeType>qu; //定义队列 memset(e.x, 0, sizeof(e.x)); //初始化根节点的x值 memset(e.worker, 0, sizeof(e.worker)); //初始化根节点的worker e.i = 0; e.cost = 0; bound(e); //求根节点的lb e.no = total++

; //给根节点编号 qu.push(e); //将根节点压入队列 while (!qu.empty()) { e = qu.top(); //取出队首元素 qu.pop(); //弹出队首元素 if (e.i == n) { //搜索到叶子节点，更新最优解 if (e.cost < bestc) { bestc = e.cost; memcpy(bestx, e.x, sizeof(e.x)); } continue; } for (j = 1; j <= n; j++) { if (e.worker[j] == 0) { e1 = e; e1.x[e.i][j] = 1; e1.worker[j] = 1; //将任务j分配给工人 e1.cost += cost[e.i][j]; //计算分配任务j的代价 e1.i++; //转移到下一层 bound(e1); //求当前节点的下界 if (e1.bound < bestc) { //如果下界小于当前最优解，将节点压入队列 e1.no = total++; qu.push(e1); } } } } }

这是一个求解任务分配问题的代码，使用了优先队列实现了分支限界算法。首先将根节点压入队列，然后每次取出队首元素进行扩展，对于每个可行的扩展，计算下界，如果下界小于当前最优解，则将其压入队列。整个搜索过程中，队列按照下界从小到大排序，保证了每次取出的都是下界最小的节点进行扩展，从而尽可能地快速地搜索到最优解。