算法:路径遍历(二)图上的路径遍历

本贴最后更新于 1622 天前,其中的信息可能已经斗转星移

一、问题回顾

  还是要简单描述一下问题:有一个 5 X 5 的点方阵,如下图,要想用一笔画将所有的蓝色点连起来,是否有可行路线。需要满足 3 点要求:
  1、笔画必须水平或垂直。
  2、笔画不可以超出方阵边界之外,
  3、每个点只经过一次,且不可以经过黄色点。
  这个问题的数学证明已经在开头的文章中给出,在此不做赘述。这里只考虑它的算法实现。
image.png
  在思考算法之前,需要先对问题进行抽象分析,我们可以将上面的问题理解成下图这样 :
image.png

二、模拟情景分析

  由于题目已经被数学证明没有一条路线能够满足题目要求(证明过程见:这里),所以算法的目的不是为了找到所谓符合要求的路线,而是遍历从出发点向网格中所有点可形成的所有路线。可以假设上面的网格是一个地图,小明同学按照地图在网格中行走,目的是找出从出发点到所有点的所有路线。小明先在地图中规定坐标,网格底边作为 x 轴,左侧的竖边作为 y 轴,那么红色五角星坐标就是(1,4)。小明从原点开始出发,刚开始时地图中所有的交叉点都被标记“未走过”标识。小明随机选择下一个点,假如依次经过(0,0)、(1,0)、(1,1)、(2,1)、(2,2)、(3,2)、(4,2)、(4,1)、(4,0)、(3,0)、(3,1),每往前走一个点,他都会在地图的相应位置标记已经走过。走到(3,1)时,由于四周的(2,1)、(3,2)、(4,1)都已经走到过,所以往前是无路可走的,只能逐步回退,回退之前小明为了下次不再重新走这个线路,他将这个线路记到了本子上,并标记本路线为历史路线,然后回退,每回退一步小明都会在离开的那个位置将“已走过”的标记涂抹掉并改为“未走过”标识,因为这样当下次从其他路线走时还可以走那个位置。当回退到(3,0)时,(3,1)位置就会由标记“已走过”改为标记“未走过”的状态,并发现临近的(2,0)还没有走过,于是不再回退,转向(2,0)。到达(2,0)时,又出现了无路可走的情况,于是记录当下的路线,然后回退并标记地图。当回退到(3,0)时,虽然会发现(3,1)是“未走过”状态,但由于如果走(3,1)的话就会发现这条路线在笔记本的历史路线中已经出现过,所以依然不能走(3,1),继续回退,按照这个原则一直走下去,直到遍历完从起点出发到达地图上所有点的所有路线,小明最终一定会回到起点。此时他笔记本中的历史路线列表,就是从起点达地图上所有点的所有路线。

三、算法分析

  考虑到算法的实现,这显然是利用了数据结构中的“图”。每一次路线尝试,都是对图的深度遍历,算法要做的事情,无非就是随机选择起点,然后不断地深度遍历新的路线。每往前走一步,就将新位置放进栈。这里要注意的是,针对每一次尝试,当走到无路可走时,并不意味着 24 个点全部已经遍历到了,因为根据规则,无路可走的原因可能是当下点的四周位置(下面统称为“邻居”)已经全部走过了,即它们已经在栈中了,或者是走到了边角的位置。那么此时无路可走该怎么办呢?是重新从起点开始呢,还是怎样。理论上都可行,不过考虑到效率,即让算法尽量少做重复的事情,我选择在无路可走时,将当下的路线(一个由点序列组成的数组)做记录(存入一个集合中,这个集合记录着所有历史路线),然后回退并将离开的位置从栈弹出,每次回退都将当下路线记录为历史路线,直到周围存在“没有在栈中的点”时不再回退,而是转向新的位置。此时,最近一次回退的那个历史路线决定了下次不会再走这个路线的方向。(假如连续回退了 N 步,那么最近一次回退的那个历史路线则是临近前 N-1 次回退历史路线的子集)。不断以上面的方式进行下去,由于“地图”是有限的,当所有可能路线全部遍历过时,最终一定会回到起点。此时历史路线集合列表,记录了从起点达地图上所有点的所有路线。

四、算法描述:

  1、输入:一个二维数组 M[26][5]。(第一维度角标 1 到 4 分别代表上右下左四个方向,第二维度角标 1 到 25 分别代表图的每个点,一次从地图的左上到右下为 1 到 25。数组中的每个值,比如 M[20][1]=15 表示地图编号为 20 的点的上边是编号为 15 的点,M[20][2]=0 表示地图编号为 20 的点的右方没有通路。其中 M[i][0]=0,M[0][j]=0)
  2、初始化:定义栈 Q = {1} 和 集合 H = {} .(Q 中记录了当下路径中依次走过的所有点,H 记录着所有的历史路径。)
  3、重复以下动作,直到 Q = {}:
  根据 Q 的栈顶元素 d,和邻接表 M 找出 d 的所有临近点元素,从其中随机选择一个元素,且 Q 中不存在该元素,若找到,将该元素放入 Q 中。若找不到,则将 Q 的副本存入 H 中,并将 d 从 Q 中弹出。
  4、输出:H。

五、算法实现

  到这里,对原始问题的抽象思考过程和算法的理论分析过程已经描述完毕。下面就是用实际的代码实现该算法并做到可视化。如果不考虑可视化,那么随便一个编程语言都可以很方便的实现它,我之前用 java 写过,将结果输出在控制台那种。不过感觉没啥意思,还是想要可视化的感觉。当时很长一段时间我都不知道如何将它可视化,直到我遇到了 React,深入了解后,发现用 React 来完成该算法的可视化,真是再合适不过了。
  由于 React 是面向组件开发的模式,并且可以很容易根据状态来自动渲染页面,所以可视化部分的设计,就变成对原始“地图”的拆解和状态的定义。我设计的最基础的组件和整体样式如下图这样:

Snipaste20190720173848.jpg

  每个位置(点)都有上下左右四个方向,点与点之间,如果存在连线,则将对应方向的线条用 CSS 渲染成“block”,其他渲染成“none”.这个过程在定义好 CSS 样式后,根据数据状态,React 会自动帮助界面渲染,不需要反复用 js 写渲染逻辑。
  最终效果请点击这个 程序链接 1程序链接 2 查看。以下附带部分代码。另外关于实现过程中对性能的优化,我已经做了一些努力,以后也会不断对其优化,欢迎有兴趣的朋友提出高见。

import React, { Component } from 'react';
import './AppDemo.css';
import Grid from './Grid';

class AppDemo extends Component {
    constructor(proprs) {
        super(proprs);
        var width = 5;
        var height = 5;
        var matrix = this.init(width,height);
        var x = 50;
        var start = Math.floor(Math.random() * width * height + 1);
        this.state = {
            matrix: matrix,
            start: start,
            arr: [start],
            historyPath: [],
            width: width,
            height: height,
            timeID: 0,
            speed: 5,
            random: true,
            x: x,
            time: 0
        }
    }
    init(width,height){
        var matrix = [[0, 1, 2, 3, 4]];
        for (var numb = 1; numb <= width * height; numb++) {
            var up = numb > width ? numb - width : 0;
            var right = (numb % width) !== 0 ? numb + 1 : 0;
            var down = numb <= width * (height - 1) ? numb + width : 0;
            var left = ((numb - 1) % width) !== 0 ? numb - 1 : 0;
            var arr = [numb];
            arr.push(up);
            arr.push(right);
            arr.push(down);
            arr.push(left);
            matrix.push(arr);
        }
        return matrix;
    }
    handle() {
        //var beginTime1=0;
        //var beginTime2=0;
        //beginTime1 = new Date().getTime();
        var nowRow = this.state.arr[this.state.arr.length - 1];//获取当下的位置编号
        var arr = this.state.arr;//路径编号
        var matrix = this.state.matrix;//矩阵存储结构
        var historyPath = this.state.historyPath;//历史路径
        if (arr.length > 0) {//如果路径长度>0
            var next = false;//默认找不到路径
            var ran = 1
            if (this.state.random) {
                ran = Math.floor(Math.random() * 4 + 1);
            }
            //var beginTime4 = new Date().getTime();
            for (var i = 0; i < 4; i++) {
                var nextNumb = matrix[nowRow][ran];
                if (nextNumb !== 0 && !this.containNowPath(nextNumb)) {//找到路径
                    arr.push(nextNumb);//将新元素入栈
                    if (!this.containHistoryPath(arr)) {//若新路径没有在历史路径中出现过,则走该路径
                        this.setState({
                            arr: arr
                        });
                        next = true;
                        break;
                    } else {//若新路径在历史路径中出现过,则跳过该路径
                        arr.pop();//放弃该位置
                        ran = ran + 1 > 4 ? 1 : ran + 1;
                    }
                } else {
                    ran = ran + 1 > 4 ? 1 : ran + 1;
                }
            }

            //var beginTime5 = new Date().getTime();
            if (!next) {//如果无路可走
                //判断当下路径(未退步之前)是否包含于历史记录。
                if (!this.containHistoryPath(arr)) {
                    historyPath.push(arr.slice());//若没有包含与历史中,则将新的尝试路径保存进历史路径集中
                }
                arr.pop();//将最后一个元素弹出,相当于后退一步
                this.setState({//修改当前改变了的状态
                    arr: arr,
                    historyPath: historyPath
                });
            }
        } else {//若路径遍历结束,则换一个起点继续遍历。
            this.stop();
            // this.setState({
            //     start: this.state.start + 1,
            //     arr: [this.state.start + 1],
            //     historyPath: [],
            //     len: 5
            // });
        }
        // beginTime2 = new Date().getTime();
        // var time = beginTime2 - beginTime1 ;
        // if(time> this.state.time){
        //     this.setState({//修改当前改变了的状态
        //         time: time
        //     });
        // }
        //alert(time);
    }

    containNowPath(row) {//判断下一个位置是否已经存在当下路径中。
        var r = false;
        for (var i = 0; i < this.state.arr.length; i++) {
            r = this.state.arr[i] === row;
            if (r) {
                break;
            }
        }
        return r;
    }
    containHistoryPath(arr) {//从历史路径中查找是否已经存在下一步要走的路径
        var r = false;
        var historyPath = this.state.historyPath;
        for (var i = historyPath.length - 1; i >= 0; i--) {
            r = historyPath[i].toString().indexOf(arr.toString()) !== -1;
            if (r) {
                break;
            }
        }
        return r;
    }
    render() {
        return (
            <div>
                <div style={{ margin: "50px auto 0px auto", width: (this.state.width * this.state.x) + "px", minWidth: "700px" }}>
                    <div className="control">
                        <button type="button" onClick={() => this.start()}>开始</button>
                        <button type="button" onClick={() => this.stop()}>暂停</button>
                        <button type="button" onClick={() => this.start()}>继续</button>
                        <button type="button" onClick={() => this.step()}>单步</button>
                        <apan style={{ margin: "0px auto 0px 10px", width: "120px", display: "inline-block" }}>尝试次数{this.state.historyPath.length}</apan>
                        <apan style={{ margin: "0px auto 0px 10px" }}>速度</apan>
                        <button style={this.state.speed === 1000 ? { backgroundColor: "#61dafb" } : {}} type="button" onClick={() => this.speed(1000)}>极慢</button>
                        <button style={this.state.speed === 500 ? { backgroundColor: "#61dafb" } : {}} type="button" onClick={() => this.speed(500)}></button>
                        <button style={this.state.speed === 100 ? { backgroundColor: "#61dafb" } : {}} type="button" onClick={() => this.speed(100)}></button>
                        <button style={this.state.speed === 50 ? { backgroundColor: "#61dafb" } : {}} type="button" onClick={() => this.speed(50)}></button>
                        <button style={this.state.speed === 5 ? { backgroundColor: "#61dafb" } : {}} type="button" onClick={() => this.speed(5)}>极快</button>
                        <apan style={{ margin: "0px auto 0px 10px", width: "50px", display: "inline-block" }}></apan>
                        <button style={this.state.random ? { backgroundColor: "#61dafb" } : {}} type="button" onClick={() => this.random()}>随机</button><br />
                    </div>
                    <div className="control2">
                        <button style={{ width: "80px" }} type="button" onClick={() => this.addheight(1)}>增加行+</button>
                        <button style={{ width: "80px" }} type="button" onClick={() => this.addwidth(1)}>增加列+</button>
                        <button style={{ width: "80px" }} type="button" onClick={() => this.big(1)}>放大+</button><br />
                        <button style={{ width: "80px" }} type="button" onClick={() => this.addheight(-1)}>减少行-</button>
                        <button style={{ width: "80px" }} type="button" onClick={() => this.addwidth(-1)}>减少列-</button>
                        <button style={{ width: "80px" }} type="button" onClick={() => this.big(-1)}>缩小-</button>
                    </div>
                    <Grid x={this.state.x} width={this.state.width} height={this.state.height} arr={this.state.arr} />

                </div>
            </div >

        )
    }
    addwidth(n) {
        this.stop();
        var width = this.state.width;
        width = width + n;
        if (width > 0 && width * this.state.x <= 1000) {
            var matrix = this.init(width,this.state.height);
            var start = Math.floor(Math.random() * width * this.state.height + 1);
            this.setState({
                matrix : matrix,
                start: start,
                arr: [start],
                historyPath: [],
                width: width
            });
        } else {
            this.setState({
                width: Math.floor(1000 / this.state.x),
            });
        }
    }
    addheight(n) {
        this.stop();
        var height = this.state.height;
        height = height + n;
        if (height > 0 && height * this.state.x <= 500) {
            var matrix = this.init(this.state.width,height);
            var start = Math.floor(Math.random() * this.state.width * height + 1);
            this.setState({
                matrix:matrix,
                start: start,
                arr: [start],
                historyPath: [],
                height: height
            });
        } else {
            this.setState({
                height: Math.floor(500 / this.state.x),
            });
        }
    }
    big(n) {
        var x = this.state.x;
        x = x + n;
        if (x > 0 && ((x * this.state.width <= 1000) || (x*this.state.height<=500)) ){
            this.setState({
                x: x
            });
        } else {
            this.setState({
                x: Math.floor(x * this.state.width > x*this.state.height?1000/this.state.width:500/this.state.height)
            });
        }
    }
    // shouldComponentUpdate(nextProps, nextState){
    //     return nextState.arr.length>100;
    // }
    step() {
        this.stop();
        this.handle();
    }
    start() {
        var timeID = this.state.timeID;
        if (timeID === 0) {
            timeID = setInterval(
                () => this.handle(),
                this.state.speed
            );
        }
        this.setState({
            timeID: timeID
        });
    }
    stop() {
        var timeID = this.state.timeID;
        if (timeID !== 0) {
            clearInterval(timeID);
        }
        this.setState({
            timeID: 0
        });
    }
    componentDidMount() {
        var matrix = [[0, 1, 2, 3, 4]];
        var width = this.state.width;
        var height = this.state.height;
        for (var numb = 1; numb <= width * height; numb++) {
            var up = numb > width ? numb - width : 0;
            var right = (numb % width) !== 0 ? numb + 1 : 0;
            var down = numb <= width * (height - 1) ? numb + width : 0;
            var left = ((numb - 1) % width) !== 0 ? numb - 1 : 0;
            var arr = [numb];
            arr.push(up);
            arr.push(right);
            arr.push(down);
            arr.push(left);
            matrix.push(arr);
        }
    }
    speed(n) {
        var timeID = this.state.timeID;
        clearInterval(timeID);
        timeID = 0;
        timeID = setInterval(
            () => this.handle(),
            n
        );
        this.setState({
            timeID: timeID,
            speed: n
        });
    }
    random() {
        this.setState({
            random: !this.state.random
        });
    }

    sleep(numberMillis) {
        var now = new Date();
        var exitTime = now.getTime() + numberMillis;
        while (true) {
            now = new Date();
            if (now.getTime() > exitTime)
                return true;
        }
    }
}

export default AppDemo;
  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...