一、理解廣度優(yōu)先算法

我們要實(shí)現(xiàn)的是廣度優(yōu)先算法走迷宮

比如,我們有一個(gè)下面這樣的迷宮

這個(gè)迷宮是6行5列

其中0代表可以走的路, 1代表一堵墻. 我們把墻標(biāo)上言責(zé), 就如右圖所示. 其中(0,0)是起點(diǎn), (6, 5)是終點(diǎn).

我們要做的是, 從起點(diǎn)走到終點(diǎn)最近的路徑.

這個(gè)例子是拋轉(zhuǎn)隱喻, 介紹廣度優(yōu)先算法, 廣度優(yōu)先算法的應(yīng)用很廣泛, 所以, 先來(lái)看看規(guī)律

1.1、分析如何進(jìn)行廣度優(yōu)先探索

第一步, 我們先明確起點(diǎn). 這個(gè)起點(diǎn)有上下左右四個(gè)方向可以探索. 我們按照順時(shí)針順序探索, 上 左 下 右

第二步: 起始位置向外探索, 有4個(gè)方向.

如上圖紅色標(biāo)出的位置. 也就是起始位置可以向外探索的路徑有4個(gè). 上 左 下 右

我們?cè)賮?lái)繼續(xù)探索.

第三步: 再次明確探索方向是 上 左 下 右

第四步: 探索上方的紅1, 上方的紅1可以向外探索的路徑有3個(gè)

第五步: 探索左側(cè)紅1, 左側(cè)紅1 有兩條路徑向外探索,

為什么是兩個(gè)呢? 本來(lái)是有3個(gè), 但上面的路徑已經(jīng)被上面的紅1探索過(guò)了, 所以, 不重復(fù)探索的原則, 左側(cè)紅1 向外擴(kuò)展的路徑有2條

第六步: 下面的紅1 向外探索的路徑有2條

第七步: 右側(cè)的紅1向外探索的路徑, 如上圖可見, 只剩下1條了

第二輪探索, 得到的探索結(jié)果是:

經(jīng)過(guò)第二輪探索, 一共探索出了8條路徑, 也就是8個(gè)黑2

接下來(lái)進(jìn)行第三輪探索. 順序依然是順時(shí)針方向,

1. 第一個(gè)2向外探索的路徑有3條

2. 第二個(gè)黑2向外探索的路徑只有1條

3. 第三個(gè)黑2向外探索的路徑有2條

4. 第四個(gè)黑2向外探索的路徑有1條

5. 第五個(gè)黑2 向外探索的路徑有兩條

6. 第六個(gè)黑2向外探索的路徑有1條

7. 第七個(gè)黑2向外探索的路徑有兩條

8. 第8個(gè)黑2向外探索的路徑為0條. 已經(jīng)沒有路徑. 所以不再向外探索

通過(guò)第三輪向外探索, 我們探索出來(lái)了12條路徑.

這是有的節(jié)點(diǎn)可以向外探索3條路徑,有的可以向外探索2條路徑, 有的向外探索1條路徑, 有的沒有路徑可以向外探索了.

總結(jié)：

通過(guò)上面的例子, 我們可以看到每個(gè)節(jié)點(diǎn)的3中狀態(tài). 我們來(lái)分析一下, 有哪三種狀態(tài).

剛開始, 只有一個(gè)其實(shí)位置0. 這個(gè)0是已知的, 還沒有開始向外探索. 外面還有好多等待探索的節(jié)點(diǎn).所以,此時(shí)的0, 是已經(jīng)發(fā)現(xiàn)還未探索的節(jié)點(diǎn)

當(dāng)0開始向外探索, 探索到4個(gè)1, 這時(shí)候0就變成了已經(jīng)發(fā)現(xiàn)且已經(jīng)探索的節(jié)點(diǎn). 二1變成了一經(jīng)發(fā)現(xiàn)還未探索的節(jié)點(diǎn). 其實(shí)此時(shí)外面還有3, 4, 5 這些還未被發(fā)現(xiàn)未被探索的節(jié)點(diǎn).

我們通過(guò)分析, 廣度優(yōu)先算法還有一個(gè)特點(diǎn), 那就是循環(huán)遍歷, 第一輪的紅1都探索完了, 在進(jìn)行黑2的探索, 不會(huì)說(shuō)紅1探索出來(lái)一個(gè), 還沒有全部完成,就繼續(xù)向外探索.

總結(jié)規(guī)律如下:

1. 節(jié)點(diǎn)有三種狀態(tài)

• a. 已經(jīng)發(fā)現(xiàn)還未探索的節(jié)點(diǎn)
• b. 已經(jīng)發(fā)現(xiàn)并且已經(jīng)探索的節(jié)點(diǎn)
• c. 還未發(fā)現(xiàn)且未探索的節(jié)點(diǎn)

2. 階段探索的順序

按照每一輪全部探索完,在探索下一輪, 這樣就形成了一個(gè)隊(duì)列, 我們把已經(jīng)發(fā)現(xiàn)還未探索的節(jié)點(diǎn)放到隊(duì)列里

接下來(lái)我們開始探索了.

首先, 我們知道迷宮的起始位置, (0,0)點(diǎn). 當(dāng)前我們站在起始位置(0,0), 那么這個(gè)起點(diǎn)就是已經(jīng)發(fā)現(xiàn)還未探索的節(jié)點(diǎn).

我們定義一個(gè)隊(duì)列來(lái)存放已經(jīng)發(fā)現(xiàn)但還未探索的節(jié)點(diǎn)

第二步: 從隊(duì)列中取出節(jié)點(diǎn)(0,0), 開始下一步探索.我們看看迷宮最終的樣子

我們看到(0,0)只能向下走, 他的右邊是一堵墻, 走不了. 上面,左面也不能走. 所以, 探索出來(lái)的路徑只有一個(gè)(1,0), 吧(1,0)放入到隊(duì)列中

第三步: 我們?cè)趶年?duì)列中把(1,0)取出來(lái)進(jìn)行探索, 這時(shí)隊(duì)列就空了.

對(duì)照迷宮, (1,0)可以向下走, 可以向右走. 不能向上和向左. 因此, (1,0)探索出來(lái)兩條路, (2,0) 和(1,1), 把這兩個(gè)點(diǎn)放入到隊(duì)列中

第四步: 接下來(lái)我們來(lái)探索(2,0)這個(gè)點(diǎn), 對(duì)照迷宮, 我沒發(fā)現(xiàn)(2,0)這個(gè)點(diǎn)下和右都是墻, 左不能走, 上就走回去了也不可以. 所以, (2,0)是個(gè)死路, 探索出來(lái)的路徑是0

第五步: 繼續(xù)探索(1,1), 對(duì)照迷宮, (1,1)只能向右探索到(1,2) , 因此我們把(1,2)放入隊(duì)列中

第六步:對(duì)(1,2)繼續(xù)探索, 發(fā)現(xiàn)有兩條路徑可以走(2,2)和(0,2), 然后, 將這兩個(gè)點(diǎn)放到隊(duì)列中

第七步: 接下來(lái)繼續(xù)這樣探索下去, 一直走一直走, 走到最后就是這樣的

那我們要怎么來(lái)判斷路徑呢? 倒過(guò)來(lái)走, 從13開始, 上一個(gè)數(shù)12, 只有一個(gè), 12上面只有一個(gè)數(shù)是11, 只有一個(gè), 一次類推, 一直找到1, 找到0.

第八步: 廣度優(yōu)先算法, 什么時(shí)候結(jié)束呢? 兩種情況

• 第一種: 走到最后13的位置
• 第二種: 死路, 走到一個(gè)位置, 不能再走了. 如何判斷呢?隊(duì)列中沒有可探索的點(diǎn)了, 探索結(jié)束

1.2、我們來(lái)總結(jié)一下

1. 從(0,0)點(diǎn)開始, 將已經(jīng)發(fā)現(xiàn)還未探索的點(diǎn), 放入到隊(duì)列中.

2. 從隊(duì)列中取出已經(jīng)發(fā)現(xiàn)還未探索的節(jié)點(diǎn), 進(jìn)行探索, 探索的方式是, 像四周探索, 然后把新發(fā)現(xiàn)還未探索的節(jié)點(diǎn)從隊(duì)列中取出來(lái).

3. 如何判斷呢? 如果當(dāng)前是一堵墻, 也就是他的value=0, 那么探索失敗. 向左探索的時(shí)候, 如果左邊是(0,*)探索失敗. 向上探索的時(shí)候, 如果上面是(*,0)探索失敗; 像右面探索的時(shí)候, 碰到邊(*,4)探索失敗. 向下探索, 碰到(5,*)探索失敗. 也就是, 橫向坐標(biāo)的范圍是 0<=x<=4, 縱坐標(biāo)是 0<=y<=5

4. 已經(jīng)探索過(guò)的節(jié)點(diǎn)不要重復(fù)探索

1.3、代碼分析

1. 隊(duì)列可以用一個(gè)數(shù)組來(lái)實(shí)現(xiàn). 先進(jìn)先出

2. 點(diǎn)用二維數(shù)據(jù)來(lái)表示. 但是go中的二維數(shù)組的含義是一位數(shù)組里的值又是一個(gè)數(shù)組.比如[][]int, 他是一個(gè)一維數(shù)組[]int, 里面的值又是一個(gè)一維數(shù)組.[]int.

那么用在這里就是, 縱坐標(biāo)表示有6行, 那么他是一個(gè)[6]int, 橫坐標(biāo)表示每行里面又是一個(gè)數(shù)組, 每行有6個(gè)元素[5]int, 所以, 這就是一個(gè)[6][5]int 有6行5列的數(shù)組.

二、代碼實(shí)現(xiàn)廣度優(yōu)先算法走迷宮

第一步: step代表從start開始, 走了多少步走到目標(biāo)點(diǎn), 最后的路徑是通過(guò)這個(gè)創(chuàng)建出來(lái)的, 最后從后往前推就可以算出最短路徑

第二步: 定義一個(gè)隊(duì)列, 用來(lái)保存已經(jīng)發(fā)現(xiàn)還未探索的點(diǎn), 隊(duì)列里的初始值是(0,0)點(diǎn)

第三步: 開始走迷宮, 走迷宮退出的條件有兩個(gè)

     1. 走到終點(diǎn), 退出

     2. 隊(duì)列中沒有元素, 退出

第四步:  判斷坐標(biāo)是否符合探索的要求

         1. maze at next is 0

         2. and setp at next is 0, 如果step的值不是0 ,說(shuō)明曾經(jīng)到過(guò)這個(gè)點(diǎn)了, 不能重復(fù)走

         3. next != start 處理特殊點(diǎn), (0,0)點(diǎn)

第五步: 已經(jīng)找到這個(gè)點(diǎn)了, 計(jì)算當(dāng)前的步數(shù), 并加入隊(duì)列中

package main

import (
    "fmt"
    "os"
)

func readFile(filename string) [][]int{
    // 定義一個(gè)行和列,用來(lái)接收迷宮是幾行幾列的數(shù)組
    var row, col int
    file, e := os.Open(filename)
    if e != nil {
        panic("error")
    }
    defer file.Close()

    fmt.Fscan(file, &row, &col)

    // 定義一個(gè)數(shù)組
    // 注意: 定義數(shù)組的時(shí)候, 我們只要傳入幾行就可以了.
    // 二維數(shù)組的含義, 其實(shí)質(zhì)是一個(gè)一維數(shù)組, 一維數(shù)組里每一個(gè)元素又是一個(gè)數(shù)組
    maze := make([][]int, row)
    for i := 0; i < len(maze); i++ {
        maze[i] = make([]int, col)
        for j := 0; j < len(maze[i]); j++ {
            fmt.Fscan(file, &maze[i][j])
        }
    }

    return maze
}

type point struct {
    i, j int
}

// 當(dāng)前節(jié)點(diǎn), 向四個(gè)方向探索后的節(jié)點(diǎn)
// 這里使用的是返回新的節(jié)點(diǎn)的方式, 不修改原來(lái)的節(jié)點(diǎn). 所以使用的是值拷貝,而不是傳地址
func (p point) add(dir point) point{
    return point{p.i + dir.i, p.j + dir.j }
}

// 獲取某個(gè)點(diǎn)的坐標(biāo)值
// 同時(shí)判斷這個(gè)點(diǎn)有沒有越界, 返回的是這個(gè)值是否有效
// return 第一個(gè)參數(shù)表示返回的值是否是1, 是1表示撞墻了
//        第二個(gè)參數(shù)表示返回的值是否不越界, 不越界返回true, 越界,返回false 就和你
func (p point) at(grid [][]int) (int, bool) {
    if p.i < 0 || p.i >= len(grid) {
        return 0, false
    }

    if p.j <0 || p.j >= len(grid[0]) {
        return 0, false
    }
    return grid[p.i][p.j], true
}

// 定義要探索的方向, 上下左右四個(gè)方向
var dirs = []point {
    point{-1, 0},
    point{0, -1},
    point{1, 0},
    point{0, 1},
}

// 走迷宮
func walk(maze [][]int, start, end point) [][]int {
    // 第一步: step代表從start開始, 走了多少步走到目標(biāo)點(diǎn), 最后的路徑是通過(guò)這個(gè)創(chuàng)建出來(lái)的, 最后從后往前推就可以算出最短路徑
    // 2. 通step還可以知道哪些點(diǎn)是到過(guò)的, 哪些點(diǎn)是沒到過(guò)的
    step := make([][]int, len(maze))
    for i := range step {
        // 定義每一行有多少列, 這樣就定義了一個(gè)和迷宮一樣的二維數(shù)組
        step[i] = make([]int, len(maze[i]))
    }

    // 第二步: 定義一個(gè)隊(duì)列, 用來(lái)保存已經(jīng)發(fā)現(xiàn)還未探索的點(diǎn), 隊(duì)列里的初始值是(0,0)點(diǎn)
    Que := []point{start}

    // 第三步: 開始走迷宮, 走迷宮退出的條件有兩個(gè)
    // 1. 走到終點(diǎn), 退出
    // 2. 隊(duì)列中沒有元素, 退出
    for len(Que) > 0 {
        // 開始探索, 依次取出隊(duì)列中, 已經(jīng)發(fā)現(xiàn)還未探索的元素
        // cur 表示當(dāng)前要探索的節(jié)點(diǎn)
        cur := Que[0]
        // 然后從頭拿掉第一個(gè)元素
        Que = Que[1:]

        // 如果這個(gè)點(diǎn)是終點(diǎn), 就不向下探索了
        if cur == end {
            break
        }

        // 當(dāng)前節(jié)點(diǎn)怎么探索呢? 要往上下左右四個(gè)方向去探索
        for _, dir := range dirs {
            // 探索下一個(gè)節(jié)點(diǎn), 這里獲取下一個(gè)節(jié)點(diǎn)的坐標(biāo). 當(dāng)前節(jié)點(diǎn)+方向
            next := cur.add(dir)
            // 判斷坐標(biāo)是否符合探索的要求
            // 1. maze at next is 0
            // 2. and setp at next is 0, 如果step的值不是0 ,說(shuō)明曾經(jīng)到過(guò)這個(gè)點(diǎn)了, 不能重復(fù)走
            // 3. next != start 處理特殊點(diǎn), (0,0)點(diǎn)

            // 探索這個(gè)點(diǎn)是否是墻
            val, ok := next.at(maze)
            if !ok || val == 1 {
                continue
            }

            // 探索這個(gè)點(diǎn)是否已經(jīng)走過(guò)
            val, ok = next.at(step)
            if val != 0 || !ok {
                continue
            }

            // 走到起始點(diǎn)了, 返回
            if next == start {
                continue
            }

            // 已經(jīng)找到這個(gè)點(diǎn)了, 計(jì)算當(dāng)前的步數(shù)
            curval, _ := cur.at(step) // 當(dāng)前這一步的步數(shù)
            step[next.i][next.j] = curval + 1 // 下一步是當(dāng)前步數(shù)+1
            Que = append(Que, next) // 將下一步節(jié)點(diǎn)放入到隊(duì)列中
        }

    }
    return step
}

func main() {

    maze := readFile("maze/maze.in")

    steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
    // len(maze)-1, len[maze[0]]-1 是終點(diǎn)
    // 0,0是起始點(diǎn)
    for _, row := range steps {
        for _, val := range row  {
            fmt.Printf("%3d", val)
        }
        fmt.Println()
    }
}

以上就是詳解Go語(yǔ)言運(yùn)用廣度優(yōu)先搜索走迷宮的詳細(xì)內(nèi)容，更多關(guān)于Go 廣度優(yōu)先搜索走迷宮的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論