使用深度优先搜索方法解决大规模迷宫问题

AI 10个月前 admin

42 0 0

DFS算法又称深度优先搜索：

1. dfs是一种在开发爬虫早期使用较多的方法，是搜索算法的一种。

2. dfs的目的是要达到被搜索结构的叶结点，即那些不包含任何超链的HTML文件。

3. dfs根据已有的邻接矩阵或邻接表用递归方法编写深度优先搜索遍历算法，并输出遍历结果。

作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率非常低，在数据规模变大时，这种算法就显得力不从心了。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.

这道题目的迷宫的尺寸非常大，约5000*5000，近2500万个像素点，如果每一个像素点的识别和路径解析超过0.001秒，那么全部遍历就需要近7个小时，所以需要尽可能的减少遍历的数量，以及单步所需的时间。这个时候DFS比BFS要省时很多

使用深度优先搜索方法解决大规模迷宫问题

这是放大30倍后的迷宫部分截图，红色的点代表入口，原图右下角的绿点代表出口

使用深度优先搜索方法解决大规模迷宫问题

先将图片转为二维列表，通过pillow识别图片像素点，黑色为墙壁，白色为通道，并识别开始和结束的颜色

pic = Image.open(file)
x_size,y_size = pic.size
x_block,y_block = 1,1 #get_block(pic)
array = np.zeros((x_size,y_size))
for y in range(0,pic.size[1]):
    for x in range(0,pic.size[0]):
        out = pic.getpixel((x, y))
     if  out == (0,0,0):
            array[y,x] = map_wall
        elif out == (255, 255, 255) :
            array[y,x] = map_path
        elif out == (255, 0, 0) :
            array[y,x] = map_start
        elif out == (125, 255, 127) :
            array[y,x] = map_dest

再根据二维列表迷宫的尺寸，构建一个空的二维列表，用来跟进迷宫的遍历进度

self.map = np.zeros((size,size))

主程序需要按照下、右、左、上的顺序来确认每个点的四周，如果遇到通道，则将通道的路径加到self.exist_stack中，如果遇到墙壁，则弹出最新的一个self.exist_stack，并将其作为下一个点。直到寻找到出口为止。

因为迷宫的尺寸非常大，还需要每隔一定步数，来渲染当前的位置及路径

def save_pic(self):
    # try:
    max_x = len(self.map[0])
    max_y = len(self.map)
    # MAX = len(self.map)
    pic = Image.new("RGB", (max_x+1, max_y+1))
    for y in range(0,max_y):
        for x in range(0,max_x):
            if self.map[y][x] == self.map_path:
                pic.putpixel([x, y], (255, 255, 255))
            elif self.map[y][x] == self.map_wall:
                pic.putpixel([x, y], (0, 0, 0))
            elif self.map[y][x] == self.map_dest:
                pic.putpixel([x, y], (0, 0, 255))
            elif self.map[y][x] == self.map_start:
                pic.putpixel([x, y], (255, 0, 0))
                begin_x = x
                begin_y = y
    for step in self.next_path[:-1]: # 开始和结尾点不覆盖
        if   step == self.move["right"]:
            begin_x = begin_x + 1
        elif step == self.move["down"]:
            begin_y = begin_y + 1
        elif step == self.move["left"]:
            begin_x = begin_x - 1
        elif step == self.move["up"]:
            begin_y = begin_y - 1
        pic.putpixel([begin_x, begin_y], (0, 255, 0))
    pic.save(self.save_pic_addr)

整体的代码：

#coding=utf-8
import os
import time
import numpy as np
from PIL import Image
import time
import random
import sys

class Robot(object):
    def __init__(self,size=100):
        self.start_time = time.time()
        self.end_time = time.time()
        self.maze_wall = 8
        self.maze_path = 1
        self.maze_start = 3
        self.maze_dest = 4
        self.map_wall = 8
        self.map_path = 1
        self.map_start= 3
        self.map_dest = 4
        self.map_none = 0
        self.map = np.zeros((size,size))
        self.move={"up":"u","down":"d","left":"l","right":"r"}
        self.move_list = [self.move['up'],self.move['left'],self.move['right'],self.move['down']]
        # 坐标
        self.now_x = 1
        self.now_y = 1
        self.next_x = 1
        self.next_y = 1
        self.exist_stack = []
        self.point_round = False # 每个点四周的点是否检测完
        self.all_finish = False
        self.now_path = []
        self.next_path = []
        self.save_pic_count = 0
        self.save_pic_addr = "./save_pic.png"
    def save_pic(self):
        max_x = len(self.map[0])
        max_y = len(self.map)
        pic = Image.new("RGB", (max_x+1, max_y+1))
        for y in range(0,max_y):
            for x in range(0,max_x):
                if self.map[y][x] == self.map_path:
                    pic.putpixel([x, y], (255, 255, 255))
                elif self.map[y][x] == self.map_wall:
                    pic.putpixel([x, y], (0, 0, 0))
                elif self.map[y][x] == self.map_dest:
                    pic.putpixel([x, y], (0, 0, 255))
                elif self.map[y][x] == self.map_start:
                    pic.putpixel([x, y], (255, 0, 0))
                    begin_x = x
                    begin_y = y
        for step in self.next_path[:-1]: # 开始和结尾点不覆盖
            if   step == self.move["right"]:
                begin_x = begin_x + 1
            elif step == self.move["down"]:
                begin_y = begin_y + 1
            elif step == self.move["left"]:
                begin_x = begin_x - 1
            elif step == self.move["up"]:
                begin_y = begin_y - 1
            pic.putpixel([begin_x, begin_y], (0, 255, 0))
        pic.save(self.save_pic_addr)
        # except Exception as e:
        #     print(str(e))

    def get_point_round(self):
        # 按照下 右 左 上的顺序遍历
        list = [(-1,0),(0,-1),(0,1),(1,0)] # y,x 因为exist是pop的结果,所以应该上 左 右 下的顺序遍历
        # 遍历四周方向
        for index,offset in enumerate(list):
            if self.map[self.now_y+offset[0],self.now_x+offset[1]] == 0: # 该格为0 ,未检测过
                self.next_y = self.now_y+offset[0]
                self.next_x = self.now_x+offset[1]
                self.next_path = self.now_path + [self.move_list[index]] # 将对应路径添加
                return False
        self.point_round = True
        return True

    def next_step(self):
        self.get_point_round()
        if not self.point_round: # 附近四个点还未检测完,返回检测四个点
            return False
        else: # 检测完四个点，即将切换base点
            if len(self.exist_stack) >= 1: # 判断存在出口,弹出出口栈
                self.now_x,self.now_y,self.now_path = self.exist_stack.pop() # 弹出最近的分支
                self.point_round = False
                self.next_step()
            # 如果没有出口，则意味着迷宫已经结束，且没有发现出口
            elif len(self.exist_stack) == 0:
                print("迷宫无解")
                print(self.next_path)
                exit(0)

    def set_point(self,map_value):
        self.map[self.next_y,self.next_x] = map_value # 先给地图对应的点赋值
        if map_value == 1: # 遇到通道，添加出口栈
            self.exist_stack.append([self.next_x,self.next_y,self.next_path]) # 添加分支
        elif map_value == 8: # 遇到墙壁
            if self.save_pic_count >= 100000: # 图片进度保存
                self.save_pic()
                self.save_pic_count = 0
            else:
                self.save_pic_count += 1
        elif map_value == 4: # 遇到出口
            self.all_finish = True
            self.end_time = time.time()
            print("已经发现终点")
            print("Robot running time : " + str(int((self.end_time-self.start_time)))+" s")


    def pic2array(self,file,map_wall = 8,map_path=1,map_start= 3,map_dest = 4):
        try:
            pic = Image.open(file)
            # pic= pic.convert("1") # 转为黑白二值图像
            x_size,y_size = pic.size
            x_block,y_block = 1,1 # block代表多少个像素点是一个单元格
            array = np.zeros((x_size,y_size))
            for y in range(0,pic.size[1]):
                for x in range(0,pic.size[0]):
                    out = pic.getpixel((x, y))
                    if  out == (0,0,0):
                        array[y,x] = map_wall
                    elif out == (255, 255, 255) :
                        array[y,x] = map_path
                    elif out == (255, 0, 0) :
                        array[y,x] = map_start
                    elif out == (125, 255, 127) :
                        array[y,x] = map_dest
            return array
        except Exception as e:
            self.exception(e,func_name=sys._getframe().f_code.co_name)
            raise
        
    def array_solve(self,maze):
        self.now_x = 1
        self.now_y = 1
        self.map = np.zeros((len(maze[0]),len(maze)))
        while not self.all_finish:
            self.next_step()
            if self.next_x <0 or self.next_y < 0 or self.next_y >=len(self.map) or self.next_x >= len(self.map[0]) :
                self.set_point(self.map_wall)
            # 对三种类型进行判断
            elif maze[self.next_y][self.next_x] == self.maze_wall:
                self.set_point(self.map_wall)
            elif maze[self.next_y][self.next_x] == self.maze_path:
                self.set_point(self.map_path)
            elif maze[self.next_y][self.next_x] == self.maze_dest:
                self.set_point(self.map_dest)
            elif maze[self.next_y][self.next_x] == self.maze_start:
                self.set_point(self.map_start)
        return self.next_path


r = Robot()  
pic_addr = "./maze.png"
maze = r.pic2array(pic_addr)
output = r.array_solve(maze)
with open("./maze_result.txt","w") as f:
    f.write("".join(output))