算法5.旅行售货员问题和数独游戏。

冷不防 2022-07-13 08:23 255阅读 0赞

1.  某售货员要到4个城市去推销商品，已知各城市之间的路程，如右图所示。请问他应该如何选定一条从城市1出发，经过每个城市一遍，最后回到城市1的路线，使得总的周游路程最小？并分析所设计算法的计算时间复杂度。  
    ![这里写图片描述][SouthEast]  
    (1) 算法设计思路  
    解向量：\{1,2,3,4,1\}\{1,2,4,3,1,\}\{1,3,4,2,1\}\{1,3,2,4,1\}\{1,4,2,3,1\}\{1,4,3,2,1\}  
    解空间：是一个排序树，树的叶结点个数为（n-1）!=6  
    上界函数：当前第一次所得到的值作为约束条件，然后比该值小时更新约束值  
    int n,图的顶点数，int\[\] x 当前解，int\[\] bestx 当前最优解，int\[\]\[\] a 图的邻接矩阵，int cc 当前费用，int bestc 当前最优值，No 无边标记  
    (2) 算法实现的伪代码及其计算时间复杂度分析  
    求解旅行售货员问题的算法back（int t）  
    输入：t为当前城市的个数  
    输出：最短路径和其对应值

s1:  If (t=n){
    s2: if (a[x[n-1]][x[n]]!=No&&a[x[n]][1]!=No && (cc+a[x[n-1]][n]+a[x[n]][1])<bestc || bestc=No){ s3: for (inti =1 to n )best[i]=x[i] s4: bestc=cc+ a[x[n-1]][n]+a[x[n]][1] s5: } s6: else{ s7: for (inti =t to n){ s8: if(a[x[t-1]][i]!=No && (cc+a[x[n-1]][n]+a[x[n]][1]<bestc || bestc =No)){ s9: swap(x[t],x[i]) ; s10: cc+=a[x[t-1]][t]; s11: back(t+1) s12: cc-=a[x[t-1]][t] s13: swap(x[t],x[i]) s14: } s15: }

算法fucntionA的计算时间复杂度分析：
    O(n!)

(3) 实验代码及运行结果

public class TSP {
            static int[] x = new int[5];
            static int[] bestx = new int[5];
            static int[][] a = new int[5][5];
            static int cc = 0;
            static int no = 10000;
            static int bestc = no;
            static int n = 4;
    
            static void back(int i) {
                if (i == n) {
                    if (a[x[n - 1]][x[n]] != 0
                            && a[x[n]][1] != 0
                            && (cc + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc || bestc == 0)) {
                        for (int j = 1; j <= n; j++)
                            bestx[j] = x[j];
                        bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];
                    }
                } else {
                    for (int j = i; j <= n; j++) {
                        // 是否可进入x[j]子树?
                        if (a[x[i - 1]][x[j]] != 0
                                && (cc + a[x[i - 1]][x[i]] < bestc || bestc == 0)) {
                            // 搜索子树
                            // swap(x[i], x[j]);
                            int temp1 = x[i];
                            x[i] = x[j];
                            x[j] = temp1;
                            cc += a[x[i - 1]][x[i]]; // 当前费用累加
                            back(i + 1); // 排列向右扩展,排列树向下一层扩展
                            cc -= a[x[i - 1]][x[i]];
                            // swap(x[i], x[j]);
                            int temp2 = x[i];
                            x[i] = x[j];
                            x[j] = temp2;
                        }
                    }
                }
            }
    
            // private static void swap(int i, int j) { 
            // // TODO Auto-generated method stub
            // int temp = i;
            // i = j;
            // j = temp;
            // }
    
            public static void main(String[] args) {
                a[1][1] = no;
                a[1][2] = 30;
                a[1][3] = 6;
                a[1][4] = 4;
                a[2][1] = 30;
                a[2][2] = no;
                a[2][3] = 5;
                a[2][4] = 10;
                a[3][1] = 6;
                a[3][2] = 5;
                a[3][3] = no;
                a[3][4] = 20;
                a[4][1] = 4;
                a[4][2] = 10;
                a[4][3] = 20;
                a[4][4] = no;
    
                for (int i = 0; i <= 4; i++)
                    x[i] = i;
                // x[1]=1;
                // x[2]=3;x[3]=2;x[4]=4;
                back(2);
                System.out.print("最优路劲为：");
                for (int i = 1; i <= 4; i++)
                    System.out.print(bestx[i]+"->");
                System.out.println(x[1]);
                System.out.println("最小值为"+bestc);
            }
        }

//  
![这里写图片描述][SouthEast 1]  
//

(4) 体会  
用回溯算法搜索排列树的算法框架可以描述为

void back(int t){
    if (t>n) output(x);
    else for (inti =t,i<n;i++){
    swap(x[t],x[i]);
    if( contriant(t)&&bound(t)) back(t+1)
    swap(x[t],x[i])
    }
    }

1.  数独游戏：九宫格是在81个格子(9×9)中，要满足以下条件：① 每个横行和竖列中的9个格子都包含数字1～9，且不重复；② 每个黑色粗实线围住的9个格子(3×3)都包含数字1～9，且不重复。如图所示：  
    要求：找出给定数字的九宫格。  
    输入：输入9行9列81个数字，其中0表示要填的数字。  
    输出：输出满足条件的九宫格。  
    ![这里写图片描述][SouthEast 2]  
    某测试样例如下：  
    ![这里写图片描述][SouthEast 3]  
    (1) 算法设计思路  
    数独游戏是N后问题的变形版本。将n\*n看成二维矩阵，行i列j，解空间是完成n叉树。  
    先判断要变化的数是否为0，如果为0，在行，列和小九宫格中判断有没有相同数字，有相同数字则+1，直到9，如果不为0，直接变化下一个数。

(2) 算法实现的伪代码及其计算时间复杂度分析  
求解数独游戏的算法back(int i,int j)  
输入：数组 的行i，列j  
输出：满足条件的九宫格

s16:  if(i=8并且j=9){
    s17: 输出满足条件的九宫格
    s18: }
    s19: if (j=9){
    s20: j=0;i++
    s21: } 
    s22:  if (x[i][j]=0)
    s23: for (int n=1 to 9){
    s24: if (判断是否在行，列，小九宫格中出现重复的值){
    s25: x[i][j]=n;
    s26: back(i,j+1)
    s27: x[i][j]=0;
    s28: }
    s29: else back(i,j+1)

算法fucntionB的计算时间复杂度分析：
    O(n^n)

(3) 实验代码及运行结果

public class 数独游戏 {
            static int[][] bestx = new int[9][9];
            static int[][] x = { { 0, 6, 1, 0, 3, 0, 0, 2, 0 },
                    { 0, 5, 0, 0, 0, 8, 1, 0, 7 }, { 0, 0, 0, 0, 0, 7, 0, 3, 4 },
                    { 0, 0, 9, 0, 0, 6, 0, 7, 8 }, { 0, 0, 3, 2, 0, 9, 5, 0, 0 },
                    { 5, 7, 0, 3, 0, 0, 9, 0, 0 }, { 1, 9, 0, 7, 0, 0, 0, 0, 0 },
                    { 8, 0, 2, 4, 0, 0, 0, 6, 0 }, { 0, 4, 0, 0, 1, 0, 2, 5, 0 }, };;
            static int cc = 0;
            static int bestc;
    
            static void back(int i, int j) {
                if (i == 8 && j == 9) {
                    for (int a = 0; a <= 8; a++)
                        for (int b = 0; b <=8; b++)
                            bestx[a][b] = x[a][b];
                    return;
                }
                //如果j=9，则重置j，然后行+1
                if (j == 9) {
                    j = 0;
                    i++;
                }
                if (x[i][j] == 0)
                    for (int n = 1; n < 10; n++) {
                        if (!boo(i, j, n)) {
       //判断是否在行，列，小九宫格中出现重复的值
                            x[i][j] = n;
                            back(i, j + 1);
                            x[i][j] = 0;
                        }
                    }
                else
                    back(i, j + 1);
            }
            //判断是否在行，列，小九宫格中出现重复的值
            static boolean boo(int i, int j, int k) {
                int m = i / 3;
                int n = j / 3;
                for (int a = 0; a < 9; a++) {
                    //判断行
                    if (k == x[i][a])
                        return true;
                    //判断列
                    if (k == x[a][j])
                        return true;
                    //判断小九宫格
                    if (k == x[3 * m + a / 3][3 * n + a % 3])
                        return true;
                }
                return false;
            }
    
            public static void main(String[] args) {
                System.out.println("test");
                back(0, 0);
                System.out.println("test");
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++) {
                        if (j < 8)
                            System.out.print(bestx[i][j] + " ");
                        else {
                            System.out.println(bestx[i][j]);
                        }
                    }
                }
            }
        }

/![这里写图片描述][SouthEast 4]  
(4) 体会  
回溯算法一般都有一个套路，先找出问题的解空间，再思考回溯方法。  
用回溯算法搜索子集树的一般算法可以描述为：

void back(int i){
        if (i>n) output(x);
        else 
        for (int j=0 to n){
        x[t]=i,
        if (constraint(i)&&bound(i)) back(i+1)
        }
        }

[SouthEast]: /images/20220713/23eb22f0abc6428d8b9be40b3ec7ba49.png
[SouthEast 1]: /images/20220713/f5d5f5ad56124ce1abac0f0a0160f7e2.png
[SouthEast 2]: /images/20220713/24437f9ccedd477d9728bdd9176cdd4e.png
[SouthEast 3]: /images/20220713/6c018a559b9e4af987efd587653059fa.png
[SouthEast 4]: /images/20220713/ea8cc7f722cb4cbe9f588d6ee921fcd9.png