溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
本篇內(nèi)容主要講解“golang之如何使用圖的最短路徑 A*(A-Star)算法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習“golang之如何使用圖的最短路徑 A*(A-Star)算法”吧!
A*（A-Star）算法也是一種在圖中求解最短路徑問題的算法， 由狄克斯特拉算法發(fā)展而來。 A*算法不僅會考慮從起點到候補頂點的距離， 還會考慮從當前所在頂點到終點的估算距離。 距離估算值越接近當前頂點到終點的實際值， A*算法的搜索效率也就越高. 當距離估算值小于實際距離時， 是一定可以得到正確答案的. A*算法在游戲編程中經(jīng)常被用于計算敵人追趕玩家時的行動路線等. 摘自 <<我的第一本算法書>> 【日】石田保輝；宮崎修一
如下圖, 某游戲中, 地圖是網(wǎng)格狀的, 我方在S點, 敵人在G點, 空白區(qū)域是湖泊/樹林等不可到達區(qū)域: 
現(xiàn)在需要追擊敵人, 因此需要計算S點到G點的最短行進路線. A*算法是以狄克斯特拉算法為基礎(chǔ), 區(qū)別是在計算候選節(jié)點的權(quán)重時, 需要同時考慮測量權(quán)重和估算權(quán)重. 此場景中, 使用S點到G點坐標的直線距離作為估算權(quán)重. 估算權(quán)重的作用就像牽引風箏的繩子, 使得每次選取的候選節(jié)點, 盡量是靠往終點方向. 
給定若干頂點, 以及頂點間的若干條邊, 尋找從指定起點srcNode到指定終點dstNode的最小權(quán)重路徑
設(shè)定srcNode的權(quán)重為0, 其他頂點的權(quán)重為無窮大
計算所有節(jié)點到dstNode節(jié)點的估算距離, 以x,y坐標的直線距離作為估算值
節(jié)點.總權(quán)重 = 節(jié)點.測量權(quán)重 + 節(jié)點.估算權(quán)重
將srcNode節(jié)點送入候選堆
for 候選堆不為空:
從候選堆pop頂點node, node是總權(quán)重最小的候選節(jié)點
如果node.id == dstNode.id, 循環(huán)結(jié)束
遍歷從node出發(fā)的所有邊, 將邊的終點to的測量權(quán)重, 更新為min(to.測量權(quán)重, node.測量權(quán)重+邊.權(quán)重)
如果to.測量權(quán)重 > node.測量權(quán)重+邊.權(quán)重, 說明更新有效
如果更新有效, 判斷to是否在堆中, 如果是, 則上浮以維護堆秩序, 否則, 將to節(jié)點push入候選堆
判斷dstNode的測量權(quán)重是否被更新(!=無窮大), 如果是則說明存在最短路徑
反向查找最短路徑:
設(shè)定當前節(jié)點current = 終點
push節(jié)點current進路徑隊列
遍歷終點為current的邊, 查找符合條件的node:邊的起點.測量權(quán)重 = current.測量權(quán)重-邊.權(quán)重
push節(jié)點node進路徑隊列
循環(huán)1-4, 直到current == srcNode, 查找完成
INode: 頂點接口, 支持xy坐標和估算權(quán)重
ILine: 邊接口
IPathFinder: 最短路徑查找算法接口
IComparator: 頂點比較接口
IHeap: 頂點堆接口
tNode: 頂點, 實現(xiàn)INode
tLine: 邊, 實現(xiàn)ILine
tNodeWeightComparator: 基于權(quán)重的頂點比較器, 實現(xiàn)IComparator接口
tArrayHeap: 堆的實現(xiàn)
tAStarPathFinder: A*算法的實現(xiàn), 使用xy坐標的直線距離作為估算權(quán)重
a_star_finder_test.go
package graph
import (
"fmt"
"strings"
"testing"
)
import astar "learning/gooop/graph/a_star"
func Test_AStarFinder(t *testing.T) {
fnAssertTrue := func(b bool, msg string) {
if !b {
t.Fatal(msg)
}
}
// 設(shè)定頂點
nodes := []astar.INode {
astar.NewNode("11", 1, 1),
astar.NewNode("21", 2, 1),
astar.NewNode("31", 3, 1),
astar.NewNode("12", 1, 2),
astar.NewNode("32", 3, 2),
astar.NewNode("13", 1, 3),
astar.NewNode("33", 3, 3),
astar.NewNode("43", 4, 3),
astar.NewNode("53", 5, 3),
astar.NewNode("63", 6, 3),
astar.NewNode("73", 7, 3),
astar.NewNode("14", 1, 4),
astar.NewNode("34", 3, 4),
astar.NewNode("74", 7, 4),
astar.NewNode("15", 1, 5),
astar.NewNode("35", 3, 5),
astar.NewNode("55", 5, 5),
astar.NewNode("65", 6, 5),
astar.NewNode("75", 7, 5),
astar.NewNode("16", 1, 6),
astar.NewNode("36", 3, 6),
astar.NewNode("56", 5, 6),
astar.NewNode("17", 1, 7),
astar.NewNode("27", 2, 7),
astar.NewNode("37", 3, 7),
astar.NewNode("47", 4, 7),
astar.NewNode("57", 5, 7),
astar.NewNode("67", 6, 7),
astar.NewNode("77", 7, 7),
}
// 為相鄰點創(chuàng)建邊
var lines []astar.ILine
mapNodes := make(map[string]astar.INode, len(nodes))
for _,it := range nodes {
k := fmt.Sprintf("%v,%v", it.GetX(), it.GetY())
mapNodes[k] = it
}
for _,it := range nodes {
if up,ok := mapNodes[fmt.Sprintf("%v,%v", it.GetX(), it.GetY() - 1)];ok {
lines = append(lines, astar.NewLine(it.ID(), up.ID(), 1), astar.NewLine(up.ID(), it.ID(), 1))
}
if down,ok := mapNodes[fmt.Sprintf("%v,%v", it.GetX(), it.GetY() + 1)];ok {
lines = append(lines, astar.NewLine(it.ID(), down.ID(), 1), astar.NewLine(down.ID(), it.ID(), 1))
}
if left,ok := mapNodes[fmt.Sprintf("%v,%v", it.GetX()-1, it.GetY())];ok {
lines = append(lines, astar.NewLine(it.ID(), left.ID(), 1), astar.NewLine(left.ID(), it.ID(), 1))
}
if right,ok := mapNodes[fmt.Sprintf("%v,%v", it.GetX()+1, it.GetY())];ok {
lines = append(lines, astar.NewLine(it.ID(), right.ID(), 1), astar.NewLine(right.ID(), it.ID(), 1))
}
}
// a*算法 查找最短路徑
ok,path := astar.AStarPathFinder.FindPath(nodes, lines, "33", "77")
if !ok {
t.Fatal("failed to find min path")
}
fnPathToString := func(nodes []astar.INode) string {
items := make([]string, len(nodes))
for i,it := range nodes {
items[i] = fmt.Sprintf("%s", it)
}
return strings.Join(items, " ")
}
pathString := fnPathToString(path)
t.Log(pathString)
fnAssertTrue(pathString == "33(0+6) 34(1+5) 35(2+4) 36(3+4) 37(4+4) 47(5+3) 57(6+2) 67(7+1) 77(8+0)", "incorrect path")
}$ go test -v a_star_finder_test.go === RUN Test_AStarFinder a_star_finder_test.go:96: 33(0+6) 34(1+5) 35(2+4) 36(3+4) 37(4+4) 47(5+3) 57(6+2) 67(7+1) 77(8+0) --- PASS: Test_AStarFinder (0.00s) PASS ok command-line-arguments 0.002s
頂點接口, 支持xy坐標和估算權(quán)重
package a_star
type INode interface {
ID() string
GetX() int
GetY() int
SetX(int)
SetY(int)
SetEstimatedWeight(int)
SetMeasuredWeight(int)
GetMeasuredWeight() int
GetTotalWeight() int
}
const MaxWeight = int(0x7fffffff_00000000)邊接口
package a_star
type ILine interface {
From() string
To() string
Weight() int
}最短路徑查找算法接口
package a_star
type IPathFinder interface {
FindPath(nodes []INode, lines []ILine, from string, to string) (bool,[]INode)
}頂點比較接口
package a_star
type IComparator interface {
Less(a interface{}, b interface{}) bool
}頂點堆接口
package a_star
type IHeap interface {
Size() int
IsEmpty() bool
IsNotEmpty() bool
Push(node interface{})
Pop() (bool, interface{})
IndexOf(node interface{}) int
ShiftUp(i int)
}頂點, 實現(xiàn)INode
package a_star
import "fmt"
type tNode struct {
id string
x int
y int
measuredWeight int
estimatedWeight int
}
func NewNode(id string, x int, y int) INode {
return &tNode{
id,x, y, MaxWeight,0,
}
}
func (me *tNode) ID() string {
return me.id
}
func (me *tNode) GetX() int {
return me.x
}
func (me *tNode) GetY() int {
return me.y
}
func (me *tNode) SetX(x int) {
me.x = x
}
func (me *tNode) SetY(y int) {
me.y = y
}
func (me *tNode) SetEstimatedWeight(w int) {
me.estimatedWeight = w
}
func (me *tNode) SetMeasuredWeight(w int) {
me.measuredWeight = w
}
func (me *tNode) GetMeasuredWeight() int {
return me.measuredWeight
}
func (me *tNode) GetTotalWeight() int {
return me.estimatedWeight + me.measuredWeight
}
func (me *tNode) String() string {
return fmt.Sprintf("%s(%v+%v)", me.id, me.measuredWeight, me.estimatedWeight)
}邊, 實現(xiàn)ILine
package a_star
type tLine struct {
from string
to string
weight int
}
func NewLine(from string, to string, weight int) ILine {
return &tLine{
from,to,weight,
}
}
func (me *tLine) From() string {
return me.from
}
func (me *tLine) To() string {
return me.to
}
func (me *tLine) Weight() int {
return me.weight
}基于權(quán)重的頂點比較器, 實現(xiàn)IComparator接口
package a_star
import "errors"
type tNodeWeightComparator struct {
}
func newNodeWeightComparator() IComparator {
return &tNodeWeightComparator{
}
}
func (me *tNodeWeightComparator) Less(a interface{}, b interface{}) bool {
if a == nil || b == nil {
panic(gNullArgumentError)
}
n1 := a.(INode)
n2 := b.(INode)
return n1.GetTotalWeight() <= n2.GetTotalWeight()
}
var gNullArgumentError = errors.New("null argument error")堆的實現(xiàn)
package a_star
import (
"errors"
"fmt"
"strings"
)
type tArrayHeap struct {
comparator IComparator
items []interface{}
size int
version int64
}
func newArrayHeap(comparator IComparator) IHeap {
return &tArrayHeap{
comparator: comparator,
items: make([]interface{}, 0),
size: 0,
version: 0,
}
}
func (me *tArrayHeap) Size() int {
return me.size
}
func (me *tArrayHeap) IsEmpty() bool {
return me.size <= 0
}
func (me *tArrayHeap) IsNotEmpty() bool {
return !me.IsEmpty()
}
func (me *tArrayHeap) Push(value interface{}) {
me.version++
me.ensureSize(me.size + 1)
me.items[me.size] = value
me.size++
me.ShiftUp(me.size - 1)
me.version++
}
func (me *tArrayHeap) ensureSize(size int) {
for ;len(me.items) < size; {
me.items = append(me.items, nil)
}
}
func (me *tArrayHeap) parentOf(i int) int {
return (i - 1) / 2
}
func (me *tArrayHeap) leftChildOf(i int) int {
return i*2 + 1
}
func (me *tArrayHeap) rightChildOf(i int) int {
return me.leftChildOf(i) + 1
}
func (me *tArrayHeap) last() (i int, v interface{}) {
if me.IsEmpty() {
return -1, nil
}
i = me.size - 1
v = me.items[i]
return i,v
}
func (me *tArrayHeap) IndexOf(node interface{}) int {
n := -1
for i,it := range me.items {
if it == node {
n = i
break
}
}
return n
}
func (me *tArrayHeap) ShiftUp(i int) {
if i <= 0 {
return
}
v := me.items[i]
pi := me.parentOf(i)
pv := me.items[pi]
if me.comparator.Less(v, pv) {
me.items[pi], me.items[i] = v, pv
me.ShiftUp(pi)
}
}
func (me *tArrayHeap) Pop() (bool, interface{}) {
if me.IsEmpty() {
return false, nil
}
me.version++
top := me.items[0]
li, lv := me.last()
me.items[0] = nil
me.size--
if me.IsEmpty() {
return true, top
}
me.items[0] = lv
me.items[li] = nil
me.shiftDown(0)
me.version++
return true, top
}
func (me *tArrayHeap) shiftDown(i int) {
pv := me.items[i]
ok, ci, cv := me.minChildOf(i)
if ok && me.comparator.Less(cv, pv) {
me.items[i], me.items[ci] = cv, pv
me.shiftDown(ci)
}
}
func (me *tArrayHeap) minChildOf(p int) (ok bool, i int, v interface{}) {
li := me.leftChildOf(p)
if li >= me.size {
return false, 0, nil
}
lv := me.items[li]
ri := me.rightChildOf(p)
if ri >= me.size {
return true, li, lv
}
rv := me.items[ri]
if me.comparator.Less(lv, rv) {
return true, li, lv
} else {
return true, ri, rv
}
}
func (me *tArrayHeap) String() string {
level := 0
lines := make([]string, 0)
lines = append(lines, "")
for {
n := 1<<level
min := n - 1
max := n + min - 1
if min >= me.size {
break
}
line := make([]string, 0)
for i := min;i <= max;i++ {
if i >= me.size {
break
}
line = append(line, fmt.Sprintf("%4d", me.items[i]))
}
lines = append(lines, strings.Join(line, ","))
level++
}
return strings.Join(lines, "\n")
}
var gNoMoreElementsError = errors.New("no more elements")A*算法的實現(xiàn), 使用xy坐標的直線距離作為估算權(quán)重
package a_star
import "math"
type tAStarPathFinder struct {
}
func newAStarPathFinder() IPathFinder {
return &tAStarPathFinder{}
}
func (me *tAStarPathFinder) FindPath(nodes []INode, lines []ILine, srcID string, dstID string) (bool,[]INode) {
// 節(jié)點索引
mapNodes := make(map[string]INode, 0)
for _,it := range nodes {
mapNodes[it.ID()] = it
}
srcNode, ok := mapNodes[srcID]
if !ok {
return false, nil
}
dstNode,ok := mapNodes[dstID]
if !ok {
return false, nil
}
// 邊的索引
mapFromLines := make(map[string][]ILine, 0)
mapToLines := make(map[string][]ILine, 0)
for _, it := range lines {
if v,ok := mapFromLines[it.From()];ok {
mapFromLines[it.From()] = append(v, it)
} else {
mapFromLines[it.From()] = []ILine{ it }
}
if v,ok := mapToLines[it.To()];ok {
mapToLines[it.To()] = append(v, it)
} else {
mapToLines[it.To()] = []ILine{ it }
}
}
for _,it := range nodes {
// 設(shè)置src節(jié)點的weight為0, 其他節(jié)點的weight為MaxWeight
if it.ID() == srcID {
it.SetMeasuredWeight(0)
} else {
it.SetMeasuredWeight(MaxWeight)
}
// 計算每個節(jié)點到dst節(jié)點的估算距離
if it.ID() == dstID {
it.SetEstimatedWeight(0)
} else {
it.SetEstimatedWeight(me.distance(it.GetX(), it.GetY(), dstNode.GetY(), dstNode.GetY()))
}
}
// 將起點push到堆
heap := newArrayHeap(newNodeWeightComparator())
heap.Push(srcNode)
// 遍歷候選節(jié)點
for heap.IsNotEmpty() {
_, top := heap.Pop()
from := top.(INode)
if from.ID() == dstID {
break
}
links, ok := mapFromLines[from.ID()]
if ok {
for _,line := range links {
if to,ok := mapNodes[line.To()];ok {
if me.updateMeasuredWeight(from, to, line) {
n := heap.IndexOf(to)
if n >= 0 {
heap.ShiftUp(n)
} else {
heap.Push(to)
}
}
}
}
}
}
// 逆向查找最短路徑
if dstNode.GetMeasuredWeight() >= MaxWeight {
return false, nil
}
path := []INode{ dstNode }
current := dstNode
maxRound := len(lines)
for ;current != srcNode && maxRound > 0;maxRound-- {
linkedLines, _ := mapToLines[current.ID()]
for _,line := range linkedLines {
from, _ := mapNodes[line.From()]
if from.GetMeasuredWeight() == current.GetMeasuredWeight() - line.Weight() {
current = from
path = append(path, from)
}
}
}
if current != srcNode {
return false, nil
}
me.reverse(path)
return true, path
}
func (me *tAStarPathFinder) distance(x0, y0, x1, y1 int) int {
dx := x0 - x1
dy := y0 - y1
return int(math.Round(math.Sqrt(float64(dx * dx + dy * dy))))
}
func (me *tAStarPathFinder) reverse(nodes []INode) {
for i,j := 0, len(nodes)-1;i < j;i,j=i+1,j-1 {
nodes[i], nodes[j] = nodes[j], nodes[i]
}
}
func (me *tAStarPathFinder) updateMeasuredWeight(from INode, to INode, line ILine) bool {
w := me.min(from.GetMeasuredWeight() + line.Weight(), to.GetMeasuredWeight())
if to.GetMeasuredWeight() > w {
to.SetMeasuredWeight(w)
return true
}
return false
}
func (me *tAStarPathFinder) min(a, b int) int {
if a <= b {
return a
}
return b
}
var AStarPathFinder = newAStarPathFinder()到此，相信大家對“golang之如何使用圖的最短路徑 A*(A-Star)算法”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習！
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼