算法设计与分析实验报告c++实现(N皇后问题、卫兵布置问题、求解填字游戏问题、图的m着色问题)

2024-04-11 11:52:06
开发
35

一．N皇后问题

基本原理和思路：
从一条路往前走，能进则进，不能进则退回来，换一条路再试。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

代码实现如下：

#include <iostream>
#include <cmath>
using namespace std;
//皇后的个数,方案数目
int n,sum=0;
//记录放置方案
int x[100];//不能这样定义int *x;
//用户递归求取方案
void Queen1(void);
void TraceBack(int);
void PrintMethod(void);
//检查这一皇后放置方案是否满足要求
int Place(int);

int main()
{


    cout << "输入皇后个数：" << endl;
    cin>>n;
    Queen1();
    return 0;
}

void Queen1(void)
{
    TraceBack(0);
}
void TraceBack(int r)
{
    int i;
    if(r>=n){
        PrintMethod();//这个函数的正确性还没有得到验证
        sum++;
    }
    else{
        for(i=0;i<n;i++){
            x[r]=i;//在下一行判断当前路是不可行的之后，进入同级的另外的路径
            if(Place(r))//先试探当前这条路是可行的，则进入下一步循环
               TraceBack(r+1);
        }
    }
}
void PrintMethod(void)
{
    int i,j;
    cout<<"第"<<sum<<"个方案\n";
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(j==x[i])
                cout<<"1";
            else
               cout<<"0";
        }
        cout<<endl;
    }
}
int Place(int r)
{
    int i;
    for(i=0;i<r;i++)
    {
        if(x[r]==x[i] || abs(r-i)==abs(x[r]-x[i]))//在此处判断皇后走的下一步路是否可行，如果不可行性，return 0；
            return 0;
    }
    return 1;
}

分析：时间复杂度为O(n^n)

二．卫兵步列问题

基本原理和思路：初始令所有的 X [i, j]= 1， i =1,2, …… m ， j =1,2, ……n . 算法从（1,1 ）开始直到（m,n）为止，搜索树是二叉树，有 m x n 层 . 每个结点对应一个陈列室位置，如果令 X [i, j]= 0 ，取消（i,j ）位置的哨兵，进入左子树；否则进入右子树。在进入左子树时需要检查房间被监视的情况。即当取消（ i,j ）位置的哨兵时，此位置及其上、下、左、右位置是否被监视。

代码实现如下：

#include<iostream>
#include<fstream>
#include<queue>

using namespace std;
class Solve;

class Node   //Node节点，用来存放搜索树的节点
{
    friend class Solve;
private:
    int i;    //当前要放置的新位置 横坐标：i 纵坐标：j
    int j;
    int robotNums;    //当前节点已经放置的哨兵数目
    int beenMonitored;   //当前已经被监视的房间数
    int** x;    //当前放置哨兵的地方   0表示没有，1表示放置了
    int** y;    //当前已经被监视的地方   0表示没有，1表示已经监视了
    int m;      //行
    int n;      //列

public:
    Node();   //构造函数
    Node(int m, int n);   //构造函数,m、n是行列数
    Node(const Node& a);  //这个函数是用于heap的push，push会调用复制构造函数，因此必须自定义一个
    friend bool operator<(const Node& a, const Node& b);   //重载<，用于优先队列的使用
    Node& operator=(const Node& a)   //赋值运算符，懒得换位置了
    {
        if (x || y)
        {
            for (int i = 0; i < m + 2; ++i)
            {
                if (x)
                {
                    delete[] x[i];
                }
                if (y)
                {
                    delete[] y[i];
                }
            }
            delete[] x;
            delete[] y;
            x = NULL;
            y = NULL;
        }

        i = a.i;
        j = a.j;
        robotNums = a.robotNums;
        beenMonitored = a.beenMonitored;
        m = a.m;
        n = a.n;
        x = new int* [m + 2];
        y = new int* [m + 2];
        for (int i = 0; i < m + 2; ++i)
        {
            x[i] = new int[n + 2];
            y[i] = new int[n + 2];
            for (int j = 0; j < n + 2; ++j)
            {
                x[i][j] = a.x[i][j];
                y[i][j] = a.y[i][j];
            }
        }
        return *this;
    }
    ~Node();   //用到了new，因此析构函数要重载，避免内存泄露

};

class Solve     //解决问题的类
{
private:
    priority_queue<Node> heap;    //优先队列heap
    int ans;     //答案所需要的哨兵数目
    int m;       //行列数
    int n;
    int** result;  //答案哨兵的排列顺序

public:
    Solve();
    Solve(int m, int n);
    void run(ofstream& fcout);    //进行整个计算+输出
    void get_min();               //运用分支限界法，寻找最小值
    void print(ofstream& fcout);  //打印哨兵位置和数目
    void copy(int** x, int** y);  //将一个二维数组赋值给另一个
    void change(Node& tmp, int i, int j);   //生成子节点，同时将其添加到heap中
};




int main()
{
    ifstream fcin;
    fcin.open("input.txt");
    if (!fcin.is_open())
    {
        cout << "文件 input.txt 未能打开" << endl;
        return -1;
    }

    int m, n;
    fcin >> m >> n;
    fcin.close();
    Solve solve(m, n);

    ofstream fcout;
    fcout.open("output.txt");
    if (!fcout.is_open())
    {
        cout << "文件 output.txt 未能打开" << endl;
        return -1;
    }
    solve.run(fcout);
    fcout.close();

    return 0;
}

分析：复杂度 W(n,m)=O(nm2)。

三．求解填字游戏问题

基本原理和思路：从（0，0）开始向右搜索，搜到（3，0）结束
搜索时记录那些点被用过，下一个点一定是没有被用过的点，使用vis数组标记
退出条件：搜索到 x == 3时，即此时九个点都已经填了一遍值，输出填入的九个值
改点是否可以填入，是否合法：使用check函数来检查一下，由于是从左向右开始填起，所以相邻元素只需要考虑上和下两个方向，check函数加上判断边界的条件即可。
若该点合法，则填入该点，否则继续循环找一个可选点。
判断边界：即不能超出 3 * 3 的范围，到了最右边要进行换行，否则横坐标直接++即可！具体实现：if(y == 2) dfs(x + 1, 0); else dfs(x, y + 1);
最后取消标记，回溯上一个点，找下一种选择情况。

代码实现如下：

#include <iostream>

using namespace std;

int a[3][3], count;
bool vis[10];

bool isprime(int n)
{
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0) return false;
	}
	return true;
}

bool check(int x, int y, int k)
{
	// 上 
	if(x - 1 >= 0 && !isprime(a[x - 1][y] + k)) return false;
	// 左 
	if(y - 1 >= 0 && !isprime(a[x][y - 1] + k)) return false;
	return true;
}

void dfs(int x, int y)
{
	if(x == 3){
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 3; j++){
				cout << a[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
		count ++;
		return;
	}
	for(int i = 1; i <= 10; i++){
		if(!vis[i] && check(x, y, i)){
			a[x][y] = i; vis[i] = true;
			if(y == 2) dfs(x + 1, 0);
			else dfs(x, y + 1);
			a[x][y] = 0; vis[i] = false;
		}
	}
}

int main()
{
	dfs(0, 0);
	cout << "Total: " << count << endl;
	return 0;
}

分析：采用回溯法，即求全排列，时间复杂度O(n!)

四．求解图的m着色问题

基本原理和思路：MaxSum(i,j)：从第i行j列到底边的最大数字之和
从最后一行开始递推，MaxSum(n,j)=D(n,j)//n行j列，MaxSum(n-1,j) = D(n-1,j) + max( MaxSum(n,j) , MaxSum(n,j+1) )
然后为了减少空间，不需要用二维数组来存储MaxSum(n,j)的值，只需要求MaxSum(n,j)的时候存储下一行MaxSum(n+1,j)的值就可以，然后计算完第n行的MaxSum之后再覆盖原来的第n+1行的MaxSum的值。

代码实现如下：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>


using namespace std;


const int N = 5;//图的顶点数
const int M = 3;//色彩数
class Color
{
    friend int mColoring(int, int, int **);
private:
    bool Ok(int k);
    void Backtrack(int t);
    int n,      //图的顶点数
        m,      //可用的颜色数
        **a,    //图的邻接矩阵
        *x;     //当前解
    long sum;   //当前已找到的可m着色方案数
};
int mColoring(int n,int m,int **a);
int main()
{
    int **a = new int *[N+1];
    for(int i=1; i<=N; i++)
    {
        a[i] = new int[N+1];
    }


    cout<<"请输入图G的邻接矩阵:"<<endl;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cin>>a[i][j];


        }
        cout<<endl;
    }
    cout<<"图G的着色方案如下："<<endl;
    cout<<"当m="<<M<<"时，图G的可行着色方案数目为："<<mColoring(N,M,a)<<endl;
    for(int i=1; i<=N; i++)
    {
        delete[] a[i];
    }
    delete []a;
}


void Color::Backtrack(int t)
{
    if (t>n)
    {
        sum++;
        for (int i=1; i<=n; i++)
            cout << x[i] << " ";
        cout << endl;
    }
    else
    {
        for (int i=1; i<=m; i++)
        {
            x[t]=i;
            if (Ok(t)) Backtrack(t+1);
            x[t]=0;
        }
    }
}


bool Color::Ok(int k)// 检查颜色可用性
{
    for (int j=1; j<=n; j++)
    {
        if ((a[k][j]==1)&&(x[j]==x[k])) //相邻且颜色相同
        {
            return false;
        }
    }
    return true;
}


int mColoring(int n,int m,int **a)
{
    Color X;


    //初始化X
    X.n = n;
    X.m = m;
    X.a = a;
    X.sum = 0;
    int *p = new int[n+1];
    for(int i=0; i<=n; i++)
    {
        p[i] = 0;
    }
    X.x = p;
    X.Backtrack(1);
    delete []p;
    return X.sum;
}

分析：时间复杂度是 $O(m*n^2)$ 。

原文地址:https://blog.csdn.net/weixin_45741872/article/details/137586926 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1778269766524473344.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部