C++算法学习(分支限界法)

1、目标

找到在约束条件下的最优解

2、方法

以广度优先或以最小耗费优先的方式搜索解空间树。

3、具体实现

在分支限界法中，每个活的结点都有一次机会成为扩展结点，一次性产生其所有儿子结点。不合适的儿子结点被淘汰，只留下合适的进入队列，之前的出队列。个人感觉这个就是BFS，有其他理解可以讨论下。

4、例题:

建议各位手写一下，虽然是个人笔记，也希望对网友有作用吧。

1、练广度优先遍历的基础

(1)力扣:剑指 Offer 32 - I. 从上到下打印二叉树

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
if(!root) return {};
queue<TreeNode *> mes;
vector<int> answer;
mes.push(root);
while(!mes.empty()){
TreeNode * node = mes.front();
mes.pop();
if(node->left) mes.push(node->left);
if(node->right) mes.push(node->right);
answer.push_back(node->val);
}
return answer;
}
};

(2)力扣:剑指 Offer 32 - II. 从上到下打印二叉树 II

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root) return {};
vector<vector<int>> a;
queue<TreeNode*> data;
data.push(root);
while(data.size()){
int num = data.size();
vector<int> ai;
for(int i = 0;i < num;i++){
TreeNode * node = data.front();
data.pop();
if(!node) continue;
if(node->left) data.push(node->left);
if(node->right) data.push(node->right);
ai.push_back(node->val);
}
if(ai.size() != 0) a.push_back(ai);
}
return a;
}
};

(2)力扣:剑指 Offer 32 - III. 从上到下打印二叉树 III

这个就当练练手其实和前面差不多，这个给大家介绍一个方法：

v.insert(v.begin(),data);//把data插入到vector的最前面

/**
* Definition for a binary tree node.
* struct TreeNode {
*
int val;
*
TreeNode *left;
*
TreeNode *right;
*
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root) return {};
vector<vector<int>> a;
queue<TreeNode*> data;
data.push(root);
int floor = 0;
while(data.size()){
floor++;
int num = data.size();
vector<int> ai;
for(int i = 0;i < num;i++){
TreeNode * node = data.front();
data.pop();
if(!node) continue;
if(node->left) data.push(node->left);
if(node->right) data.push(node->right);
if(floor%2 == 0) ai.insert(ai.begin(),node->val);
else ai.push_back(node->val);
}
if(ai.size() != 0) a.push_back(ai);
}
return a;
}
};

2、使用广度优先遍历

(1)力扣:542. 01 矩阵

class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
//准备工作
queue<pair<int, int>> q;
int row = matrix.size();
int col = matrix[0].size();
//开始第一步把0放入队列
for(int i = 0;i < row;i++)
for(int j = 0;j < col;j++){
if(matrix[i][j] == 0)
q.push({i,j});
else matrix[i][j] = -1;
}
//开始插入
int a[] = {-1,1,0,0};
int b[] = {0,0,1,-1};
while(!q.empty()){
pair<int,int> pair_data = q.front();
q.pop();
for(int i = 0;i <4;i++){
int newX = pair_data.first + a[i];
int newY = pair_data.second + b[i];
if(newX >= 0
&& newX < row
&& newY >= 0
&& newY < col
&& matrix[newX][newY] == -1)
{
matrix[newX][newY] = matrix[pair_data.first][pair_data.second] + 1;
q.push({newX,newY});
}
}
}
return matrix;
}
};

有点网抑云了，害，先不写了，以后遇到分支界限的问题都会更新，主要用于个人笔记，也希望对大家有一点帮助。

最后

以上就是鳗鱼胡萝卜为你收集整理的C++算法学习(分支限界法)的全部内容，希望文章能够帮你解决C++算法学习(分支限界法)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。