世界名画陈列馆问题

朱雀 2023-01-10 09:58 122阅读 0赞

世界名画陈列馆问题（回溯法）

# 问题描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbGxlcl82_size_16_color_FFFFFF_t_70_pic_center]  
此为《计算机算法设计与分析 第5版》王晓东 中习题作业

# 遇到问题 #

1.数组界线没有考虑清楚，出现越界；在change和restore只考虑i-1和j-1有没有出界，忘了考虑i+1和j+1有没有出界  
2.找到未被监视的陈列馆循环中，对最后一个房间（m-1，n-1）考虑不足，最终改为break出  
3.找到一组解的判断条件错误，最初判断是i和j都到边界m-1、n-1，没有结合循环考虑  
4.change和restore应该保持一致  
5.没有存储当前警卫布置  
6.对remainingRoom信息的更改没考虑到  
7.对三个if的处理仍有问题，如何解决数组过界问题，如果不进行边界判断，就没办法进行剪枝判断，考虑重新写个函数判断

# 代码 #

/* *代码题目：算法设计与分析世界名画陈列馆问题 *输入要求：input.txt m(矩阵行数) n(矩阵列数) *输出要求：ouput.txt bestGurad(最佳警卫数) guardPlace(警卫位置矩阵) *求解算法：回溯法 *作者：gsgysm@qq.com *编写时间：2020年12月12日 */
    #include<iostream>
    #include<fstream>
    using namespace std;
    
    class Solution
    { 
        int m,n;//矩阵行数、列数
        int bestGuard,currentGuard,remainingRoom;//最佳警卫数，当前警卫数，余下房间数
        int **guardPlace,**displayRoom,**currentGuardPlace;//最佳警卫布置，受监视展览室情况，当前警卫布置
    
    public:
        void Backtrack(int i,int j,int** displayRoom)
        { 
            //继续向下检索，直到找到没有被监视的陈列室
            while(displayRoom[i][j] >= 1){ 
                j++;
                if(j>=n){ 
                    i++;
                    j=0;
                }
                if(i==m)
                    break;
            }
    
            //查找到一组解，判断是否为最优，是则保留替换
            if(i>=m){ 
                if(currentGuard<bestGuard){ 
                    bestGuard=currentGuard;
                    for(int k=0;k<m;k++){ 
                        for(int l=0;l<n;l++){ 
                            guardPlace[k][l]=currentGuardPlace[k][l];
                        }
                    }
                }
                return ;
            }
    
            //当前警卫数+(还剩房间数+4)/5 >= bestGuard，则认为不会更佳，剪枝
            if(currentGuard+(remainingRoom+4)/5 >= bestGuard){ 
                return ;
            }
    
            if(i<m-1){ //放置在(i+1,j)，保证i不是最后一行，此种布置法为最佳情况，无需限制
                change(i+1,j);
                Backtrack(i,j,displayRoom);
                restore(i+1,j);   
            }
            if(j<n-1){ //放置在(i,j+1),保证j不是最后一行
                if(i+1<=m-1){ 
                    if(displayRoom[i+1][j]>0){ //(i,j+1)位置已经有了
                        change(i,j+1);
                        Backtrack(i,j,displayRoom);
                        restore(i,j+1);
                    }    
                }
                else{ 
                    change(i,j+1);
                    Backtrack(i,j,displayRoom);
                    restore(i,j+1);
                }
            }
            if(1){ //此种布置法一定不会比放置在(i+1,j)(i,j+1)更好，共计四种情况要考虑
                if(i+1<=m-1){ //i+1未越界
                    if(displayRoom[i+1][j]>0){ //判断(i+1,j)位置已经有了
                        if(j+1<=n-1){ //j+1未越界
                            if(displayRoom[i][j+1]>0){ //判断(i,j+1)位置已经有了
                                change(i,j);//(i+1,j)和(i,j+1)已经有了
                                Backtrack(i,j,displayRoom);
                                restore(i,j);
                            }
                        }
                    }
                    else{ 
                        change(i,j);//(i+1,j)位置已经有了，(i,j+1)位置不存在
                        Backtrack(i,j,displayRoom);
                        restore(i,j);
                    }
                }
                else{ //i+1越界
                    if(j+1<=n-1){ //判断j+1未越界
                        if(displayRoom[i][j+1]>0){ //判断(i,j+1)位置已经有了
                            change(i,j);//(i+1,j)位置不存在，(i,j+1)位置已经有了
                            Backtrack(i,j,displayRoom);
                            restore(i,j);
                        }
                    }
                    else{ //j+1越界
                        change(i,j);//(i+1,j)和(i,j+1)都不存在
                        Backtrack(i,j,displayRoom);
                        restore(i,j);
                    }
                    
                }
            }
        }
    
        //初始化各变量
        void init(void)
        { 
            currentGuard=0;//当前警卫数
            bestGuard=((m+2)/3)*n;//初始设定的警卫数 假定每个警卫只覆盖三个
            remainingRoom=m*n;//剩余未监视房间数
    
            //创建警卫位置二维数组并初始设定警卫位置
            guardPlace = new int*[m];
            for(int i=0;i<m;i++){ 
                guardPlace[i]=new int[n];
            }
            for(int i=0;i<m;i++){ 
                for(int j=0;j<n;j++){ 
                    if( (i%3==1) || (i==m-1 && m%3==1)){ //在第1、4、7、10……行全设为1 (从0开始),并考虑余下的行
                        guardPlace[i][j]=1;
                    }
                    else{ 
                        guardPlace[i][j]=0;
                    }
                }
            }
            //创建展览室位置二维数组并将元素均初始化为0
            displayRoom = new int*[m];
            for(int i=0;i<m;i++){ 
                displayRoom[i]=new int[n];
            }
            for(int i=0;i<m;i++){ 
                for(int j=0;j<n;j++){ 
                    displayRoom[i][j]=0;
                }
            }
            //创建存放当前警卫布置情况的数组
            currentGuardPlace = new int*[m];
            for(int i=0;i<m;i++){ 
                currentGuardPlace[i]=new int[n];
            }
            for(int i=0;i<m;i++){ 
                for(int j=0;j<n;j++){ 
                    currentGuardPlace[i][j]=0;
                }
            }
            
    
        }
    
        //输入函数，读入文件变量
        void input(void)
        { 
            freopen("input.txt","r",stdin);
        	scanf("%d %d",&m,&n);
            fclose(stdin);
        }
    
        //输出函数，输出最佳结果并释放数组空间
        void output(void)
        { 
            FILE *fp;
    		fp=fopen("output.txt","w");
    		fprintf(fp,"%d\n",bestGuard);
    
            for(int i=0;i<m;i++){ 
                for(int j=0;j<n;j++){ 
                	fprintf(fp,"%d ",guardPlace[i][j]);
                }
                fprintf(fp,"\n");
            }
            
            for(int i=0;i<m;i++){ 
                delete [] guardPlace[i];
                delete [] displayRoom[i];
                delete [] currentGuardPlace[i];
            }
        }
    
        int **returnPointer(void)
        { 
            return displayRoom;
        }
    
    private:
        //撤销(i,j)处的机器人，并改变周围展览室状态及剩余未监视房间数
        void restore(int i,int j)
        { 
            currentGuardPlace[i][j]--;
            currentGuard--;
            displayRoom[i][j]--;
            remainingRoom+=(!displayRoom[i][j]);
            if(i+1<=m-1){ 
                displayRoom[i+1][j]--;
                remainingRoom+=(!displayRoom[i+1][j]);//cout<<"加了房子了！！！"<<endl;
            }
            if(j+1<=n-1){ 
                displayRoom[i][j+1]--;
                remainingRoom+=(!displayRoom[i][j+1]);//cout<<"加了房子了！！！"<<endl;
            }
            if(j-1>=0){ 
                displayRoom[i][j-1]--;
                remainingRoom+=(!displayRoom[i][j-1]);//cout<<"加了房子了！！！"<<endl;
            }
            if(i-1>=0){ 
                displayRoom[i-1][j]--;
                remainingRoom+=(!displayRoom[i-1][j]);//cout<<"加了房子了！！！"<<endl;
            }
        }
    
        //在(i,j)放置一个机器人，并改变周围展览室状态及剩余未监视房间数
        void change(int i,int j)
        { 
            currentGuardPlace[i][j]++;
            currentGuard++;
            remainingRoom-=(!displayRoom[i][j]);
            displayRoom[i][j]++;
    
            if(j+1<=n-1){ 
                remainingRoom-=(!displayRoom[i][j+1]);
                displayRoom[i][j+1]++;
            }
            if(i+1<=m-1){ 
                remainingRoom-=(!displayRoom[i+1][j]);
                displayRoom[i+1][j]++;
            }
            if(i-1>=0){ 
                remainingRoom-=(!displayRoom[i-1][j]);
                displayRoom[i-1][j]++;
            }
            if(j-1>=0){ 
                remainingRoom-=(!displayRoom[i][j-1]);
                displayRoom[i][j-1]++;
            }
        }
    };
    
    int main(void)
    { 
        Solution solution;
        solution.input();
        solution.init();
        solution.Backtrack(0,0,solution.returnPointer());
        solution.output();
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbGxlcl82_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/1a1a9911147f402284982e9465348313.png