实验六分支限界法//6-1、6-6 项目VC++6.0 测试通过//6-15 项目VC2005 测试通过//6-1 最小长度电路板排列问题//头文件stdafx.h// stdafx.h : include file for standard system include files,// or project specific include files that are used frequently, but// are changed infrequently// #pragma once// Exclude rarely-used stuff from Windows headers#define WIN32_LEAN_AND_MEAN#include <stdio.h>#include <tchar.h>// TODO: reference additional headers your program requires here// sy61.cpp : Defines the entry point for the console application. ////Description://分支限界法6_1 最小长度电路板排列问题//#include "my.h"#include "stdafx.h"#include <iostream>#include <queue> using namespace std;int n,m;//#include "OutOfBounds.h" //定义节点类class BoardNode{friend int FIFOBoards(int **,int ,int,int *&);// 非类成员，可以访问私有成员的函数，最优序列查找public:operator int() const{return cd;}// 返回常数cdint len();public:int *x,s,cd,*low,*high;//x 表示当前节点的电路板排列，s 表示当前节点排列好的电路板的数//表示当前节点的最大长度，low ，high 分别表当前节点表示每一个连接块的第一个，和最后一个电路板//的位置};〃编写类的len()函数，求出当前节点的连接块长度的最大值int BoardNode::len(){int tmp=0;for(int k=1;k<=m;k++)if(low[k]<=n && high[k]>0 && tmp<high[k]-low[k]) tmp=high[k]-low[k];return tmp;}int FIFIOBoards(int **B ，int n ，int m ，int *&bestx)//n 为电路板的数量， m 为连接块的数量 {// int bestd;queue<BoardNode> q;//声明 BoardNode 类的节点队列 q BoardNode E;E.x=new int[n+1];// 为数组指针 x 分配 n+1 个动态空间，存储当前的排列E.s=0;//最初时，排列好的电路板的数目为0 E.cd=0;E.low=new int[m+1];// 存储每个连接块的第一个电路板的位置 E.high=new int[m+1];// 存储每个连接块的最后一个电路板的位置 for(int i=1;i<=m;i++){E.high[i]=0;// 初始化开始时的每个连接块的最后一个电路板的位置为 块 i 还没有电路板放入 E.x 的排列中E.low[i]=n+1;// 初始化开始时的每个连接块的第一个电路板的位置为 接块 i 还没有电路板放入 E.x 的排列中}for(i=1;i<=n;i++)E.x[i]=i;// 初始化 E.x 的排列为 1， 2，3 nint bestd=n+1;// 最优距离 bestx=O;//记录当前最优排列do{if(E.s==n-1)// 当已排列了 n-1 个时{ //判断是否改变每个连接块的最后一个电路板的位置 for(int j=1;j<=m;j++)if(B[E.x[n]][j] && n>E.high[j]) E.high[j]=n;int ld=E.len();// 存储当前节点的各连接块长度中的最大长度 //如果当前的最大长度小于了 n+1if(ld<bestd){delete[] bestx; bestx=E.x;bestd=ld;//最优距离}else delete[] E.x;//删除分配给 E.x 的数组空间 delete[] E.low;// 删除分配给E.low 的数组空间 delete[] E.high;// 删除分配给 E.high 的数组空间}else{int curr=E.s+1;//rr 记录现在应该排列第几个电路板 for(int i=E.s+1;i<=n;i++)//处理扩展节点下一层所有子节点 {0，表示连接n+1，表示连BoardNode N;N.low=new int[m+1];// 与if 中的意思相同N.high=new int[m+1];for(int j=1;j<=m;j++){N.low[j]=E.low[j];// 将 E.low[] 中的值赋给N.low[]N.high[j]=E.high[j];if(B[E.x[i]][j]){if(curr<N.low[j])N.low[j]=curr;// 若当前节点连接块j 的第一个电路板的位置比现在正在排列的电路板的位置还小if(curr>N.high[j])N.high[j]=curr;}}N.cd=N.len();//如果，当前节点的最大长度小于了最优长度则：if(N.cd<bestd){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];// 交换位置q.push(N);// 将节点N 加入队列中}else{delete[] N.low;delete[] N.high;}//printf("%d",bestd);}delete[] E.x;// 当前扩展节点所有子节点均考虑，变成死结点}//try{ if(!q.empty()){E=q.front(); //取队列首节点作为扩展节点q.pop();}else return bestd;//}//catch(OutOfBounds)//{//return bestd;//}//printf("finish");}while(!q.empty()); return bestd;return 1;}//测试void main() {//scanf("%d%d",&n,&m); cin>>n>>m;int **B=new int*[n+1];for (int t=0; t<=n; t++)B[t] = new int[m+1]; for(inti=1;i<=n;i++) for(intj=1;j<=m;j++) cin>>B[i][j];//scanf("%d",&B[i][j]);int *bestx=new int[n+1]; int bestd=0; bestd=FIFIOBoards(B,n,m,bestx);printf("%d\n",bestd); for(i=1;i<=n;i++){ cout<<bestx[i]<<"} cout<<endl;}//6-6 经典n 皇后问题H.//Description: 经典n 皇后问题广度优先建议n<=14 解空间为子集树//参考答案说排列树是不正确的，本例打印n*n 棋盘的所有解，即放置方法#include <iostream>#include <fstream> #include <algorithm>#include <functional>#include <queue> using namespace std;//本例子直接输入棋盘大小，不用文件//ifstream in("input.txt"); // 请在项目文件夹下新建一个input.txt //ofstreamout("output.txt");class Node{public:Node(int n){t = 0; this->n = n;loc = new int[n + 1];for (int i = 0; i<= n; ++i){loc[i] = 0;}}Node(const Node &other){ this->t = other.t;this->n = other.n; this->loc = new int [n + 1]; for (int i = 0; i <= n;++i){ this->loc[i] = other.loc[i];}}int t;// 已放置t 个皇后int *loc;//loc[1:t] int n;// 共放置n 个皇后bool checkNext(int next); void printQ();};bool Node::checkNext(int next){int i;for (i = 1; i <= t; ++i){if (loc[i] == next)// 检测同列{ return false;}if (loc[i] - next == t + 1 - i)// 检测反斜线行差== 列差{return false;}if (loc[i] - next == i - t - 1)// 检测正斜线{ return false;}} return true;}void Node::printQ(){for (int i = 1; i <= n; ++i){ cout<<loc[i]<<" ";} cout<<endl;}class Queen{ public:int n;//n 皇后int ansNum;// 对于n 皇后解的个数Queen(int n){ this->n = n; ansNum = 0;}void ArrangQueen();};void Queen::ArrangQueen(){ queue<Node> Q; Node ini(n); // 初始化Q.push(ini); while(!Q.empty()){Node father = Q.front(); //取队列下一个节点Q.pop();if (father.t == n){father.printQ();++ansNum;}for (int i = 1; i <= n; ++i) //一次性将当前扩展节点所有子节点考虑完，符合条件的插入队列if (father.checkNext(i)){Node Child(father); ++Child.t;Child.loc[Child.t] = i; Q.push(Child);}}}}int main(){//#define in cin//#define out cout cout<<" 请输入棋盘大小n:"; int n; cin>>n; // 从文件中读入一个整数//for(int Case = 1; Case <= cases; ++Case){ //int n; //in>>n; Queen Q(n); Q.ArrangQueen();//out<<"Case #"<<Case<<": "<<Q.ansNum<<endl;cout<<" 共"<<Q.ansNum<<" 种放置皇后方法，如上所示。