买模板做的网站表单数据在哪里看,锦州市做网站,帝国cms做中英文网站,wordpress删除小工具第六次作业【分支限界法】 文章目录 第六次作业【分支限界法】1 算法实现题6-2 最小权顶点覆盖问题2 算法实现题6-6 n后问题3 算法实现题6-7 布线问题 1 算法实现题6-2 最小权顶点覆盖问题
▲问题重述
问题描述#xff1a; 给定一个赋权无向…第六次作业【分支限界法】 文章目录 第六次作业【分支限界法】1 算法实现题6-2 最小权顶点覆盖问题2 算法实现题6-6 n后问题3 算法实现题6-7 布线问题 1 算法实现题6-2 最小权顶点覆盖问题
▲问题重述
问题描述 给定一个赋权无向图 G(V,E)每个顶点 v∈V 都有一个权值 w(v)。如果 U⊆VU⊆V且对任意(u,v)∈E 有 u∈U 或 v∈U就称 U 为图 G 的一个顶点覆盖。G 的最小权顶点覆盖是指 G 中所含顶点权之和最小的顶点覆盖。
算法设计 对于给定的无向图 G设计一个优先队列式分支限界法计算 G 的最小权顶点覆盖。
数据输入 由文件input.txt给出输入数据。第 1 行有 2 个正整数 n 和 m表示给定的图 G 有 n 个顶点和 m 条边顶点编号为 12…n。第 2 行有 n 个正整数表示 n 个顶点的权。接下来 的 m 行中每行有 2 个正整数 u,v表示图 G 的一条边(u,v)。
结果输出 将计算的最小权顶点覆盖的顶点权之和以及最优解输出到文件output.txt。文件的第1行是最小权顶点覆盖顶点权之和第2行是最优解xi1in,xi0表示顶点i不在最小权顶点覆盖中xi1表示顶点i在最小权顶点覆盖中。
输入文件示例
input.txt
7 7
1 100 1 1 1 100 10
1 6
2 4
2 5
3 6
4 5
4 6
6 7输出文件示例
output.txt
13
1 0 1 0 1 0 1▲解题思路
定义一个最小堆 MinHeap 类用于实现堆操作。HeapNode 类表示图中的一个顶点。DealNode 类包含一些操作主要是用于处理堆中结点的操作。DealNode::BBVC() 方法是该算法的核心部分。通过不断地加入和不加入某个顶点并通过堆来遍历所有可能的情况找到图的最小顶点覆盖。MinCover 函数是对 DealNode::BBVC() 方法的封装用于获取最终的最小顶点覆盖权重。在 main 函数中用户输入了图的顶点数 vertexNum 和边数 edgeNum。然后输入每个顶点的权值并通过边的信息构建了图的邻接矩阵。调用 MinCover 函数得到最小顶点覆盖权重并输出结果。
▲代码
#include fstream
#include iostream
using namespace std;template class Type
class MinHeap // 最小堆类
{
public:MinHeap(Type a[], int n); // 带两参数的构造函数在此程序中没有应用MinHeap(int ms); // 构造函数重载只初始化堆的大小对堆中结点不初始化另外堆元素的存储是以数组~MinHeap(); // 形式且无父、子指针访问父亲结点利用数组标号进行bool Insert(const Type x); // 插入堆中一个元素bool RemoveMin(Type x); // 删除堆顶最小结点void MakeEmpty(); // 使堆为空bool IsEmpty();bool IsFull();int Size();protected:void FilterDown(const int start, const int endOfHeap); // 自顶向下构造堆void FilterUp(const int start); // 自底向上构造堆
private:Type *heap;int maxSize;const int defaultSize;int currentSize; // 堆当前结点个数大小
};template class Type
MinHeapType::MinHeap(int ms) : defaultSize(100)
{maxSize (ms defaultSize) ? ms : defaultSize;heap new Type[maxSize];currentSize 0;
}template class Type
MinHeapType::MinHeap(Type a[], int n) : defaultSize(100)
{maxSize (n defaultSize) ? n : defaultSize;heap new Type[maxSize];currentSize n;for (int i 0; i n; i)heap[i] a[i];int curPos (currentSize - 2) / 2;while (curPos 0){FilterDown(curPos, currentSize - 1);curPos--;}
}template class Type
MinHeapType::~MinHeap()
{delete[] heap;
}template class Type
void MinHeapType::FilterDown(const int start, const int endOfHeap)
{int i start, j i * 2 1;Type temp heap[i];while (j endOfHeap){if (j endOfHeap heap[j] heap[j 1])j;if (temp heap[j])break;else{heap[i] heap[j];i j;j 2 * i 1;}}heap[i] temp;
}template class Type
void MinHeapType::FilterUp(const int start)
{int i start, j (i - 1) / 2;Type temp heap[i];while (i 0){if (temp heap[j])break;else{heap[i] heap[j];i j;j (i - 1) / 2;}}heap[i] temp;
}template class Type
bool MinHeapType::RemoveMin(Type x)
{if (IsEmpty()){cerr Heap empty! endl;return false;}x heap[0];heap[0] heap[currentSize - 1];currentSize--;FilterDown(0, currentSize - 1);return true;
}template class Type
bool MinHeapType::Insert(const Type x)
{if (IsFull()){cerr Heap Full! endl;return false;}heap[currentSize] x;FilterUp(currentSize);currentSize;return true;
}template class Type
bool MinHeapType::IsEmpty()
{return currentSize 0;
}template class Type
bool MinHeapType::IsFull()
{return currentSize maxSize;
}template class Type
void MinHeapType::MakeEmpty()
{currentSize 0;
}template class Type
int MinHeapType::Size()
{return currentSize;
}// 最小堆结点
class HeapNode // 堆结点类
{friend class DealNode;public:operator int() const { return cn; }private:int i, // i标示堆中结点号cn, // cn标示当前加入的覆盖顶点中权重之和*x, // x数组标示那些顶点加入了覆盖顶点的行列*c; // c数组标示X中的覆盖顶点中所有的邻接顶点
};// VC类用来对堆中结点内部的的操作
class DealNode
{friend int MinCover(int **, int[], int);private:void BBVC();bool cover(HeapNode E);void AddLiveNode(MinHeapHeapNode H, HeapNode E, int cn, int i, bool ch);int **a, n, *w, *bestx, bestn;
};void DealNode::BBVC()
{// 建立初始空堆MinHeapHeapNode H(1000);HeapNode E;E.x new int[n 1];E.c new int[n 1];for (int j 1; j n; j){E.x[j] E.c[j] 0;}int i 1, cn 0;while (true){if (i n){if (cover(E)){for (int j 1; j n; j)bestx[j] E.x[j];bestn cn;break;}}else{if (!cover(E))AddLiveNode(H, E, cn, i, true); // 加入结点标号为i 的结点到顶点覆盖集中并把更新后的结点再插入堆中AddLiveNode(H, E, cn, i, false); // 不把结点标号为 i 的结点加入到顶点覆盖集中并把更新后的结点插入堆中}if (H.IsEmpty())break;H.RemoveMin(E); // 取堆顶点赋给Ecn E.cn;i E.i 1;}
}// 检测图是否被覆盖
bool DealNode::cover(HeapNode E)
{for (int j 1; j n; j){if (E.x[j] 0 E.c[j] 0) // 存在任意一条边的两个顶点都为0的情况下为未覆盖情况return false; // X[j]记录覆盖顶点c[j]记录与覆盖顶点相连的顶点 0表征未覆盖1表征已覆盖}return true;
}void DealNode::AddLiveNode(MinHeapHeapNode H, HeapNode E, int cn, int i, bool ch)
{HeapNode N;N.x new int[n 1];N.c new int[n 1];for (int j 1; j n; j){N.x[j] E.x[j];N.c[j] E.c[j];}N.x[i] ch ? 1 : 0;if (ch){N.cn cn w[i]; // 记录i顶点是否加入覆盖的行列中for (int j 1; j n; j)if (a[i][j] 0) // 如果i,j相邻刚把j顶点加入覆盖邻接顶点集中N.c[j];}else{N.cn cn;}N.i i;H.Insert(N); // 插入堆中
}int MinCover(int **a, int v[], int n)
{DealNode Y;Y.w new int[n 1];for (int j 1; j n; j){Y.w[j] v[j]; // 初始化DealNode类对象Y;}Y.a a;Y.n n;Y.bestx v; // 将地址赋予bestxY.BBVC();return Y.bestn; // bestn是最后的最小顶点覆盖集权重
}int main()
{int startV, endV; // 一条边的起始节点终止节点int vertexNum, edgeNum; // 顶点数边数int i;cin vertexNum edgeNum;int **a; // 图的邻接矩阵表示1表示有边a new int *[vertexNum 1];for (int k 0; k vertexNum; k)a[k] new int[vertexNum 1];for (int i 0; i vertexNum; i)for (int j 0; j vertexNum; j)a[i][i] 0;int *p; // 顶点的权值数组p new int[vertexNum 1];for (i 1; i vertexNum; i)cin p[i];for (i 1; i edgeNum; i){cin startV endV;a[startV][endV] 1;a[endV][startV] 1;}int minVertex MinCover(a, p, vertexNum);cout minVertex endl;for (i 1; i vertexNum; i){cout p[i] ;}cout endl;return 0;
}
▲验证 2 算法实现题6-6 n后问题
▲问题重述
设计一个解n后问题的队列式分支限界法计算在n × n n\times nn×n个方格上放置彼此不受攻击的n个皇后的一个放置方案。 案例
input
5
output
1 3 5 2 4▲解题思路
定义一个结构体node表示棋盘上的每一个可能的位置以及记录了当前状态的一些信息如列、左右对角线等的占用情况。使用优先队列priority_queue来存储搜索过程中的状态按照结构体中的x值进行排序。这里的x表示当前放置的皇后所在的行数。在主循环中初始化棋盘的初始状态将第一行的每一个位置作为起点生成相应的初始状态并加入优先队列中。进入主循环每次从优先队列中取出一个状态判断是否达到了目标状态即放置了所有皇后如果是则输出解并结束程序因为只需要找到一个可行解即可。如果当前状态不是目标状态继续在下一行尝试放置皇后。遍历每一列对于每一个可行的位置生成新的状态并加入优先队列中。在生成新状态时进行剪枝操作检查当前位置是否与之前的皇后冲突如果冲突则跳过该位置。重复以上步骤直到找到一个解或者队列为空。由于采用优先队列搜索时会先尝试最有希望的位置加速找到解的过程。
▲代码
#include bits/stdc.h
using namespace std;
#define N 100
int n;
struct node
{int vis[N] {0}, col[N] {0}, lr[N] {0}, rl[N] {0};int x, y;node(int a, int b) : x(a), y(b) {}bool operator(const node a) const{return x a.x;}
};
priority_queuenode q;
int main()
{cin n;for (int i 0; i n; i){node temp node(0, i);temp.vis[0] i 1;temp.col[i] 1;temp.rl[temp.x temp.y] 1;temp.lr[50 temp.x - temp.y] 1;q.push(temp);}while (!q.empty()){node temp q.top();q.pop();if (temp.x n - 1){for (int i 0; i n; i){cout temp.vis[i] ;}cout endl;break; // 只需要给出一个答案即可}if (temp.x n - 1){for (int i 0; i n; i){node next node(temp.x 1, i);if (temp.col[next.y] || temp.lr[50 next.x - next.y] || temp.rl[next.x next.y]){ // 剪枝continue;}for (int i 0; i N; i){next.lr[i] temp.lr[i];next.rl[i] temp.rl[i];next.col[i] temp.col[i];}next.col[next.y] 1;next.lr[50 next.x - next.y] 1;next.rl[next.x next.y] 1;for (int i 0; i next.x; i){next.vis[i] temp.vis[i];}next.vis[next.x] i 1;q.push(next);}}}return 0;
}
▲验证
验证了n5,10,15三种情况。 3 算法实现题6-7 布线问题
▲问题重述 ▲解题思路
MinHeap 类定义了最小堆用于存储待处理的状态。该堆的元素是 BoardNode 类型的对象。BoardNode 类表示电路板的一种摆放方式包含了一些必要的信息。len 方法用于计算电路板摆放的长度。BBArrangeBoards 函数是基于分支限界法的核心算法。它通过不断生成摆放状态使用最小堆来搜索可能的最优解。HeapSize 为堆的大小。Make2DArray 函数用于动态创建二维数组。在 main 函数中用户输入了电路板数量 n。通过 Make2DArray 创建了二维数组 B表示电路板之间的连接关系。然后调用 BBArrangeBoards 函数求解问题并输出最小长度和对应的摆放方式。
▲代码
#include array
#include bits/stdc.h
#include queue
using namespace std;
int n, *p;
template class Type
class MinHeap // 最小堆类
{
public:MinHeap(Type a[], int n); // 带两参数的构造函数在此程序中没有应用MinHeap(int ms); // 构造函数重载只初始化堆的大小对堆中结点不初始化另外堆元素的存储是以数组~MinHeap(); // 形式且无父、子指针访问父亲结点利用数组标号进行bool Insert(const Type x); // 插入堆中一个元素bool RemoveMin(Type x); // 删除堆顶最小结点void MakeEmpty(); // 使堆为空bool IsEmpty();bool IsFull();int Size();protected:void FilterDown(const int start, const int endOfHeap); // 自顶向下构造堆void FilterUp(const int start); // 自底向上构造堆
private:Type *heap;int maxSize;const int defaultSize;int currentSize; // 堆当前结点个数大小
};template class Type
MinHeapType::MinHeap(int ms) : defaultSize(100)
{maxSize (ms defaultSize) ? ms : defaultSize;heap new Type[maxSize];currentSize 0;
}template class Type
MinHeapType::MinHeap(Type a[], int n) : defaultSize(100)
{maxSize (n defaultSize) ? n : defaultSize;heap new Type[maxSize];currentSize n;for (int i 0; i n; i)heap[i] a[i];int curPos (currentSize - 2) / 2;while (curPos 0){FilterDown(curPos, currentSize - 1);curPos--;}
}template class Type
MinHeapType::~MinHeap()
{delete[] heap;
}template class Type
void MinHeapType::FilterDown(const int start, const int endOfHeap)
{int i start, j i * 2 1;Type temp heap[i];while (j endOfHeap){if (j endOfHeap heap[j] heap[j 1])j;if (temp heap[j])break;else{heap[i] heap[j];i j;j 2 * i 1;}}heap[i] temp;
}template class Type
void MinHeapType::FilterUp(const int start)
{int i start, j (i - 1) / 2;Type temp heap[i];while (i 0){if (temp heap[j])break;else{heap[i] heap[j];i j;j (i - 1) / 2;}}heap[i] temp;
}template class Type
bool MinHeapType::RemoveMin(Type x)
{if (IsEmpty()){cerr Heap empty! endl;return false;}x heap[0];heap[0] heap[currentSize - 1];currentSize--;FilterDown(0, currentSize - 1);return true;
}template class Type
bool MinHeapType::Insert(const Type x)
{if (IsFull()){cerr Heap Full! endl;return false;}heap[currentSize] x;FilterUp(currentSize);currentSize;return true;
}template class Type
bool MinHeapType::IsEmpty()
{return currentSize 0;
}template class Type
bool MinHeapType::IsFull()
{return currentSize maxSize;
}template class Type
void MinHeapType::MakeEmpty()
{currentSize 0;
}template class Type
int MinHeapType::Size()
{return currentSize;
}class BoardNode
{friend int BBArrangeBoards(int **, int, int *);public:operator int() const { return cd; }int len(int **, int ii);private:int *x, s, cd;
};int BoardNode::len(int **conn, int ii)
{int sum 0;for (int i 1, sum 0; i ii; i){for (int j i 1; j ii; j){int dist x[i] x[j] ? x[i] - x[j] : x[j] - x[i];sum conn[i][j] * dist;}}return sum;
}int BBArrangeBoards(int **conn, int n, int *bestx)
{int HeapSize 10;MinHeapBoardNodeH(HeapSize);BoardNode E;E.x new int[n 1];E.s 0;E.cd 0;for (int i 1; i n; i)E.x[i] i;int bestd INT_MAX;bestx 0;while (E.cd bestd){if (E.s n - 1){int ld E.len(conn, n);if (ld bestd){delete[] bestx;bestx E.x;bestd ld;}elsedelete[] E.x;}else{for (int i E.s 1; i n; i){BoardNode N;N.x new int[n 1];N.s E.s 1;for (int j 1; j n; j)N.x[j] E.x[j];N.x[N.s] E.x[i];N.x[i] E.x[N.s];N.cd N.len(conn, N.s);if (N.cd bestd)H.Insert(N);elsedelete[] N.x;}}delete[] E.x;}try{H.RemoveMin(E);}catch (...){return bestd;}while (true){delete[] E.x;try{H.RemoveMin(E);}catch (...){break;}}return bestd;
}template class T
void Make2DArray(T **x, int rows, int cols)
{x new T *[rows];for (int i 0; i rows; i){x[i] new T[cols];}
}int main()
{cin n;p new int[n 1];int **B;Make2DArray(B, n 1, n 1);for (int i 1; i n - 1; i)for (int j i 1; j n; j)cin B[i][j];cout BBArrangeBoards(B, n, p) endl;for (int i 1; i n; i)cout p[i] ;cout endl;return 0;
}
▲验证
书上案例验证通过。
