A*（A星）算法Go lang实现

作者: Golang语言社区 | 来源:发表于2019-03-29 13:32 被阅读1次

A*（A星）算法Go lang实现
Gogs部署
go算法实现
仿 common-lang 包的 go 语言工具库
[golang] Blowfish算法的go实现
go每日一库 [go-rate] 速率限制器
go实现LFU算法
go 实现LRU算法
go rate
go lang 环境配置

A算法，A（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。
A* （A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。
公式表示为： f(n)=g(n)+h(n),
其中， f(n) 是从初始状态经由状态n到目标状态的代价估计，
g(n) 是在状态空间中从初始状态到状态n的实际代价，
h(n) 是从状态n到目标状态的最佳路径的估计代价。
（对于路径搜索问题，状态就是图中的节点，代价就是距离）
h(n)的选取
保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取（或者说h(n)的选取）。
我们以d(n)表达状态n到目标状态的距离，那么h(n)的选取大致有如下三种情况：

如果h(n)< d(n)到目标状态的实际距离，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行，此时的搜索效率是最高的。
如果 h(n)>d(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

A*同样可以用于其他搜索问题，只需要对应状态和状态的距离即可。

package main

import (
        "container/heap"
        "fmt"
        "math"
        "strings"
)
import "strconv"

type OpenList []*_AstarPoint

func (self OpenList) Len() int           { return len(self) }
func (self OpenList) Less(i, j int) bool { return self[i].fVal < self[j].fVal }
func (self OpenList) Swap(i, j int)      { self[i], self[j] = self[j], self[i] }

func (this *OpenList) Push(x interface{}) {
        // Push and Pop use pointer receivers because they modify the slice's length,
        // not just its contents.
        *this = append(*this, x.(*_AstarPoint))
}

func (this *OpenList) Pop() interface{} {
        old := *this
        n := len(old)
        x := old[n-1]
        *this = old[0 : n-1]
        return x
}


type _Point struct {
        x    int
        y    int
        view string
}

//========================================================================================

// 保存地图的基本信息
type Map struct {
        points [][]_Point
        blocks map[string]*_Point
        maxX   int
        maxY   int
}

func NewMap(charMap []string) (m Map) {
        m.points = make([][]_Point, len(charMap))
        m.blocks = make(map[string]*_Point, len(charMap)*2)
        for x, row := range charMap {
                cols := strings.Split(row, " ")
                m.points[x] = make([]_Point, len(cols))
                for y, view := range cols {
                        m.points[x][y] = _Point{x, y, view}
                        if view == "X" {
                                m.blocks[pointAsKey(x, y)] = &m.points[x][y]
                        }
                } // end of cols
        } // end of row

        m.maxX = len(m.points)
        m.maxY = len(m.points[0])

        return m
}

func (this *Map) getAdjacentPoint(curPoint *_Point) (adjacents []*_Point) {
        if x, y := curPoint.x, curPoint.y-1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
                adjacents = append(adjacents, &this.points[x][y])
        }
        if x, y := curPoint.x+1, curPoint.y-1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
                adjacents = append(adjacents, &this.points[x][y])
        }
        if x, y := curPoint.x+1, curPoint.y; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
                adjacents = append(adjacents, &this.points[x][y])
        }
        if x, y := curPoint.x+1, curPoint.y+1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
                adjacents = append(adjacents, &this.points[x][y])
        }
        if x, y := curPoint.x, curPoint.y+1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
                adjacents = append(adjacents, &this.points[x][y])
        }
        if x, y := curPoint.x-1, curPoint.y+1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
                adjacents = append(adjacents, &this.points[x][y])
        }
        if x, y := curPoint.x-1, curPoint.y; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
                adjacents = append(adjacents, &this.points[x][y])
        }
        if x, y := curPoint.x-1, curPoint.y-1; x >= 0 && x < this.maxX && y >= 0 && y < this.maxY {
                adjacents = append(adjacents, &this.points[x][y])
        }
        return adjacents
}

func (this *Map) PrintMap(path *SearchRoad) {
        fmt.Println("map's border:", this.maxX, this.maxY)
        for x := 0; x < this.maxX; x++ {
                for y := 0; y < this.maxY; y++ {
                        if path != nil {
                                if x == path.start.x && y == path.start.y {
                                        fmt.Print("S")
                                        goto NEXT
                                }
                                if x == path.end.x && y == path.end.y {
                                        fmt.Print("E")
                                        goto NEXT
                                }
                                for i := 0; i < len(path.TheRoad); i++ {
                                        if path.TheRoad[i].x == x && path.TheRoad[i].y == y {
                                                fmt.Print("*")
                                                goto NEXT
                                        }
                                }
                        }
                        fmt.Print(this.points[x][y].view)
                NEXT:
                }
                fmt.Println()
        }
}

func pointAsKey(x, y int) (key string) {
        key = strconv.Itoa(x) + "," + strconv.Itoa(y)
        return key
}

//========================================================================================

type _AstarPoint struct {
        _Point
        father *_AstarPoint
        gVal   int
        hVal   int
        fVal   int
}

func NewAstarPoint(p *_Point, father *_AstarPoint, end *_AstarPoint) (ap *_AstarPoint) {
        ap = &_AstarPoint{*p, father, 0, 0, 0}
        if end != nil {
                ap.calcFVal(end)
        }
        return ap
}

func (this *_AstarPoint) calcGVal() int {
        if this.father != nil {
                deltaX := math.Abs(float64(this.father.x - this.x))
                deltaY := math.Abs(float64(this.father.y - this.y))
                if deltaX == 1 && deltaY == 0 {
                        this.gVal = this.father.gVal + 10
                } else if deltaX == 0 && deltaY == 1 {
                        this.gVal = this.father.gVal + 10
                } else if deltaX == 1 && deltaY == 1 {
                        this.gVal = this.father.gVal + 14
                } else {
                        panic("father point is invalid!")
                }
        }
        return this.gVal
}

func (this *_AstarPoint) calcHVal(end *_AstarPoint) int {
        this.hVal = int(math.Abs(float64(end.x-this.x)) + math.Abs(float64(end.y-this.y)))
        return this.hVal
}

func (this *_AstarPoint) calcFVal(end *_AstarPoint) int {
        this.fVal = this.calcGVal() + this.calcHVal(end)
        return this.fVal
}

//========================================================================================

type SearchRoad struct {
        theMap  *Map
        start   _AstarPoint
        end     _AstarPoint
        closeLi map[string]*_AstarPoint
        openLi  OpenList
        openSet map[string]*_AstarPoint
        TheRoad []*_AstarPoint
}

func NewSearchRoad(startx, starty, endx, endy int, m *Map) *SearchRoad {
        sr := &SearchRoad{}
        sr.theMap = m
        sr.start = *NewAstarPoint(&_Point{startx, starty, "S"}, nil, nil)
        sr.end = *NewAstarPoint(&_Point{endx, endy, "E"}, nil, nil)
        sr.TheRoad = make([]*_AstarPoint, 0)
        sr.openSet = make(map[string]*_AstarPoint, m.maxX+m.maxY)
        sr.closeLi = make(map[string]*_AstarPoint, m.maxX+m.maxY)

        heap.Init(&sr.openLi)
        heap.Push(&sr.openLi, &sr.start) // 首先把起点加入开放列表
        sr.openSet[pointAsKey(sr.start.x, sr.start.y)] = &sr.start
        // 将障碍点放入关闭列表
        for k, v := range m.blocks {
                sr.closeLi[k] = NewAstarPoint(v, nil, nil)
        }

        return sr
}

func (this *SearchRoad) FindoutRoad() bool {
        for len(this.openLi) > 0 {
                // 将节点从开放列表移到关闭列表当中。
                x := heap.Pop(&this.openLi)
                curPoint := x.(*_AstarPoint)
                delete(this.openSet, pointAsKey(curPoint.x, curPoint.y))
                this.closeLi[pointAsKey(curPoint.x, curPoint.y)] = curPoint

                //fmt.Println("curPoint :", curPoint.x, curPoint.y)
                adjacs := this.theMap.getAdjacentPoint(&curPoint._Point)
                for _, p := range adjacs {
                        //fmt.Println("\t adjact :", p.x, p.y)
                        theAP := NewAstarPoint(p, curPoint, &this.end)
                        if pointAsKey(theAP.x, theAP.y) == pointAsKey(this.end.x, this.end.y) {
                                // 找出路径了, 标记路径
                                for theAP.father != nil {
                                        this.TheRoad = append(this.TheRoad, theAP)
                                        theAP.view = "*"
                                        theAP = theAP.father
                                }
                                return true
                        }

                        _, ok := this.closeLi[pointAsKey(p.x, p.y)]
                        if ok {
                                continue
                        }

                        existAP, ok := this.openSet[pointAsKey(p.x, p.y)]
                        if !ok {
                                heap.Push(&this.openLi, theAP)
                                this.openSet[pointAsKey(theAP.x, theAP.y)] = theAP
                        } else {
                                oldGVal, oldFather := existAP.gVal, existAP.father
                                existAP.father = curPoint
                                existAP.calcGVal()
                                // 如果新的节点的G值还不如老的节点就恢复老的节点
                                if existAP.gVal > oldGVal {
                                        // restore father
                                        existAP.father = oldFather
                                        existAP.gVal = oldGVal
                                }
                        }

                }
        }

        return false
}

//========================================================================================

func main() {
        presetMap := []string{
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                "X . X X X X X X X X X X X X X X X X X X X X X X X X X",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                "X X X X X X X X X X X X X X X X X X X X X X X X . X X",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
                ". . . . . . . . . . . . . . . . . . . . . . . . . . .",
        }
        m := NewMap(presetMap)
        m.PrintMap(nil)

        searchRoad := NewSearchRoad(0, 0, 18, 10, &m)
        if searchRoad.FindoutRoad() {
                fmt.Println("找到了， 你看！")
                m.PrintMap(searchRoad)
        } else {
                fmt.Println("找不到路径！")
        }
}

原文地址：http://www.byteedu.com/forum.php?mod=viewthread&tid=436&page=1&extra=#pid552

A*（A星）算法Go lang实现
A算法，A（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算...
Gogs部署
1 go lang安装配置 1.1 centos go lang install yum install merc...
go算法实现
1.简易的桶排序 2.冒泡排序 3.求整数二进制表示中1的个数
仿 common-lang 包的 go 语言工具库
common-lang-in-go https://github.com/sjsdfg/common-lang-i...
[golang] Blowfish算法的go实现
最近由于工作的需要，需要的实现一个go的Blowfish算法。其实go本身有一个加密算法库crypto，其中有Bl...
go每日一库 [go-rate] 速率限制器
go-rate是速率限制器库,基于 Token Bucket(令牌桶)算法实现。 go-rate被用在LangTr...
go实现LFU算法
go 实现LRU算法
本文转载自：动手写分布式缓存 - GeeCache第一天 LRU 缓存淘汰策略[https://geektutu....
go rate
在go中的使用 Go提供了一个package(golang.org/x/time/rate)，采用令牌桶的算法实现...
go lang 环境配置
原文地址 go lang环境配置 Go下载地址：https://golang.google.cn/dl/ vsco...