gong的文章

  • 图的深度优先搜索(DFS)的应用--马踏棋盘问题(骑士周游问题)

    将马随机放在国际象棋的 8X8 棋盘Board[0~7] [0~7]的某个方格中,马按走棋规则(马走日字)进行移动。要求每个方格只进入一次,走遍棋盘上全部64个方格。
    马踏棋盘游戏代码实现
    马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
    如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了53个点,走到了第53个,坐标(1,0) ,发现已经走到尽头,没办法,那就只能回退了,查看其他的路径,就在棋盘上不停的回退…
    分析第一种方式的问题,并使用贪心算法(greedyalgorithm)进行优化。解决马踏棋盘问题。
    使用前面的游戏来验证算法是否正确。
    解决步骤和思路: https://blog.csdn.net/zhang0558/article/details/50497298

    创建棋盘chessBoard,是一个二维数组
    将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(ArrayList),最多有8个位置,每走-步,就使用step+1
    遍历ArrayList中存放的所有位置,看看哪个可以走通,如果走通,就继续,走;不通,就回溯
    判断马儿是否完成了任务,使用step 和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘置0

    注意:马儿不同的走法(策略),会得到不同的结果,效率也会有影响(优化)
    public class HorsechessBoard { private static int X; // 表示列 private static int Y; // 表示行 private static boolean visited[]; // 是否被访问 private static boolean finished; // 是否全部完成 // 进行行走 public static void traversal(int[][] arr, int row, int col, int step) { arr[row][col] = step; visited[row * X + col] = true;// 初始位置标记为已访问 // 获取下一步集合 ArrayList<Point> ps = next(new Point(col, row)); sort(ps); //然后在traversal方法当中的ps进行排序: // 遍历集合 while (!ps.isEmpty()) { Point p = ps.remove(0); // 判断该点是否访问过 if (!visited[p.y * X + p.x]) { // 没有访问过 traversal(arr, p.y, p.x, step+1); } } if (step < X * Y && !finished) { arr[row][col] = 0; visited[row * X + col] = false; } else { finished = true; } } public static void sort(ArrayList<Point> ps) { ps.sort(new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { int count1 = next(o1).size(); int count2 = next(o2).size(); if (count1 < count2) { return -1; } else if (count1 == count2) { return 0; } else { return 1; } } }); } // 根据当前位置计算还有哪些位置可以走 static int weizhi[][] = {{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}}; public static ArrayList<Point> next(Point cutPoint) { ArrayList<Point> ps = new ArrayList<Point>(); Point p1 = new Point(); // 判断是否可以走下一个位置 if ((p1.x = cutPoint.x - 2) >= 0 && (p1.y = cutPoint.y - 1) >= 0) { ps.add(new Point(p1)); } if ((p1.x = cutPoint.x - 1) >= 0 && (p1.y = cutPoint.y - 2) >= 0) { ps.add(new Point(p1)); } if ((p1.x = cutPoint.x + 1) < X && (p1.y = cutPoint.y - 2) >= 0) { ps.add(new Point(p1)); } if ((p1.x = cutPoint.x + 2) < X && (p1.y = cutPoint.y - 1) >= 0) { ps.add(new Point(p1)); } if ((p1.x = cutPoint.x + 2) < X && (p1.y = cutPoint.y + 1) < Y) { ps.add(new Point(p1)); } if ((p1.x = cutPoint.x + 1) < X && (p1.y = cutPoint.y + 2) < Y) { ps.add(new Point(p1)); } if ((p1.x = cutPoint.x - 1) >= 0 && (p1.y = cutPoint.y + 2) < Y) { ps.add(new Point(p1)); } if ((p1.x = cutPoint.x - 2) >= 0 && (p1.y = cutPoint.y + 1) < Y) { ps.add(new Point(p1)); } return ps; } public static void main(String[] args) { X = 9;//chg to 6 Y = 9; int row = 5; int col = 5; int[][] arr = new int[X][Y]; visited = new boolean[X * Y]; System.out.println("开始"); long start = System.currentTimeMillis(); traversal(arr, row-1, col-1,1); long end = System.currentTimeMillis(); System.out.println("耗时 = "+ (end-start)+" 毫秒"); for(int[] rows:arr) { for(int step :rows) { System.out.print(step+"\t"); } System.out.println(); } System.out.println("结束"); }}
    0  留言 2020-08-24 15:51:20
  • 图结构中寻找最小生成树的一种算法--Prim算法

    普里姆算法是图结构中寻找最小生成树的一种算法。所谓生成树,即为连通图的极小连通子图,其包含了图中的n个顶点,和n-1条边,这n个顶点和n-1条边所构成的树即为生成树。当边上带有权值时,使生成树中的总权值最小的生成树称为最小代价生成树,简称最小生成树。最小生成树不唯一,且需要满足一下准则:

    只能使用图中的边构造最小生成树
    具有n个顶点和n-1条边
    每个顶点仅能连接一次,即不能构成回路
    获得图的最小生成树,即在保证图中所有顶点不重复连通的情况下,使得总权值最小

    如何使总权值最小?
    通过构造邻接矩阵找最小总权值,如图1右边所示。邻接矩阵中保存了顶点之间的连通关系和权值大小,我们可以构造最小代价数组lowcost[n]来记录图中与各顶点相连的最小权值(其中n为顶点数)。再构造顶点编号数组adjvex[],用于记录lowcost中权值所对应的顶点编号。初始化lowcost数组为邻接矩阵中第一行,即lowcost[] = {0,10,#,#,#,11,#,#,#} (这里用“#”表示图中无穷)。除去起始顶点v0外,其余为n-1条边的权值。我们将v1行的权值与lowcost数组中保存的权值对比,如果对应的权值比lowcost中的小,则替换之,这里比较后得到的lowcost[] = {0,10,18,#,#,11,16,#,12}。依次遍历邻接矩阵中剩余的v2到v8,即可得到总权值最小的lowcost数组。
    但是,这样虽然保证了总权值最小,但是不能保证所有节点是连通的。
    由lowcost数组可以知道,权值为“#”是无效权值,即与当前顶点不相连的顶点,权值为0表示顶点本身或者说是已经匹配到的相连的最小权值点。在每次重建lowcost数组之后,遍历数组中的权值,将权值最小的项置为0,表示对应顶点已经匹配到了权值最小的边。并记录该顶点的编号为minId,下次更新lowcost数组从minId开始搜寻,以此类推。比如,初始化lowcost后将权值最小的顶点,即v1置为0,得到lowcost[] = {0,0,#,#,#,11,#,#,#},minId = 1。之后,从v1开始替换lowcost中的权值。当lowcost中所有的权值都置为0时,即所有顶点都连通且保证总权值最小。
    public class Prim { public static void main(String[] args) { int min = Integer.MAX_VALUE; //定义min变量保存每一个lowcost数组中的最小值,默认为无效权值 int minId = 0;//定义minId变量保存最小权值的顶点编号 int sum = 0;//定义sum变量记录总权值 String[] Vertex = new String[] { "A", "B", "C", "D", "E", "F" }; //顶点集 int[][] Matrix = new int[6][]; //邻接矩阵 //邻接矩阵初始化 Matrix[0] = new int[] { 0, 7, 5, 1, min, min }; Matrix[1] = new int[] { 7, 0, min, 6, 3, min }; Matrix[2] = new int[] { 5, min, 0, 7, min, 2 }; Matrix[3] = new int[] { 1, 6, 7, 0, 6, 4 }; Matrix[4] = new int[] { min, 3, min, 6, 0, 7 }; Matrix[5] = new int[] { min, min, 2, 4, 7, 0 }; int vertexSize = Vertex.length;//顶点个数 int lowcost[] = new int[vertexSize];//定义最小代价矩阵 int adjvex[] = new int[vertexSize];//定义数组保存最小权值的顶点编号 //lowcost矩阵初始化 for(int i=0;i<vertexSize;i++) { lowcost[i] = Matrix[0][i]; } for(int i=1;i<vertexSize;i++) { min = Integer.MAX_VALUE; minId = 0; for(int j=1;j<vertexSize;j++) { if(lowcost[j]!=0&&lowcost[j]<min) {//找到lowcost中的最小有效权值 min = lowcost[j];//记录最小值 minId = j;//记录最小权值的顶点编号 } } lowcost[minId] = 0; sum += min; System.out.println("连接顶点:" +Vertex[adjvex[minId]]+" 权值:" +min); for(int j=1;j<vertexSize;j++) { if(lowcost[j]!=0&&Matrix[minId][j]<lowcost[j]) {//在邻接矩阵中以编号为minId的顶点作为下一个顶点对lowcost中进行最小值替换 lowcost[j] = Matrix[minId][j]; adjvex[j] = minId; } } } System.out.println("总权值为:" + sum); }}
    0  留言 2020-08-24 15:51:30
eject