以圖文的形式對(duì)深度搜索和廣度搜索的理論進(jìn)行講解時(shí)，可能會(huì)對(duì)一些概念有些模糊，且不太清楚怎么把該理論用程序的方式進(jìn)行復(fù)現(xiàn)并解決這一搜索問題（這說的就是本人）。所以后面我看完了一份實(shí)現(xiàn)這兩種搜索方法的代碼，在這做一個(gè)筆記，希望對(duì)大家有所幫助。

深度搜索和廣度搜索的區(qū)別

兩者本質(zhì)的區(qū)別就是一個(gè)找下一個(gè)節(jié)點(diǎn)時(shí)是做的堆棧（先進(jìn)后出），一個(gè)是做隊(duì)列（先進(jìn)先出）。我們用for循環(huán)和一個(gè)列表來簡(jiǎn)單說明理解一下。這里可能說的不好，如果給大家說模糊了可以不用看

li = []
for i in range(5):
    li.append(i)
print(li) # ==>結(jié)果[0,1,2,3,4]

?1.1 深度優(yōu)先搜索的堆棧

上面的for循環(huán)程序中，列表里面的0是第一個(gè)進(jìn)去的，4是最后一個(gè)進(jìn)去的，所以我們?cè)谶x擇下一個(gè)點(diǎn)時(shí)就會(huì)選擇4。選擇過程也是取列表的最后一位,并將其從列表中刪除

state = li[-1] # 選擇下一步的位置狀態(tài)（當(dāng)作是坐標(biāo)和行動(dòng)方向）
li = li[:-1] # 選中后的狀態(tài)會(huì)進(jìn)入程序運(yùn)算，所以這從列表中刪除選擇后的點(diǎn)
print(li) # ==> [0,1,2,3]

?1.2 廣度優(yōu)先搜索的隊(duì)列

我們的隊(duì)列，簡(jiǎn)單的說就是排隊(duì)，誰先進(jìn)入列表，那么在下一次選擇動(dòng)作節(jié)點(diǎn)時(shí)就優(yōu)先被選中。

state = li[0] # 取列表的第一個(gè)節(jié)點(diǎn)狀態(tài)（同坐標(biāo)和行動(dòng)方向）
li = li[-1] # 選取后進(jìn)入程序運(yùn)算，并從列表中刪除該狀態(tài)點(diǎn)
print(li) # ==> [1,2,3,4]

探索集?

在程序搜索過程中保存我們已經(jīng)探索過的所有節(jié)點(diǎn)坐標(biāo)，在程序中會(huì)一直對(duì)這個(gè)集合進(jìn)行判斷，保證不會(huì)在子節(jié)點(diǎn)和父節(jié)點(diǎn)之間來回探索，創(chuàng)建形式如下代碼。

explore = set() # 創(chuàng)建探索集合

深度優(yōu)先搜索

2.1? 數(shù)據(jù)形式及處理

本文所采用的數(shù)據(jù)形式為txt文本，文本中內(nèi)容如下：

 *****

 ** **
 **B**
 *  **
 * ***
A  ***

數(shù)據(jù)由A、B、*號(hào)和空格組成，其中*號(hào)表示不可通行的墻，A是我們的起始點(diǎn)，B是我們的目標(biāo)點(diǎn)，空格表示可通行的點(diǎn)。

用代碼實(shí)現(xiàn)數(shù)據(jù)處理并轉(zhuǎn)換為坐標(biāo)形式，如下所示：

class Maze():

    def __init__(self, filename):

        # Read file and set height and width of maze
        """
        初始化操作，找到文件中的起點(diǎn)a和終點(diǎn)b是否存在
        存在進(jìn)行行列的遍歷，找到A,B在文本中的坐標(biāo)點(diǎn)
        :param filename:我們傳入的txt文本，文本內(nèi)容如上所示 

        """
        with open(filename) as f:
            contents = f.read()

        # Validate start and goal 判斷是否存在起始點(diǎn)和目標(biāo)點(diǎn)位，不存在退出程序
        if contents.count("A") != 1:
            raise Exception("maze must have exactly one start point")
        if contents.count("B") != 1:
            raise Exception("maze must have exactly one goal")

        # Determine height and width of maze 找到文本的長(zhǎng)寬，做循環(huán)起到記錄坐標(biāo)點(diǎn)的作用
        contents = contents.splitlines()
        self.height = len(contents)
        self.width = max(len(line) for line in contents)

        # Keep track of walls
        self.walls = []
        # 這里循環(huán)找到所有坐標(biāo)，及A、B、*號(hào)和空格所在的坐標(biāo)點(diǎn)并保存
        for i in range(self.height):
            row = []
            for j in range(self.width):
                try:
                    if contents[i][j] == "A":
                        self.start = (i, j)
                        row.append(False)
                    elif contents[i][j] == "B":
                        self.goal = (i, j)
                        row.append(False)
                    elif contents[i][j] == " ":
                        row.append(False)
                    else:
                        row.append(True)
                except IndexError:
                    row.append(False)
            self.walls.append(row)

        self.solution = None

代碼解釋（有編程經(jīng)驗(yàn)的看上面代碼即可 ）：我們向Maze類里面?zhèn)魅胛覀兊膖xt文本，打開并讀取其中的內(nèi)容。對(duì)內(nèi)容進(jìn)行判斷（是否存在起始點(diǎn)和目標(biāo)點(diǎn)）。獲取內(nèi)容的高度和寬度，本文所傳入的高寬為 7*5 （最上面那個(gè)很多*號(hào)的就是）。循環(huán)高度和寬度，找到A點(diǎn)和B點(diǎn)的坐標(biāo)，將空格和A、B點(diǎn)在row列表中保存為False，*號(hào)保存為True，最后將每一行的row列表保存到self.wall的列表當(dāng)中。在后續(xù)找點(diǎn)時(shí)判斷self.wall[i][j]及第 i 行第 j 列的布爾值是否為True，是則代表無法通行。

2.2節(jié)點(diǎn)保存、路徑搜索及路徑回溯

我們可以通過PIL庫(kù)中的Image, ImageDraw，將以上處理結(jié)果轉(zhuǎn)換為圖片的形式，紅色代表起始點(diǎn)，綠色代表目標(biāo)點(diǎn)，白色為可以通過的節(jié)點(diǎn)。我們?cè)诤罄m(xù)過程都以下圖為例。

2.2.1 節(jié)點(diǎn)保存

我們使用class類的方式保存當(dāng)前狀態(tài)坐標(biāo)、行動(dòng)的方向和父節(jié)點(diǎn)（父節(jié)點(diǎn)也是這個(gè)類，也存著坐標(biāo)、行動(dòng)和父節(jié)點(diǎn)），代碼如下：

class Node():
    def __init__(self, state, parent, action):
        self.state = state
        self.parent = parent
        self.action = action

?我們每在后面while循環(huán)實(shí)例化該類時(shí)，都會(huì)在內(nèi)存中有記錄。可以看python類的基礎(chǔ)知識(shí)

2.2.2 路徑搜索

    def neighbors(self, state):
        """
        在調(diào)用這個(gè)函數(shù)的時(shí)候會(huì)傳入當(dāng)前狀態(tài)的坐標(biāo)點(diǎn)。也就是我們?cè)诔绦蛑?        自己定義下一步優(yōu)先走的方向，在candidates列表里面就是上下左右的
        順序進(jìn)行移動(dòng) 以點(diǎn)（0，0）為例，得到的candidates列表就是
        [
        "up",(-1,0),
        "down",(1,0),
        "left",(0,-1),
        "right",(0,1)    
        ]
        得到行動(dòng)列表后開始進(jìn)行循環(huán)判斷，判斷是否超出長(zhǎng)和寬，以及self.wall[r][c]是否為True，
        如果都不滿足就代表可以行動(dòng)，添加到result列表
        """
        row, col = state
        candidates = [
            ("up", (row - 1, col)),
            ("down", (row + 1, col)),
            ("left", (row, col - 1)),
            ("right", (row, col + 1))
        ]

        result = []
        # 保存可以走的方向， 判斷是否在邊界以及是否有墻 self.wall列表中的是bool
        for action, (r, c) in candidates:
            if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
                result.append((action, (r, c)))
        return result


    def solve(self):
        """Finds a solution to maze, if one exists."""

        # Keep track of number of states explored
        self.num_explored = 0

        # Initialize frontier to just the starting position
        # 初始化起始點(diǎn)的節(jié)點(diǎn)，并將其保存到StackFrontier()類里面的frontier列表當(dāng)中（保存的是一個(gè)對(duì)象）
        
        start = Node(state=self.start, parent=None, action=None)
        frontier = StackFrontier()
        frontier.add(start)

        # Initialize an empty explored set 初始化探索集
        self.explored = set()

        # Keep looping until solution found 循環(huán)查找路徑
        while True:
            # If nothing left in frontier, then no path
            if frontier.empty():
                raise Exception("no solution")

            # Choose a node from the frontier
  
            # 獲取并子節(jié)點(diǎn)（坐標(biāo)和行動(dòng)方向，以及父節(jié)點(diǎn)）并從邊界列表中刪除該節(jié)點(diǎn)（具體看StackFrontier類的remove函數(shù)），其過程與最開始的堆棧列表過程相同
            node = frontier.remove()
            self.num_explored += 1

            # If node is the goal, then we have a solution
            if node.state == self.goal:
                actions = []
                cells = []
                # while循環(huán)對(duì)路徑進(jìn)行回溯（過程在文中進(jìn)行簡(jiǎn)紹）
                while node.parent is not None:
                    actions.append(node.action)
                    cells.append(node.state)
                    node = node.parent
                print(cells)
                actions.reverse()
                cells.reverse()
                self.solution = (actions, cells)
                return

            # Mark node as explored
            self.explored.add(node.state)

            # Add neighbors to frontier 返回的執(zhí)行列表是 先上 后下
            for action, state in self.neighbors(node.state):
                if not frontier.contains_state(state) and state not in self.explored:
                    # state 和 action保存的是子節(jié)點(diǎn)的行動(dòng)和狀態(tài)，而parent保存了父節(jié)點(diǎn)的所有狀態(tài)，比如從起始點(diǎn)到第二個(gè)點(diǎn)，parent保存的就是起始狀態(tài)的所有狀態(tài)
                    child = Node(state=state, parent=node, action=action)

                    frontier.add(child)
class StackFrontier():
    def  __init__(self):
        self.frontier = []
    def add(self, node):
        self.frontier.append(node)

    def contains_state(self, state):
        return any(node.state == state for node in self.frontier)

    def empty(self):
        return len(self.frontier) == 0

    def  remove(self):
        # 堆棧，先進(jìn)后出 深度搜索
        if self.empty():
            raise Exception("empty frontier")
        else:
            # 取列表中最后一個(gè)對(duì)象，并將邊界列表的最后一個(gè)刪除，返回結(jié)果為對(duì)象（對(duì)象中有當(dāng)前節(jié)點(diǎn)、運(yùn)動(dòng)方向和他的父節(jié)點(diǎn)）
            node = self.frontier[-1]
            self.frontier = self.frontier[:-1]
            return node

上述代碼是存在于Maze類當(dāng)中，函數(shù)neighbors是查找當(dāng)前坐標(biāo)點(diǎn)上下左右4個(gè)方向的坐標(biāo)，并判斷是否可以通過，如果可以就保存到result列表當(dāng)中，并返回result列表。

?solve函數(shù)是判斷是否到達(dá)目標(biāo)點(diǎn)的函數(shù)， 可以看程序中的注釋進(jìn)行了解。我們運(yùn)行整體程序后得到一下結(jié)果的路徑圖，我們看圖講解一下過程。

本圖為深度優(yōu)化搜索得到的結(jié)果，如果了解了上面對(duì)程序的解釋，那么我們看后面的內(nèi)容應(yīng)該會(huì)比較容易。

同理紅色代表我們的起始點(diǎn)A，綠色代表我們的目標(biāo)點(diǎn)B，藍(lán)色是我們深度優(yōu)化搜索算法得到的路徑，白色為為探索的路徑。? 我們來講一下程序在這圖片中的路徑搜索過程。

以起始點(diǎn)為例A（6，0），經(jīng)過初始化節(jié)點(diǎn)的Node類保存起始點(diǎn)的坐標(biāo)（起始點(diǎn)無父節(jié)點(diǎn)和行動(dòng)方向），將A點(diǎn)傳入以下程序中尋找可移動(dòng)的方向和節(jié)點(diǎn)

    def neighbors(self, state):
        """
        在調(diào)用這個(gè)函數(shù)的時(shí)候會(huì)傳入當(dāng)前狀態(tài)的坐標(biāo)點(diǎn)。也就是我們?cè)诔绦蛑?        自己定義下一步優(yōu)先走的方向，在candidates列表里面就是上下左右的
        順序進(jìn)行移動(dòng) 以點(diǎn)（0，0）為例，得到的candidates列表就是
        [
        "up",(-1,0),
        "down",(1,0),
        "left",(0,-1),
        "right",(0,1)    
        ]
        得到行動(dòng)列表后開始進(jìn)行循環(huán)判斷，判斷是否超出長(zhǎng)和寬，以及self.wall[r][c]是否為True，
        如果都不滿足就代表可以行動(dòng)，添加到result列表
        """
        row, col = state
        candidates = [
            ("up", (row - 1, col)),
            ("down", (row + 1, col)),
            ("left", (row, col - 1)),
            ("right", (row, col + 1))
        ]

        result = []
        # 保存可以走的方向， 判斷是否在邊界以及是否有墻 self.wall列表中的是bool
        for action, (r, c) in candidates:
            if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
                result.append((action, (r, c)))
        return result

? ? ? ?得到列表結(jié)果為:? [ ("up",(5,0)),( "down",(7,0)),("left",(6,-1)), ("right",(6,1)) ],

將得到的列表再經(jīng)過for循環(huán)判斷是否超出原文本的長(zhǎng)寬，以及是否為墻，如果滿足其中一項(xiàng)就表示該節(jié)點(diǎn)無法通過，比如節(jié)點(diǎn) (“down”,(7,0))超出了我們整體的高度及超出了二維矩陣的索引（高度是從0開始到6結(jié)尾，整體高為7）這個(gè)節(jié)點(diǎn)就不會(huì)被保存進(jìn)result列表中。

因此從A點(diǎn)開始可以通過的節(jié)點(diǎn)為 result = [("up",(5,0)）,("right",(6,1))]。得到的結(jié)果返回到for循環(huán)中，如下程序：

             for action, state in self.neighbors(node.state):
                if not frontier.contains_state(state) and state not in self.explored:
                    # state 和 action保存的是子節(jié)點(diǎn)的行動(dòng)和狀態(tài)，而parent保存了父節(jié)點(diǎn)的所有狀態(tài)，比如從起始點(diǎn)到第二個(gè)點(diǎn)，parent保存的就是起始狀態(tài)的所有狀態(tài)
                    child = Node(state=state, parent=node, action=action)

                    frontier.add(child)

在本段程序中會(huì)將兩個(gè)子節(jié)點(diǎn)保存到Node類中，并將child這個(gè)對(duì)象保存到邊界列表中（邊界列表在StackFrontier類中）。深度優(yōu)先搜索會(huì)在下一次的while循環(huán)中去找StackFrontier類中邊界列表中最后一個(gè)對(duì)象，并賦予變量node，然后重置邊界列表（就是刪除取出來的最后一位對(duì)象）。然后開始重復(fù)上方可行動(dòng)節(jié)點(diǎn)的搜索，找到便保存到邊界列表，沒有就會(huì)在邊界列表中已有的對(duì)象去查找可移動(dòng)節(jié)點(diǎn)。

?2.2.3 回溯

?我們已經(jīng)知道每找到一個(gè)節(jié)點(diǎn)在重新中都會(huì)對(duì)其做一次對(duì)象保存（保存在Node類里），其中保存的內(nèi)容為該節(jié)點(diǎn)的坐標(biāo)和父節(jié)點(diǎn)運(yùn)動(dòng)的該節(jié)點(diǎn)的方向，以及父節(jié)點(diǎn)的對(duì)象。我們看下方程序，就是在while循環(huán)判斷是否存在父節(jié)點(diǎn)，存在的情況下找到當(dāng)前節(jié)點(diǎn)的坐標(biāo)，并將該節(jié)點(diǎn)的父節(jié)點(diǎn)重新賦值給到node變量，直到回溯到我們的起始點(diǎn)節(jié)點(diǎn)。

回溯程序

       # 判罰是否到達(dá)我們的目標(biāo)點(diǎn)  
       if node.state == self.goal:
                actions = []
                cells = []
                # 開是while循環(huán)判斷回溯，判斷我們類里面是否有父節(jié)點(diǎn)（在起始點(diǎn)的時(shí)候我們沒有父節(jié)點(diǎn)的）
                while node.parent is not None:
                    # 將回溯節(jié)點(diǎn)進(jìn)行保存
                    actions.append(node.action)
                    cells.append(node.state)
                    # 重新對(duì)變量node進(jìn)行賦值，得到當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)
                    node = node.parent

起始點(diǎn)的節(jié)點(diǎn)

# 在循環(huán)查找路徑前我們就已經(jīng)將我們的起始點(diǎn)進(jìn)行保存（parent代表我們的父節(jié)點(diǎn)，在這里是None,代表沒有，起到while回溯退出的作用）
start = Node(state=self.start, parent=None, action=None)

?看一看回溯過程

"""
    以起始點(diǎn)和他的一個(gè)子節(jié)點(diǎn)為例
"""

start = Node(state=(6,0),parent=None,action=None)

# parent保存的是節(jié)點(diǎn)對(duì)象
child = Node(state=(6,1),parent=start,action='right')

node = child 

action = []
cells = []

while node.parent is not None:
    action.append(node.action)
    cells.append(node.state)
    node = node.parent  # node.parent = Node(state=(6,0),parent=None,action=None)

?廣度優(yōu)先搜索

我們的廣度優(yōu)先搜索的處理過程和深度優(yōu)先搜索相同，唯一不同的地方是在下方StackFrontier類的remove函數(shù)當(dāng)中，需要更改為取列表的第一位，及索引0

class StackFrontier():
    def  __init__(self):
        self.frontier = []
    def add(self, node):
        self.frontier.append(node)

    def contains_state(self, state):
        return any(node.state == state for node in self.frontier)

    def empty(self):
        return len(self.frontier) == 0

    def  remove(self):
        # 堆棧，先進(jìn)后出 深度搜索
        if self.empty():
            raise Exception("empty frontier")
        else:
            # 取列表中最后一個(gè)對(duì)象，并將邊界列表的最后一個(gè)刪除，返回結(jié)果為對(duì)象（對(duì)象中有當(dāng)前節(jié)點(diǎn)、運(yùn)動(dòng)方向和他的父節(jié)點(diǎn)）
            node = self.frontier[-1]
            self.frontier = self.frontier[:-1]
            return node

函數(shù)更改，將上方remove函數(shù)改為以下代碼：

    def remove(self):
        if self.empty():
            raise Exception("empty frontier")
        else:
            # 這里取了邊界列表的第一位
            node = self.frontier[0]
            print(node)
            # 這里刪除了邊界列表的第一位
            self.frontier = self.frontier[1:]
            return node

?在尋找節(jié)點(diǎn)的時(shí)候和深度搜索相同，只是按照所有節(jié)點(diǎn)進(jìn)入邊界列表的順序來進(jìn)行下一步的行動(dòng)。

下圖是廣度優(yōu)先搜索得出的結(jié)果圖：

?粉紅色為探索過的路徑

?總結(jié)

寫完感覺整篇文章的邏輯和內(nèi)容有點(diǎn)混亂，本人對(duì)兩者算法的理解也有限，可能存在理解錯(cuò)誤的地方，如果導(dǎo)致您感到困惑地方還望理解。

完整代碼如下

##############################
#Maze.py
#Introdution:
#IDE:
#From
#By:qin,2023....
##############################

import sys
import matplotlib.pyplot as plt


#類：
class Node():
    def __init__(self, state, parent, action):
        self.state = state
        self.parent = parent
        self.action = action


class StackFrontier():
    def  __init__(self):
        self.frontier = []
    def add(self, node):
        self.frontier.append(node)

    def contains_state(self, state):
        return any(node.state == state for node in self.frontier)

    def empty(self):
        return len(self.frontier) == 0

    # def  remove(self):
    #     # 堆棧，先進(jìn)后出 深度搜索
    #     if self.empty():
    #         raise Exception("empty frontier")
    #     else:
    #         node = self.frontier[-1]
    #         self.frontier = self.frontier[:-1]
    #         return node
    def remove(self):
        if self.empty():
            raise Exception("empty frontier")
        else:
            node = self.frontier[0]
            print(node)
            self.frontier = self.frontier[1:]
            return node


class QueueFrontier(StackFrontier):
    # 隊(duì)列 先進(jìn)先出，進(jìn)行廣度搜索
    def remove(self):
        if self.empty():
            raise Exception("empty frontier")
        else:
            node = self.frontier[0]
            print(node)
            self.frontier = self.frontier[1:]
            return node

class Maze():

    def __init__(self, filename):

        # Read file and set height and width of maze
        """
        初始化操作，找到文件中的起點(diǎn)a和終點(diǎn)b是否存在
        存在進(jìn)行行列的遍歷，找到A,B在文本中的坐標(biāo)點(diǎn)
        :param filename:

        """
        with open(filename) as f:
            contents = f.read()

        # Validate start and goal
        if contents.count("A") != 1:
            raise Exception("maze must have exactly one start point")
        if contents.count("B") != 1:
            raise Exception("maze must have exactly one goal")

        # Determine height and width of maze
        contents = contents.splitlines()
        self.height = len(contents)
        self.width = max(len(line) for line in contents)

        # Keep track of walls
        self.walls = []
        for i in range(self.height):
            row = []
            for j in range(self.width):
                try:
                    if contents[i][j] == "A":
                        self.start = (i, j)
                        row.append(False)
                    elif contents[i][j] == "B":
                        self.goal = (i, j)
                        row.append(False)
                    elif contents[i][j] == " ":
                        row.append(False)
                    else:
                        row.append(True)
                except IndexError:
                    row.append(False)
            self.walls.append(row)

        self.solution = None


    def print(self):
        solution = self.solution[1] if self.solution is not None else None
        print()
        for i, row in enumerate(self.walls):
            for j, col in enumerate(row):
                if col:
                    print("█", end="")
                elif (i, j) == self.start:
                    print("A", end="")
                elif (i, j) == self.goal:
                    print("B", end="")
                elif solution is not None and (i, j) in solution:
                    print("*", end="")
                else:
                    print(" ", end="")
            print()
        print()


    def neighbors(self, state):
        row, col = state
        candidates = [
            ("up", (row - 1, col)),
            ("down", (row + 1, col)),
            ("left", (row, col - 1)),
            ("right", (row, col + 1))
        ]

        result = []
        # 保存可以走的方向， 判斷是否在邊界以及是否有墻 self.wall列表中的是bool
        for action, (r, c) in candidates:
            if 0 <= r < self.height and 0 <= c < self.width and not self.walls[r][c]:
                result.append((action, (r, c)))
        return result


    def solve(self):
        """Finds a solution to maze, if one exists."""

        # Keep track of number of states explored
        self.num_explored = 0

        # Initialize frontier to just the starting position
        start = Node(state=self.start, parent=None, action=None)
        print("起始點(diǎn)的坐標(biāo)",start.state)
        frontier = StackFrontier()
        frontier.add(start)

        # Initialize an empty explored set
        self.explored = set()

        # Keep looping until solution found
        while True:
            # If nothing left in frontier, then no path
            if frontier.empty():
                raise Exception("no solution")

            # Choose a node from the frontier
            r = QueueFrontier()
            node = frontier.remove()
            self.num_explored += 1

            # If node is the goal, then we have a solution
            if node.state == self.goal:
                actions = []
                cells = []
                while node.parent is not None:
                    actions.append(node.action)
                    cells.append(node.state)
                    node = node.parent
                print(cells)
                actions.reverse()
                cells.reverse()
                self.solution = (actions, cells)
                return

            # Mark node as explored
            self.explored.add(node.state)

            # Add neighbors to frontier 返回的執(zhí)行列表是 先上 后下
            for action, state in self.neighbors(node.state):
                if not frontier.contains_state(state) and state not in self.explored:
                    # state 和 action保存的是子節(jié)點(diǎn)的行動(dòng)和狀態(tài)，而parent保存了父節(jié)點(diǎn)的所有狀態(tài)，比如從起始點(diǎn)到第二個(gè)點(diǎn)，parent保存的就是起始狀態(tài)的所有狀態(tài)
                    child = Node(state=state, parent=node, action=action)

                    frontier.add(child)


    def output_image(self, filename, show_solution=True, show_explored=False):
        from PIL import Image, ImageDraw
        cell_size = 50
        cell_border = 2
        # 創(chuàng)建圖像畫布，將start 、goal、wall和路徑用不同的像素表示
        # Create a blank canvas
        img = Image.new(
            "RGBA",
            (self.width * cell_size, self.height * cell_size),
            "black"
        )
        draw = ImageDraw.Draw(img)

        solution = self.solution[1] if self.solution is not None else None
        for i, row in enumerate(self.walls):
            for j, col in enumerate(row):
                # plt.clf()

                # Walls
                if col:
                    fill = (40, 40, 40)

                # Start
                elif (i, j) == self.start:
                    fill = (255, 0, 0)
                    # plt.imshow(img)
                    # plt.pause(0.4)

                # Goal
                elif (i, j) == self.goal:
                    fill = (0, 171, 28)

                # Solution
                elif solution is not None and show_solution and (i, j) in solution:
                    fill = (120, 200, 252)
                    # plt.imshow(img)
                    # plt.pause(0.4)

                # Explored
                elif solution is not None and show_explored and (i, j) in self.explored:
                    fill = (255, 100, 120)

                # Empty cell
                else:
                    fill = (237, 255, 252)

                # Draw cell
                draw.rectangle(
                    ([(j * cell_size + cell_border, i * cell_size + cell_border),
                      ((j + 1) * cell_size - cell_border, (i + 1) * cell_size - cell_border)]),
                    fill=fill
                )
                # plt.imshow(img)
                # plt.pause(0.4)
        # plt.ioff()
        # plt.show()
        img.save(filename)

# for i in range(4):
#     sys.argv.append(f"./maze{i+1}.txt")
# 
# 
# if len(sys.argv) < 2:
#     sys.exit("Usage: python maze.py maze.txt1")
# 
# 
# print((sys.argv))


# path = sys.argv[j+1]
m = Maze('./maze1.txt')
print("Maze:")
m.print()
print("Solving...")
m.solve()
print("States Explored:", m.num_explored)
print("Solution:")
m.print()
m.output_image(f"maze.png", show_explored=True)

上述代碼非本人編寫，僅用于講述與教學(xué)文章來源地址http://www.zghlxwxcb.cn/news/detail-848881.html

到了這里，關(guān)于深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索(BFS)，用代碼講原理的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！