《算法设计与分析》第五六章:回溯法与分支限界法

文章目录

  • 回溯法
  • 分支限界法
  • 一、本章作业
    • 1.活动安排问题
    • 2.旅行商问题
    • 3.单源最短路径
    • 4.任务分配问题
  • 二、算法积累
    • 1.回溯法求解01背包问题
    • 2.回溯法求解最大团问题
    • 3.回溯法求解n皇后问题
    • 4.回溯法求解地图着色
    • 5.回溯法求解哈密尔顿图
    • 6.回溯法求活动安排
    • 7.分支限界法求01背包问题
    • 8.分支限界法求单源最短路径
    • 9.分支限界法求解八数码问题
    • 10.流水作业调度

回溯法

回溯法类似于枚举(穷举、蛮力),通过深度优先搜索策略遍
历问题的所有可能解的通路,发现此路不通时,回溯到上一
步继续尝试别的通路。
回溯法适用于查找问题的所有解集或符合某种限制条件的最
佳解集。具体实现时,采用剪枝策略进行搜索范围控制,提
高效率。但其最坏时间复杂度仍然很高。
对于NPC问题来说,回溯法被认为是目前较为有效的方法。
回溯算法的基本步骤:

(1)定义问题的解空间(描述解):用一个什么样的向量表示
问题的解?该向量中的每个变量如何取值?
(2)确定解空间的结构:子集树? 排列树? 以及每个节点和
边的含义。
(3)确定剪枝函数,以深度优先搜索解空间。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

分支限界法

分支限界法对问题的解空间树进行 广度搜索的过程。其
步骤如下:

(1)生成根节点,进队列;
(2)只要队列不空:

(a)出队一个结点(FIFO或优先队列)作为扩展结点;
(b)产生其所有孩子结点,抛弃那些不可能产生可行解
或最优解的结点,将其余的孩子结点加入活结点表。

应用分支限界法的关键问题,主要包括:

(1)如何确定合适的限界函数,用于剪枝
(2)如何组织待处理活结点表( FIFO;优先队列)
(3)如何确定最优解中的各个分量(各结点存储;全局变量存储;构建树 )

队列式分支限界法:

(1)按照队列先进先出原则选取下一个结
点为扩展结点。
(2)优先队列式分支限界法:以最小耗费(最大效益)优先的
方式搜索解空间树,即按照优先队列中规定的优先级选取
优先级最高的结点成为当前扩展结点。常用堆(大根堆 /小
根堆)来实现。

一、本章作业

1.活动安排问题

假设有个活动需要使用某一资源,该资源任何时刻只能被一个活动所占用,每个活动i有一个开始时间bi和结束时间ei(bi<ei),且一旦某个活动开始执行,中间不能被打断,直到其执行完毕。如何安排活动,使得能安排尽可能多的活动。

  • 可行性: 在每次递归调用中,首先检查当前活动是否可以选择。这是通过检查当前要选择的活动 A[x[i]] 是否与已经选择的活动时间兼容来完成的。
  • 递归回溯: 如果当前活动不能选择,直接递归到下一个活动;如果可以选择,则选择并递归进入下一个活动。
  • 最优性: 在完成一次完整的活动选择后,检查当前的活动选择方案是否比记录的最优方案更优。如果是,则更新最优解向量 bestx[] 和最大兼容活动数 maxsum。
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100;

struct Action 
{
	int b; // 开始时间
	int e; // 结束时间
};

int n = 4;
Action A[] = {{0, 0}, {1, 3}, {2, 5}, {4, 8}, {6, 10}};

int x[MAXN]; // 临时解向量
int bestx[MAXN]; // 最优解向量
int laste = 0; // 结束时间
int sum = 0; 
int maxsum = 0;

void dfs(int i) 
{
	if (i > n) 
	{
		if (sum > maxsum) 
		{
			maxsum = sum;
			for (int j = 1; j <= n; j++)
				bestx[j] = x[j];
		}
	} 
    else 
    {
		// 不选择第i个活动
		x[i] = 0;
		dfs(i + 1);
		
		// 选择第i个活动
		if (A[i].b >= laste) 
		{
			int sum1 = sum;
			int laste1 = laste;
			sum++;
			laste = A[i].e;
			x[i] = 1;
			dfs(i + 1);
			// 回溯
			sum = sum1;
			laste = laste1;
		}
	}
}

void dispasolution() 
{
	int laste = 0;
	cout << "最优调度方案:\n";
	for (int j = 1; j <= n; j++) 
	{
		if (bestx[j] == 1) 
		{
			cout << "选取活动" << j << " [" << A[j].b << "," << A[j].e << "]\n";
			laste = A[j].e; // 更改为当前活动的结束时间
		}
	}
	cout << "兼容活动的个数=" << maxsum << endl;
}

int main() 
{
	for (int i = 1; i <= n; i++) 
	{
		x[i] = 0;
	}
	
	dfs(1); // 从第1个活动开始搜索
	dispasolution(); // 输出结果
	
	return 0;
}

2.旅行商问题

从某个固定的顶点出发,求解旅行商问题,输出一个最优解(包含路径和总费用)。

  • 用排列树求解
  • backtrack 函数:如果当前已经排列了 n 个节点,并且形成了一个回路且成本小于当前最优解,则更新最优解。否则,遍历剩下的节点,尝试每个节点作为当前节点,并递归求解。
  • 边的存在性检查:在尝试选择一个节点作为下一个节点时,首先检查从当前节点到下一个节点是否有一条边存在,即a[x[t-1]][x[i]]是否为非零。
    如果不存在这条边,则跳过这个选择,避免无效的搜索。
  • 当前成本检查:在选择一个节点作为下一个节点时,检查当前成本加上从当前节点到下一个节点的边的成本是否小于当前已知的最优成本bestc。如果当前成本加上这条边的成本已经超过最优成本,则剪枝,避免进一步的搜索。
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

const int maxn = 100;
int n;
int a[maxn][maxn];  // 图的邻接矩阵
int x[maxn];        // 当前解
int bestx[maxn];    // 最优解
int bestc = INT_MAX; // 最优解的成本
int cc = 0;          // 当前成本

void backtrack(int t)
{
	if (t == n + 1)  // 修改判断条件,确保包含所有节点
	{
		if (a[x[n]][x[1]] && (cc + a[x[n]][x[1]] < bestc))
		{
			for (int j = 1; j <= n; j++)
				bestx[j] = x[j]; // 最优解
			bestc = cc + a[x[n]][x[1]];
		}
	}
	else
	{
		for (int i = t; i <= n; i++)
		{
			if (a[x[t-1]][x[i]] && (cc + a[x[t-1]][x[i]] < bestc))
			{
				swap(x[t], x[i]);
				cc += a[x[t-1]][x[t]];
				backtrack(t + 1);  // 递归
				cc -= a[x[t-1]][x[t]];  // 回溯
				swap(x[t], x[i]);
			}
		}
	}
}

int main()
{
	cout << "请输入节点数:";
	cin >> n;
	
	cout << "请输入邻接矩阵:" << endl;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];
	
	for (int i = 1; i <= n; i++)
		x[i] = i;
	
	backtrack(2);  // 从第2个节点开始,因为第1个节点是固定的起点
	
	if (bestc == INT_MAX)
		cout << "No Solution!" << endl;
	else
	{
		cout << "最优解的路径为:";
		for (int i = 1; i <= n; i++)
			cout << bestx[i] << "-";
		cout << bestx[1] << endl;
		cout << "最小成本为:" << bestc << endl;
	}
	
	return 0;
}
  • 分支限界:
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100;
int n;
int a[maxn][maxn];  // 图的邻接矩阵
int bestx[maxn];    // 最优解
int bestc = INT_MAX; // 最优解的成本

struct Node 
{
    vector<int> path; // 当前路径
    int cost; // 当前路径的成本
    int bound; // 当前节点的下界
    int level; // 当前节点在搜索树中的层次
    
    bool operator<(const Node& other) const 
    {
        return bound > other.bound; // 优先选择下界值较小的节点
    }
};

// 计算当前节点的下界
int calculateBound(Node node) 
{
    int cost = node.cost;
    int bound = cost;

    bool visited[maxn] = { false };
    for (int i : node.path) 
    {
        visited[i] = true;
    }

    // 计算还没有访问的节点的最小边
    for (int i = 1; i <= n; i++) 
    {
        if (!visited[i]) 
        {
            int minEdge = INT_MAX;
            for (int j = 1; j <= n; j++) 
            {
                if (!visited[j] && a[i][j] < minEdge && a[i][j] > 0) 
                {
                    minEdge = a[i][j];
                }
            }
            bound += minEdge;
        }
    }
    return bound;
}

void branchAndBound() 
{
    priority_queue<Node> pq;
    Node startNode;
    startNode.path.push_back(1); // 从第1个节点开始
    startNode.cost = 0;
    startNode.bound = calculateBound(startNode);
    startNode.level = 1;

    pq.push(startNode);

    while (!pq.empty()) 
    {
        Node currentNode = pq.top();
        pq.pop();

        if (currentNode.level == n) 
        {
            if (a[currentNode.path.back()][1] > 0 && (currentNode.cost + a[currentNode.path.back()][1] < bestc)) 
            {
                bestc = currentNode.cost + a[currentNode.path.back()][1];
                for (int i = 0; i < n; i++) 
                {
                    bestx[i + 1] = currentNode.path[i];
                }
            }
        } 
        else 
        {
            for (int i = 2; i <= n; i++) 
            {
                if (find(currentNode.path.begin(), currentNode.path.end(), i) == currentNode.path.end() && a[currentNode.path.back()][i] > 0) 
                {
                    Node nextNode = currentNode;
                    nextNode.path.push_back(i);
                    nextNode.cost += a[currentNode.path.back()][i];
                    nextNode.bound = calculateBound(nextNode);
                    nextNode.level = currentNode.level + 1;

                    if (nextNode.bound < bestc) 
                    {
                        pq.push(nextNode);
                    }
                }
            }
        }
    }
}

int main()
{
    cout << "请输入节点数:";
    cin >> n;
    
    cout << "请输入邻接矩阵:" << endl;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    
    branchAndBound();
    
    if (bestc == INT_MAX)
        cout << "No Solution!" << endl;
    else
    {
        cout << "最优解的路径为:";
        for (int i = 1; i <= n; i++)
            cout << bestx[i] << "-";
        cout << bestx[1] << endl;
        cout << "最小成本为:" << bestc << endl;
    }
    
    return 0;
}

3.单源最短路径

给定带权有向图G=(V,E),其中每条边的权是非负实数。给定一个源点,设计算法求解从源点到所有其它各顶点的最短路径,输出到每个点的路径长度及路径。

  • 采用FIFO队列式分支限界法求解
  • 剪枝:只有下一步达到的点,可以更新该点的最短距离才可以向下走,不然就剪枝
    在这里插入图片描述
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f  // 表示∞
#define MAXN 51

// 问题表示
int n;                  // 图顶点个数
int a[MAXN][MAXN];      // 图的邻接矩阵
int v;                  // 源点

// 求解结果表示
int dist[MAXN];         // dist[i] 源点到顶点i的最短路径长度
int previous[MAXN];     // previous[i] 表示源点到i的最短路径中顶点i的前驱顶点

struct NodeType         // 队列结点类型
{
    int vno;            // 顶点编号
    int length;         // 路径长度
};

void bfs(int v)         // 求解算法
{
    NodeType e, e1;
    queue<NodeType> qu;
    e.vno = v;          // 建立源点结点e(根结点)
    e.length = 0;       // 源点结点e进队
    qu.push(e);
    dist[v] = 0;
    
    while(!qu.empty())  // 队列不空循环
    {
        e = qu.front(); qu.pop(); // 退出队列结点e
        for (int j = 0; j < n; j++)
        {
            if(a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j])
            {
                // 算法:e.vno到顶点j有边并且路径长度更短
                dist[j] = e.length + a[e.vno][j];
                previous[j] = e.vno;  // 建立相应顶点j的结点e1
                e1.vno = j;
                e1.length = dist[j];  // 结点e1进队
                qu.push(e1);
            }
        }
    }
}

int main()
{
    // 读入图的顶点个数
    scanf("%d", &n);
    
    // 读入图的邻接矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    
    // 读入源点
    scanf("%d", &v);
    
    // 初始化dist数组
    for (int i = 0; i < n; i++)
    {
        dist[i] = INF;
        previous[i] = -1;
    }
    
    // 调用bfs算法
    bfs(v);
    
    // 输出最短路径长度
    for (int i = 0; i < n; i++)
    {
        if (dist[i] == INF)
        {
            printf("INF ");
        }
        else
        {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
    
    // 输出最短路径的前驱节点
    for (int i = 0; i < n; i++)
    {
        printf("%d ", previous[i]);
    }
    printf("\n");
    
    return 0;
}

4.任务分配问题

有n(n≥1)个任务需要分配给n个人执行,每个任务只能分配给一个人,每个人只能执行一个任务。第i个人执行第j个任务的成本是c[i][j](1≤i,j≤n)。求出总成本最小的分配方案。
在这里插入图片描述

  • 剪枝策略:限界函数 bound(Node& e) 确定了每个节点的下界,以便优先队列能够以最优的方式扩展节点。条件 if (e1.lb <= mincost) 确保只有当新生成的节点有可能带来更优解时,才会继续扩展。如果不可能,就会提前停止无效搜索路径,提高了算法的效率。
#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f
#define MAXN 21

struct Node		//队列结点类型
{
    int no;			    //结点编号
    int i;			    //表示当前结点属于解空间的第i层(根节点的层次为0),即准备为人员i分配任务
    int x[MAXN];		//x[i]为人员i分配的任务编号
    bool worker[MAXN];	//worker[i]=true表示任务i已经分配
    int cost;			//已经分配任务所需要的成本
    int lb;			    //下界
    bool operator<(const Node& s) const	//重载<关系函数>
    {
        return lb > s.lb;   
    }
};
//问题表示
int n = 4;
int c[MAXN][MAXN] = { {0},{0,9,2,7,8},{0,6,4,3,7},
    {0,5,8,1,8},{0,7,6,9,4} };
//下标0的元素不用
int bestx[MAXN];		//最优分配方案
int mincost = INF;		//最小成本
int total = 1;			//结点个数累计
void bound(Node& e)     //求结点e的限界值
{
    int minsum = 0;
    for (int i1 = e.i + 1;i1 <= n;i1++)      //寻找每一行的最小值
    {                                        //如果找到e这个节点,如果说他选择了某个任务的话,就不能选择那一列的值了
        int minc = INF;
        for (int j1 = 1;j1 <= n;j1++)
            if (e.worker[j1] == false && c[i1][j1] < minc)           
                minc = c[i1][j1];                       
        minsum += minc;              
    }
    e.lb = e.cost + minsum;          //e.cost代表选择的结点成本+剩下的最小的成本
    //cout << e.lb << " ";           //可以自行选择输出不输出
}
 
void bfs()
{
    int j;
    Node e, e1;                  //e,e1相当于两个儿,帮忙运进队列的
    priority_queue<Node> qu;                  
    memset(e.x, 0, sizeof(e.x));               //解向量
    memset(e.worker, 0, sizeof(e.worker));     //任务是否分配
    e.i = 0;                      //根节点也是虚结点
    e.cost = 0;
    bound(e);
    e.no = total++;
    qu.push(e);
    while (!qu.empty())
    {
        e = qu.top();
        qu.pop();
        if (e.i == n)
        {
            if (e.cost < mincost)
            {
                mincost = e.cost;
                for (j = 1;j <= n;j++)
                    bestx[j] = e.x[j];
            }
        }
        e1.i = e.i + 1;         //相当于在根节点的情况下开始拓展进行下一个节点
        for (j = 1;j <= n;j++)
        {
            if (e.worker[j])     //查看任务j是否分配
                continue;
            for(int i1 = 1;i1 <= n;i1++)
                e1.x[i1] = e.x[i1];         //相当于对e1初始化(1)
            e1.x[e1.i] = j;             
            for (int i2 = 1;i2 <= n;i2++)
                e1.worker[i2] = e.worker[i2];     //相当于对e1初始化(2)  :::(1)(2)就相当于创建了一个新的结点并且对他初始化
            e1.worker[j] = true;           //这个代表的是它的第几个任务被选择
            e1.cost = e.cost + c[e1.i][j];
            bound(e1);
            e1.no = total++;
            if (e1.lb <= mincost)     //剪枝
                qu.push(e1);
        }
    }
}
int main()
{
    bfs();
    cout << "最优方案:" << endl;
    for (int k = 1;k <= n;k++)
    {
        cout << "第" << k << "个人员分配第" << bestx[k] << "个任务" << endl;
    }
    cout << "总成本" << mincost;
    return 0;
}

二、算法积累

1.回溯法求解01背包问题

在这里插入图片描述

  • 运用子集树进行求解
    在这里插入图片描述
  • 两个限制条件:
  • 超过最大重量:
    在这里插入图片描述
  • 不能满足最优解,即已经小于当前得出的最大价值
    在这里插入图片描述
#include <bits/stdc++.h>

using namespace std;

const int MMM = 1e5 + 20;
int n;
int c;
int w[MMM],v[MMM];
int x[MMM],op[MMM];
int maxv;


void dfs(int i, int tw, int tv, int rv, int op[])
{
	int j;
	if(i>n)
	{
		if(tw <= c && tv > maxv)
		{
			maxv = tv;
			for(j = 1; j <= n; j ++ )
				x[j] = op[j];
		}
	}
	else
	{
		if(tw + w[i] <= c)
		{
			op[i] = 1;
			dfs(i + 1, tw + w[i], tv + v[i], rv - v[i], op);
		}
		if(tv + rv - v[i] > maxv)
		{
			op[i] = 0;
			dfs(i + 1, tw, tv, rv-v[i], op);
		}
	}
}

int main()
{
	cout << "输入物品数和限重:"<<endl;
	cin >> n >> c;
	cout << "输入每个物品的重量和价值"<<endl;
	int rv = 0;
	for(int i = 1; i <= n; i ++ )
	{
		cin >> w[i] >> v[i];
		rv += v[i];
	}
	dfs(0, 0, 0,rv,op);
	for(int i = 1; i <= n; i ++ )
	{
		cout << x[i] << ' ';
	}
}

2.回溯法求解最大团问题

在这里插入图片描述

  • 用子集树:
    在这里插入图片描述
  • 剪枝:
    在这里插入图片描述
#include <bits/stdc++.h>

using namespace std;

#define MAXN 1000

int n;
bool graph[MAXN][MAXN];
bool cand[MAXN]; // 候选解
bool best[MAXN]; // 当前最优解
int maxsize; // 当前最优解大小

// 检查是否满足约束条件
bool check(int i) 
{
	for (int j = 0; j < n; j++) 
	{
		if (cand[j] && !graph[i][j]) return false; // 如果候选解中有与i不相邻的顶点,则返回false
	}
	return true; // 否则返回true
}

// 回溯法求解最大团
void backtrack(int i, int size) 
{
	// 如果考虑完所有顶点
	if (i >= n) 
	{
		if (size > maxsize) 
		{
			maxsize = size; // 更新当前最优解大小
			for (int j = 0; j < n; j++) 
			{
				best[j] = cand[j]; // 更新当前最优解
			}
		}
	} 
	else 
	{
		// 如果满足约束条件
		if (check(i)) 
		{
			cand[i] = true; // 将i加入候选解
			backtrack(i + 1, size + 1); // 递归考虑下一个顶点
		}
		// 如果满足限界条件
		if (n - i + size > maxsize) 
		{
			cand[i] = false; // 不将i加入候选解
			backtrack(i + 1, size); // 递归考虑下一个顶点
		}
	}
}

void output() 
{
	printf("给定无向图中最大团中定点的个数为:%d\n", maxsize); // 输出当前最优解大小
	printf("具体定点为:");
	for (int i = 0; i < n; i++) 
	{
		if (best[i]) printf("%d ", i + 1); // 输出当前最优解中的顶点
	}
	printf("\n");
}

int main() 
{
	cin >> n;
	
	cout << "输入邻接矩阵(如果两个顶点之间有边,则输入1;否则输入0):" << endl;
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < n; j++) 
		{
			int x;
			scanf("%d", &x);
			graph[i][j] = x == 1;
		}
	}
	
	backtrack(0, 0); // 调用回溯法函数求解最大团
	
	output(); // 输出结果及其文字说明
	
	return 0;
}
//5
//0 1 1 1 1
//1 0 1 0 1
//1 1 0 0 1
//1 0 0 0 1
//1 1 1 1 0

3.回溯法求解n皇后问题

在这里插入图片描述

  • 用m叉树求解:

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

  • 用排列数求解:

在这里插入图片描述

#include <bits/stdc++.h>

using namespace std;

int x[100];        //皇后的位置(i,x[i]),即x[i]表示皇后在i行的列位置
int n;            //棋盘规格
int sum = 0;

bool Place(int t)    //实现限界约束判断
{
	//检查与之前放置的是否冲突
	for (int i = 1; i < t;i++)
		if(abs(i-t)==abs(x[i]-x[t])||x[i]==x[t])
			return false;
	return true;
}

void Backtrack(int t)
{
	if(t>n)
	{
		sum++;
		for (int i = 1; i <= n;i++)
			cout << "(" << i << "," << x[i] << ")"
			<< " ";
		cout << endl;
	}
	else
	{
		for (int i = t; i <= n;i++)
		{
			swap(x[i], x[t]);
			if(Place(t))
				Backtrack(t + 1);
			swap(x[i], x[t]);
		}
	}
}
int main()
{
	cout << "请输入棋盘规格或者皇后数量" << endl;
	cin >> n;
	for (int i = 1; i <= n;i++)
		x[i] = i;
	Backtrack(1);
	cout << sum << endl;
	return 0;
}

4.回溯法求解地图着色

在这里插入图片描述

  • 利用m叉树求解:
    在这里插入图片描述

  • 剪枝:
    在这里插入图片描述

  • isSafe 函数用于检查是否可以为当前节点 node 着色。它检查与当前节点相邻的所有节点,如果任一相邻节点已经着色并且颜色与当前尝试的颜色 c 相同,则返回 false。否则返回 true。

  • graphColoringUtil 是递归函数,用于尝试为每个节点着色。主要逻辑如下:

    • 如果所有节点都已着色(node == SIZE),则返回 true。
    • 否则,尝试为当前节点着色,从颜色 1 到 m(最大颜色数)。
    • 如果可以安全地为当前节点着色,则递归调用自身处理下一个节点。
    • 如果无法为当前节点找到合适的颜色,则回溯,将当前节点颜色重置为 0。
#include <iostream>
#define SIZE 5

using namespace std;

void inputGraph(int graph[][SIZE])
{
	int i, j;
	for (i = 0; i < SIZE; i++)
	{
		for (j = 0; j < SIZE; j++)
		{
			cin >> graph[i][j];
		}
	}
}

bool isSafe(int node, int graph[][SIZE], int color[], int c)
{
	for (int i = 0; i < SIZE; i++)
	{
		if (graph[node][i] && c == color[i])
		{
			return false;
		}
	}
	return true;
}

bool graphColoringUtil(int graph[][SIZE], int m, int color[], int node)
{
	if (node == SIZE)
	{
		return true;
	}
	
	for (int c = 1; c <= m; c++)
	{
		if (isSafe(node, graph, color, c))
		{
			color[node] = c;
			if (graphColoringUtil(graph, m, color, node + 1))
			{
				return true;
			}
			color[node] = 0; // backtrack
		}
	}
	
	return false;
}

bool graphColoring(int graph[][SIZE], int m, int color[])
{
	return graphColoringUtil(graph, m, color, 0);
}

void output(int color[])
{
	for (int i = 0; i < SIZE; i++)
	{
		cout << "第" << i + 1 << "个区域的颜色是" << color[i] << endl;
	}
}

int main()
{
	int graph[SIZE][SIZE];
	int color[SIZE];
	
	for (int i = 0; i < SIZE; i++)
	{
		color[i] = 0;
	}
	
	cout << "请输入图的邻接矩阵:" << endl;
	inputGraph(graph);
	
	int m = 4; // 最大颜色数
	
	if (graphColoring(graph, m, color))
	{
		output(color);
	}
	else
	{
		cout << "无法使用" << m << "种颜色着色图" << endl;
	}
	
	return 0;
}

5.回溯法求解哈密尔顿图

在这里插入图片描述
在这里插入图片描述

  • 用排列树求解
  • backtrack 函数:如果当前已经排列了 n 个节点,并且形成了一个回路且成本小于当前最优解,则更新最优解。否则,遍历剩下的节点,尝试每个节点作为当前节点,并递归求解。

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

const int maxn = 100;
int n;
int a[maxn][maxn];  // 图的邻接矩阵
int x[maxn];        // 当前解
int bestx[maxn];    // 最优解
int bestc = INT_MAX; // 最优解的成本
int cc = 0;          // 当前成本

void backtrack(int t)
{
	if (t == n + 1)  // 修改判断条件,确保包含所有节点
	{
		if (a[x[n]][x[1]] && (cc + a[x[n]][x[1]] < bestc))
		{
			for (int j = 1; j <= n; j++)
				bestx[j] = x[j]; // 最优解
			bestc = cc + a[x[n]][x[1]];
		}
	}
	else
	{
		for (int i = t; i <= n; i++)
		{
			if (a[x[t-1]][x[i]] && (cc + a[x[t-1]][x[i]] < bestc))
			{
				swap(x[t], x[i]);
				cc += a[x[t-1]][x[t]];
				backtrack(t + 1);  // 递归
				cc -= a[x[t-1]][x[t]];  // 回溯
				swap(x[t], x[i]);
			}
		}
	}
}

int main()
{
	cout << "请输入节点数:";
	cin >> n;
	
	cout << "请输入邻接矩阵:" << endl;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> a[i][j];
	
	for (int i = 1; i <= n; i++)
		x[i] = i;
	
	backtrack(2);  // 从第2个节点开始,因为第1个节点是固定的起点
	
	if (bestc == INT_MAX)
		cout << "No Solution!" << endl;
	else
	{
		cout << "最优解的路径为:";
		for (int i = 1; i <= n; i++)
			cout << bestx[i] << "-";
		cout << bestx[1] << endl;
		cout << "最小成本为:" << bestc << endl;
	}
	
	return 0;
}

6.回溯法求活动安排

在这里插入图片描述

  • 利用子集树求解:
    在这里插入图片描述
  • 利用排列数求解:
    在这里插入图片描述
  • 排列树求解:
  • 采用回溯法求解,相当于找到S={1,…,n}的某个排列即调度方案,使得其中所有兼容活动个数最多,显然对应的解空间是一个是排列树。直接采用排列树递归框架实现,对于每一种调度方案求出所有兼容活动个数,通过比较求出最多活动个数maxsum,对应的调度方案就是最优调度方案bestx,即为本问题的解。
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100;

struct Action 
{
	int b; // 开始时间
	int e; // 结束时间
};

int n = 4;
Action A[] = {{0, 0}, {1, 3}, {2, 5}, {4, 8}, {6, 10}};

int x[MAXN]; // 临时解向量
int bestx[MAXN]; // 最优解向量
int laste = 0; // 结束时间
int sum = 0; 
int maxsum = 0;

void dfs(int i) 
{
	if (i > n) 
	{
		if (sum > maxsum) 
		{
			maxsum = sum;
			for (int j = 1; j <= n; j++)
				bestx[j] = x[j];
		}
	} else 
	{
		for (int j = i; j <= n; j++) 
		{
			swap(x[i], x[j]);
			int sum1 = sum;
			int laste1 = laste;
			if (A[x[i]].b >= laste) 
			{ // 开始时间大于当前结束时间
				sum++;
				laste = A[x[i]].e;
			}
			dfs(i + 1);
			// 回溯
			swap(x[i], x[j]);
			sum = sum1;
			laste = laste1;
		}
	}
}

void dispasolution() 
{
	int laste = 0;
	cout << "最优调度方案:\n";
	for (int j = 1; j <= n; j++) 
	{
		if (A[bestx[j]].b >= laste) 
		{
			cout << "选取活动" << bestx[j] << " [" << A[bestx[j]].b << "," << A[bestx[j]].e << "]\n";
			laste = A[bestx[j]].e; // 更改为当前活动的结束时间
		}
	}
	cout << "兼容活动的个数=" << maxsum << endl;
}

int main() 
{
	for (int i = 1; i <= n; i++) 
	{
		x[i] = i;
	}
	
	dfs(1); // 从第1个活动开始搜索
	dispasolution(); // 输出结果
	
	return 0;
}

7.分支限界法求01背包问题

在这里插入图片描述

  • 采用队列式分枝限界法求解0/1背包问题的算法
//将物体按单位价值从高到低排序 
#include <stdio.h>
#include <queue>
using namespace std;
#define MAXN 20						//最多可能物品数
//问题表示
//int n=3,C=30;
//int w[]={0,16,15,15};				//重量,下标0不用
//int v[]={0,45,25,25};  			//价值,下标0不用

int n=5,C=37;
int w[]={0,8,16,21,17,12};			//重量,下标0不用
int v[]={0,48,14,16,11,7};  		//价值,下标0不用

//求解结果表示
int maxv=-9999;						//存放最大价值,初始为最小值
int bestx[MAXN];					//存放最优解,全局变量
int total=1;						//解空间中结点数累计,全局变量
struct NodeType						//队列中的结点类型
{	int no;							//结点编号
	int t;							//当前结点在搜索空间中的层次
	int w;							//当前结点的总重量
	int v;							//当前结点的总价值
	int x[MAXN];					//当前结点包含的解向量
	double leftV;			   	    //剩余物品价值上界
};

void EnQueue(NodeType e,queue<NodeType> &qu)	//结点e进队qu
{
	if (e.t==n+1)					//到达叶子结点
	{			
		if (e.v>maxv && e.w<=C)			//找到更大价值的解
		{
			maxv=e.v;
			for (int j=1;j<=n;j++)
				bestx[j]=e.x[j];
		}
	}
	else qu.push(e);			//非叶子结点进队
}
void bfs()							//求0/1背包的最优解
{
	int j;
	NodeType e,e1,e2;				//定义3个结点
	queue<NodeType> qu;				//定义一个队列
	e.no=total++; 
	e.t=1;							//根结点置初值,其层次计为1
	e.w=0; e.v=0;	
	e.leftV=0;
	for (j=1;j<=n;j++)
	{
		e.x[j]=0;    //根结点的解向量 
		e.leftV+=v[j];  //求根结点的上界
	}		
					
	qu.push(e);						//根结点进队
	while (!qu.empty())				//队不空循环
	{
		e=qu.front(); qu.pop();		//出队结点e,对第e.t物品进行决策 
		//if (e.w+w[e.t+1]<=C )		//装入e.t物品。剪枝:检查左孩子结点 
		if (e.w+w[e.t]<=C && e.v+e.leftV > maxv ) //剪枝:检查左孩子结点,
		{
			
			e1.no=total++; 
			e1.t=e.t+1;				//建立左孩子结点
			e1.w=e.w+w[e.t];
			e1.v=e.v+v[e.t];
			for (j=1;j<e.t;j++)		//复制解向量
				e1.x[j]=e.x[j];
		    e1.x[e.t]=1;
		    
			e1.leftV=e.leftV-v[e.t];			
			
			EnQueue(e1,qu);			//左孩子结点进队操作
			//qu.push(e1);	
		}
		if(e.v+e.leftV-v[e.t] > maxv)   //不装入e.t物品,右剪枝 
		{
			
			e2.no=total++;				//建立右孩子结点
			e2.t=e.t+1;
			e2.w=e.w; 
			e2.v=e.v;
			for (j=1;j<e.t;j++)			//复制解向量
				e2.x[j]=e.x[j];
			e2.x[e.t]=0;
			
			e2.leftV=e.leftV-v[e.t];
			EnQueue(e2,qu);
		}
	}
}
int main()
{
	bfs();					//调用队列式分枝限界法求0/1背包问题
	printf("分支限界法FIFO求解0/1背包问题:\n  X=[");	//输出最优解
	for(int i=1;i<=n;i++)
		printf("%2d",bestx[i]);		//输出所求X[n]数组
	printf("],装入总价值为%d\n",maxv);
	
	printf("生成的结点总个数:%d\n",total-1); 
	return 0;
}
  • 采用队列式分枝限界法求解0/1背包问题的算法
//将物体按单位价值从高到低排序 
#include <stdio.h>
#include <queue>
using namespace std;
#define MAXN 20						//最多可能物品数
//问题表示
//int n=3,C=30;
//int w[]={0,16,15,15};				//重量,下标0不用
//int v[]={0,45,25,25};  			//价值,下标0不用

int n=5,C=37;
int w[]={0,8,16,21,17,12};			//重量,下标0不用
int v[]={0,48,14,16,11,7};  		//价值,下标0不用

//求解结果表示
int maxv=-9999;						//存放最大价值,初始为最小值
int bestx[MAXN];					//存放最优解,全局变量
int total=1;						//解空间中结点数累计,全局变量
struct NodeType						//队列中的结点类型
{	int no;							//结点编号
	int t;						//当前结点在搜索空间中的层次
	int w;							//当前结点的总重量
	int v;							//当前结点的总价值
	int x[MAXN];					//当前结点包含的解向量
	double leftV;			   	    //剩余物品价值上界
	bool operator<(const NodeType &s) const	//重载<关系函数
	{
		//return leftV < s.leftV;		//剩余物品价值越大,优先级越高,优先出队
		//return v < s.v;		        //已选物品价值越大,优先级越高,优先出队
		return v+leftV < s.v+s.leftV;	//已选物品价值+剩余物品价值越大,优先级越高,优先出队
	}
};

void EnQueue(NodeType e,priority_queue<NodeType> &qu)	//结点e进队qu
{
	if (e.t==n+1)					//到达叶子结点
	{   		
		if (e.v>maxv && e.w<=C)			//找到更大价值的解
		{
			maxv=e.v;
			for (int j=1;j<=n;j++)
				bestx[j]=e.x[j];
		}
	}
	else qu.push(e);			//非叶子结点进队
}
void bfs()							//求0/1背包的最优解
{
	int j;
	NodeType e,e1,e2;				//定义3个结点
	priority_queue<NodeType> qu;	//定义一个优先级队列

	e.t=1;							//根结点置初值,其层次计为1
	e.w=0; e.v=0;
	e.no=total++; 
	e.leftV=0;
	for (j=1;j<=n;j++)
	{
		e.x[j]=0;    //根结点的解向量 
		e.leftV+=v[j];  //求根结点的上界
	}					
	qu.push(e);						//根结点进队
	
	while (!qu.empty())				//队不空循环
	{
		e=qu.top(); qu.pop();		//出队结点e
		
		if (e.w+w[e.t]<=C && e.v+e.leftV > maxv)		//剪枝:检查左孩子结点
		{
			e1.no=total++; 
			e1.t=e.t+1;				//建立左孩子结点
			e1.w=e.w+w[e.t];
			e1.v=e.v+v[e.t];
			for (j=1;j<e.t;j++)		//复制解向量
				e1.x[j]=e.x[j];
			e1.x[e.t]=1;			
			e1.leftV=e.leftV-v[e.t];
			
			EnQueue(e1,qu);			//左孩子结点进队操作
		}
		if(e.v+e.leftV-v[e.t] > maxv)   //右剪枝 
		{
			e2.no=total++;				//建立右孩子结点
			e2.t=e.t+1;
			e2.w=e.w; 
			e2.v=e.v;
			for (j=1;j<e.t;j++)			//复制解向量
				e2.x[j]=e.x[j];
			e2.x[e.t]=0;			
			e2.leftV=e.leftV-v[e.t];
			
			EnQueue(e2,qu);
		}
	}
}
int main()
{
	bfs();					//调用队列式分枝限界法求0/1背包问题
	printf("分支限界法优先队列求解0/1背包问题:\n  X=[");	//输出最优解
	for(int i=1;i<=n;i++)
		printf("%2d",bestx[i]);		//输出所求X[n]数组
	printf("],装入总价值为%d\n",maxv);
	
	printf("生成的结点总个数:%d\n",total-1); 
	
	return 0;
}

8.分支限界法求单源最短路径

在这里插入图片描述

  • 采用FIFO队列式分支限界法求解
    在这里插入图片描述
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f  // 表示∞
#define MAXN 51

// 问题表示
int n;                  // 图顶点个数
int a[MAXN][MAXN];      // 图的邻接矩阵
int v;                  // 源点

// 求解结果表示
int dist[MAXN];         // dist[i] 源点到顶点i的最短路径长度
int previous[MAXN];     // previous[i] 表示源点到i的最短路径中顶点i的前驱顶点

struct NodeType         // 队列结点类型
{
    int vno;            // 顶点编号
    int length;         // 路径长度
};

void bfs(int v)         // 求解算法
{
    NodeType e, e1;
    queue<NodeType> qu;
    e.vno = v;          // 建立源点结点e(根结点)
    e.length = 0;       // 源点结点e进队
    qu.push(e);
    dist[v] = 0;
    
    while(!qu.empty())  // 队列不空循环
    {
        e = qu.front(); qu.pop(); // 退出队列结点e
        for (int j = 0; j < n; j++)
        {
            if(a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j])
            {
                // 算法:e.vno到顶点j有边并且路径长度更短
                dist[j] = e.length + a[e.vno][j];
                previous[j] = e.vno;  // 建立相应顶点j的结点e1
                e1.vno = j;
                e1.length = dist[j];  // 结点e1进队
                qu.push(e1);
            }
        }
    }
}

int main()
{
    // 读入图的顶点个数
    scanf("%d", &n);
    
    // 读入图的邻接矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    
    // 读入源点
    scanf("%d", &v);
    
    // 初始化dist数组
    for (int i = 0; i < n; i++)
    {
        dist[i] = INF;
        previous[i] = -1;
    }
    
    // 调用bfs算法
    bfs(v);
    
    // 输出最短路径长度
    for (int i = 0; i < n; i++)
    {
        if (dist[i] == INF)
        {
            printf("INF ");
        }
        else
        {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
    
    // 输出最短路径的前驱节点
    for (int i = 0; i < n; i++)
    {
        printf("%d ", previous[i]);
    }
    printf("\n");
    
    return 0;
}
  • 采用优先队列式分枝限界法求解
    在这里插入图片描述
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f  // 表示∞
#define MAXN 51

// 问题表示
int n;                  // 图顶点个数
int a[MAXN][MAXN];      // 图的邻接矩阵
int v;                  // 源点

// 求解结果表示
int dist[MAXN];         // dist[i] 源点到顶点i的最短路径长度
int previous[MAXN];     // previous[i] 表示源点到i的最短路径中顶点i的前驱顶点

struct NodeType         // 队列结点类型
{
    int vno;            // 顶点编号
    int length;         // 路径长度
    
    bool operator<(const NodeType& node) const
    {
        return length > node.length; // length 越小越优先出队
    }
};

void bfs(int v)         // 求解算法
{
    NodeType e, e1;
    priority_queue<NodeType> pqu;    // 定义优先队列
    e.vno = v;                       // 建立源点结点e
    e.length = 0;                    // 源点结点e进队
    pqu.push(e);
    dist[v] = 0;
    
    while(!pqu.empty())              // 队列不空循环
    {
        e = pqu.top(); pqu.pop();    // 退出队列结点e
        for (int j = 0; j < n; j++)
        {
            if(a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j])
            {
                // 算法:e.vno到顶点j有边且路径长度更短
                dist[j] = e.length + a[e.vno][j];
                previous[j] = e.vno; // 建立相应顶点j的结点e1
                e1.vno = j;
                e1.length = dist[j]; // 结点e1进队
                pqu.push(e1);
            }
        }
    }
}

int main()
{
    // 读入图的顶点个数
    scanf("%d", &n);
    
    // 读入图的邻接矩阵
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    
    // 读入源点
    scanf("%d", &v);
    
    // 初始化dist数组
    for (int i = 0; i < n; i++)
    {
        dist[i] = INF;
        previous[i] = -1;
    }
    
    // 调用bfs算法
    bfs(v);
    
    // 输出最短路径长度
    for (int i = 0; i < n; i++)
    {
        if (dist[i] == INF)
        {
            printf("INF ");
        }
        else
        {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
    
    // 输出最短路径的前驱节点
    for (int i = 0; i < n; i++)
    {
        printf("%d ", previous[i]);
    }
    printf("\n");
    
    return 0;
}

9.分支限界法求解八数码问题

在这里插入图片描述

  • 剪枝:
    在这里插入图片描述
    在这里插入图片描述
#include<bits/stdc++.h>

using namespace std;

struct state
{
	int a[3][3];
	int zx,zy;
	int integer;//map->9位数
	int useful;//若0位置越界或节点重复,则为无效节点 
};

state start;
queue<state> q;
map<int,int> used;
map<int,int> step;

int walk[4][2]=
{
	0,-1,//left
	+1,0,//down
	0,+1,//right
	-1,0//up
};

int bfs();
int setinteger(state n);
state move(state now,int i);

void init()
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		{
			cin>>start.a[i][j];
			if(start.a[i][j]==0)
			{
				start.zx=i;
				start.zy=j;
			}
		}
	start.integer=setinteger(start);
	used[start.integer]=1;
	step[start.integer]=0;
	q.push(start);
}

int setinteger(state n)
{
	n.integer=0;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		{
			n.integer*=10;
			n.integer+=n.a[i][j];
		}
//	cout<<n.integer<<endl;
	return n.integer;
}

int bfs()
{
	state now,next;
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			next=move(now,i);
			if(next.useful)
			{
				if(next.integer==123456780)
					return step[next.integer];
				else
					q.push(next);
			}
		}
	}
	return -1;
}

state move(state now,int i)
{
	int newx,newy;
	state next;
	next.useful=0;
	for(int j=0;j<3;j++)
		for(int k=0;k<3;k++)
		{
			next.a[j][k]=now.a[j][k];
//			cout<<next.a[j][k]<<endl;
		}	
	newx=now.zx+walk[i][0];
	newy=now.zy+walk[i][1];
//	cout<<newx<<newy<<endl;
	if(newx>=0 && newx<3 && newy>=0 && newy<3)
	{
		swap(next.a[now.zx][now.zy],next.a[newx][newy]);
		next.zx=newx;
		next.zy=newy;
		next.integer=setinteger(next);
		if(!used.count(next.integer))
		{
			used[next.integer]=1;
			step[next.integer]=step[now.integer]+1;
			next.useful=1;
		}
	}
//	cout<<next.integer<<endl;
	return next;
}

int main()
{
	init();
	cout<<bfs()<<endl;
	return 0;
} 

10.流水作业调度

在这里插入图片描述

  • 回溯法:
#include <bits/stdc++.h>

using namespace std;

const int MAX = 5; // 假设最大作业数为5

int n = 4; // 作业数
int a[MAX] = {0, 5, 12, 4, 8}; // M1上的执行时间, 下标0不用
int b[MAX] = {0, 6, 2, 14, 7}; // M2上的执行时间, 下标0不用
int f1 = 0, f2[MAX + 1] = {0}; // 初始执行时间和f2数组初始化为0
int x[MAX] = {1, 2, 3, 4}; // 作业序列,假设初始顺序为1, 2, 3, 4
int bestf = INT_MAX; // 最优解的f2[n]值
int bestX[MAX] = {0}; // 最优解的作业序列
int leftT = 0; // 剩余作业在M2上的总时间

void dfs(int i) 
{
    if (i > n) 
    {
        if (f2[n] < bestf) 
        {
            bestf = f2[n]; // 找到更优解
            for (int j = 1; j <= n; j++) 
            {
                bestX[j] = x[j]; // 复制解向量
            }
        }
    } 
    else 
    {
        for (int j = i; j <= n; j++) 
        {
            swap(x[i], x[j]);
            f1 += a[x[i]]; // 选择作业x[i],在M1上执行完的时间
            f2[i] = max(f1, f2[i - 1]) + b[x[i]];
            leftT -= b[x[i]]; // 更新剩余作业时间
            if (f2[i] + leftT < bestf) // 剪枝
            {
                dfs(i + 1);
            }
            f1 -= a[x[i]]; // 回溯
            leftT += b[x[i]]; // 回溯更新剩余作业时间
            swap(x[i], x[j]);
        }
    }
}

int main() 
{
    for (int i = 1; i <= n; i++) 
    {
        leftT += b[i]; // 计算所有作业在M2上的总时间
    }
    dfs(1);
    cout << "最优解的M2完成时间为: " << bestf << endl;
    cout << "最优解的作业序列为: ";
    for (int i = 1; i <= n; i++) 
    {
        cout << bestX[i] << " ";
    }
    cout << endl;
    return 0;
}
  • 分支限界法:
#include <bits/stdc++.h>

using namespace std;

const int MAX = 5; // 假设最大作业数为5

struct NodeType 
{
    int no; // 结点编号
    int x[MAX + 1]; // x[i]表示第i步分配作业编号
    int y[MAX + 1]; // y[i]=1表示编号为i的作业已经分配
    int i; // 步骤编号
    int f1; // 已经分配作业在M1的执行时间
    int f2; // 已经分配作业在M2的执行时间
    int lb; // 下界
    bool operator<(const NodeType &s) const 
    {
        return lb > s.lb; // lb越小越优先出队
    }
};

int n = 4; // 作业数
int a[MAX] = {0, 5, 12, 4, 8}; // M1上的执行时间, 下标0不用
int b[MAX] = {0, 6, 2, 14, 7}; // M2上的执行时间, 下标0不用
int bestf = INT_MAX; // 最优解的f2[n]值
int bestX[MAX + 1] = {0}; // 最优解的作业序列

void bound(NodeType &e) // 求结点e的限界值
{
    int sum = 0;
    for (int i = 1; i <= n; i++) // 仅累计还没有分配的作业的b时间
        if (e.y[i] == 0) sum += b[i];
    e.lb = e.f2 + sum;
}

void dfs(int i)
{
    priority_queue<NodeType> pq;
    NodeType u, v;
    v.i = 0; v.f1 = v.f2 = 0;
    for (int j = 1; j <= n; j++) 
    {
        v.y[j] = 0;
    }
    bound(v);
    pq.push(v);
    while (!pq.empty()) 
    {
        v = pq.top(); pq.pop();
        if (v.i == n) 
        {
            if (v.f2 < bestf) 
            {
                bestf = v.f2;
                for (int j = 1; j <= n; j++) 
                {
                    bestX[j] = v.x[j];
                }
            }
        } 
        else 
        {
            v.i++;
            for (int j = 1; j <= n; j++) 
            {
                if (v.y[j] == 0) 
                {
                    u = v;
                    u.x[u.i] = j;
                    u.y[j] = 1;
                    u.f1 += a[j];
                    u.f2 = max(u.f1, u.f2) + b[j];
                    bound(u);
                    if (u.lb < bestf) 
                    {
                        pq.push(u);
                    }
                }
            }
        }
    }
}

int main() 
{
    dfs(1);
    cout << "最优解的M2完成时间为: " << bestf << endl;
    cout << "最优解的作业序列为: ";
    for (int i = 1; i <= n; i++) 
    {
        cout << bestX[i] << " ";
    }
    cout << endl;
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/724644.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

手写MyBatis 重要基本原理框架

1. 手写MyBatis 重要基本原理框架 文章目录 1. 手写MyBatis 重要基本原理框架1.1 第一步&#xff1a;IDEA中创建模块1.2 第二步&#xff1a;资源工具类&#xff0c;方便获取指向配置文件的输入流1.3 第三步&#xff1a;定义SqlSessionFactoryBuilder类1.4 第四步&#xff1a;分…

再进一步!deepin V23成功适配SpacemiT MUSE™ Box

内容来源&#xff1a;deepin&#xff08;深度&#xff09;社区 deepin作为国内领先的Linux操作系统发行版&#xff0c;一直致力于为用户提供更广泛的硬件支持&#xff0c;并积极投身于蓬勃发展的RISC-V生态建设。自deepin-ports SIG&#xff08;特别兴趣小组&#xff09;成立以…

WSL2 无法将磁盘”C:\Program Files\WSL\system.vhd“ 附加到WSL2 系统找不到指定的文件

WSL2 无法将磁盘”C:\Program Files\WSL\system.vhd“ 附加到WSL2 系统找不到指定的文件 开局就是雷蹦开局就是雷蹦 早上上班,一开机直接崩溃了,这啥问题,这个文件我哪里敢删除不是。肯定不是我的问题,我不看。心里默默告诉自己,一切都是状态机。确定了一下,首先确实存在…

类注释规范

类注释规范 1.1.1 模板配置 模板路径&#xff1a;File–>settings–>Editor–>File and Code Templates–>Includes–>File Header  N A M E &#xff1a;设置类名&#xff0c;与下面的 {NAME}&#xff1a;设置类名&#xff0c;与下面的 NAME&#xff1a;设…

gitee添加别人的仓库后,在该仓库里添加文件夹/文件

一、在指定分支里添加文件夹&#xff08;如果库主没有创建分支&#xff0c;自己还要先创建分支&#xff09; eg:以在一个项目里添加视图文件为例&#xff0c;用Echarts分支在usr/views目录下添加Echarts文件夹&#xff0c;usr/views/Echarts目录下添加index.vue 1.切换为本地仓…

C++之STL(二三)

1、vector源码刨析 1.1、数据结构以及动态扩充算法 其实vector内部有三个指针&#xff0c;分别是数据的第一个元素Myfirst、数据的最后一个元素的下一个位置Mylast&#xff0c;最后一个空间的下一个位置Myend&#xff1b;当你插入数据的时候&#xff0c;先判断当前容量够不够&…

浅谈RC4

一、什么叫RC4&#xff1f;优点和缺点 RC4是对称密码&#xff08;加密解密使用同一个密钥&#xff09;算法中的流密码&#xff08;一个字节一个字节的进行加密&#xff09;加密算法。 优点&#xff1a;简单、灵活、作用范围广&#xff0c;速度快 缺点&#xff1a;安全性能较差&…

昇思大模型学习·第一天

mindspore快速入门回顾 导入mindspore包 处理数据集 下载mnist数据集进行数据集预处理 MnistDataset()方法train_dataset.get_col_names() 打印列名信息使用create_tuple_iterator 或create_dict_iterator对数据集进行迭代访问 网络构建 mindspore.nn: 构建所有网络的基类用…

LoRA用于高效微调的基本原理

Using LoRA for efficient fine-tuning: Fundamental principles — ROCm Blogs (amd.com) 大型语言模型的低秩适配&#xff08;LoRA&#xff09;用于解决微调大型语言模型&#xff08;LLMs&#xff09;的挑战。GPT和Llama等拥有数十亿参数的模型&#xff0c;特定任务或领域的微…

chrome 录制器及性能分析工具的使用

需求背景&#xff1a; 对比不同VPN方案网络延迟的差异。 验证工具&#xff1a; chrome浏览器自带的录制器、性能插件可以完美的解决这个问题。 注意&#xff1a;录制的操作都在当前页面&#xff0c;不存在新开标签页的场景 解决方案&#xff1a; 使用chrome录制器&#xf…

day14-226.翻转二叉树+101. 对称二叉树+104.二叉树的最大深度

一、226.翻转二叉树 题目链接&#xff1a;https://leetcode.cn/problems/invert-binary-tree/ 文章讲解&#xff1a;https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE 视频讲解&#xff1…

李宏毅2023机器学习作业HW06解析和代码分享

ML2023Spring - HW6 相关信息&#xff1a; 课程主页 课程视频 Sample code HW06 视频 HW06 PDF 个人完整代码分享: GitHub | Gitee | GitCode P.S. HW06 是在 Judgeboi 上提交的&#xff0c;出于学习目的这里会自定义两个度量的函数&#xff0c;不用深究&#xff0c;遵循 Sugge…

四十八、openlayers地图调色总结——锐化、模糊、浮雕滤镜,调整地图色相、饱和度、亮度

这篇是对滤镜的总结&#xff0c;方便工作中直接使用。 想要调整图层的颜色&#xff0c;有两种方法。 方法一&#xff1a; 加载图层时使用tileLoadFunction函数拿到context添加canvas滤镜效果。 this.imagery new TileLayer({source: new XYZ({url: "https://server.arc…

渲染农场深度解析:原理理解、配置要点与高效使用策略

许多设计领域的新手可能对“渲染农场”这一概念感到陌生。渲染农场是一种强大的计算资源集合&#xff0c;它通过高性能的CPU和GPU以及专业的渲染引擎&#xff0c;为设计项目提供必要的渲染支持。这种平台由多台计算机或渲染节点组成&#xff0c;形成一个分布式网络&#xff0c;…

第四篇:精通Docker构建:Dockerfile的艺术与策略

精通Docker构建&#xff1a;Dockerfile的艺术与策略 1. 开篇&#xff1a;探索Docker的革命 在探讨我们的主题之前&#xff0c;让我们先回顾一下Docker的概念。Docker是一个开源平台&#xff0c;用于自动化应用程序的部署、扩展和管理&#xff0c;这一切都是在轻量级的容器中进…

6月17日(周一)美国股市行情总结:标普纳指齐新高,AI和芯片股尤为出色

标普500指数在六天里第五天上涨&#xff0c;纳指和纳指100均连续六日新高&#xff0c;道指止步四日连跌脱离近两周低位&#xff0c;罗素小盘股指止步两日连跌并脱离六周最低。微软收盘市值仍为美股第一、苹果为第二、英伟达第三&#xff0c;但早盘触及盘中新高的英伟达市值曾超…

Linux虚拟机安装nginx并进行浏览器访问 - 附带常见问题和常用指令(实施必备)

1、Linux安装Nginx 1.1、下载Nginx安装包 Linux Nginx-1.25.5 官方其他版本 1.2、解压安装包 tar -zxvf nginx-1.25.5.tar.gz 1.3、安装依赖包 由于我使用的是1.25.5版本&#xff0c;所以需要加入依赖包 # yum install pcre pcre-devel # yum install zlib-devel 1.4、配置…

数据集制作——语义分割前png、jpg格式标签图转yolo格式.txt文件(附代码)

&#x1f4aa; 专业从事且热爱图像处理&#xff0c;图像处理专栏更新如下&#x1f447;&#xff1a; &#x1f4dd;《图像去噪》 &#x1f4dd;《超分辨率重建》 &#x1f4dd;《语义分割》 &#x1f4dd;《风格迁移》 &#x1f4dd;《目标检测》 &#x1f4dd;《暗光增强》 &a…

【论文阅读】MOA,《Mixture-of-Agents Enhances Large Language Model Capabilities》

前面大概了解了Together AI的新研究MoA&#xff0c;比较好奇具体的实现方法&#xff0c;所以再来看一下对应的文章论文。 论文&#xff1a;《Mixture-of-Agents Enhances Large Language Model Capabilities》 论文链接&#xff1a;https://arxiv.org/html/2406.04692v1 这篇文…