golang之如何使用圖的最短路徑A*(A-Star)算法

本篇內(nèi)容主要講解“golang之如何使用圖的最短路徑 A*(A-Star)算法”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“golang之如何使用圖的最短路徑 A*(A-Star)算法”吧!

在應(yīng)城等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專(zhuān)注、極致的服務(wù)理念，為客戶(hù)提供成都做網(wǎng)站、成都網(wǎng)站建設(shè)、成都外貿(mào)網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作定制網(wǎng)站制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計(jì),網(wǎng)絡(luò)營(yíng)銷(xiāo)推廣,成都外貿(mào)網(wǎng)站建設(shè)公司,應(yīng)城網(wǎng)站建設(shè)費(fèi)用合理。

golang練習(xí)之

A*(A-Star)算法

A*（A-Star）算法也是一種在圖中求解最短路徑問(wèn)題的算法，
由狄克斯特拉算法發(fā)展而來(lái)。

A*算法不僅會(huì)考慮從起點(diǎn)到候補(bǔ)頂點(diǎn)的距離，
還會(huì)考慮從當(dāng)前所在頂點(diǎn)到終點(diǎn)的估算距離。

距離估算值越接近當(dāng)前頂點(diǎn)到終點(diǎn)的實(shí)際值，
A*算法的搜索效率也就越高.
當(dāng)距離估算值小于實(shí)際距離時(shí)，
是一定可以得到正確答案的.

A*算法在游戲編程中經(jīng)常被用于計(jì)算敵人追趕玩家時(shí)的行動(dòng)路線等.

摘自 <<我的第一本算法書(shū)>> 【日】石田保輝；宮崎修一

場(chǎng)景

如下圖, 某游戲中, 地圖是網(wǎng)格狀的, 我方在S點(diǎn), 敵人在G點(diǎn), 空白區(qū)域是湖泊/樹(shù)林等不可到達(dá)區(qū)域: golang之如何使用圖的最短路徑 A*(A-Star)算法現(xiàn)在需要追擊敵人, 因此需要計(jì)算S點(diǎn)到G點(diǎn)的最短行進(jìn)路線. A*算法是以狄克斯特拉算法為基礎(chǔ), 區(qū)別是在計(jì)算候選節(jié)點(diǎn)的權(quán)重時(shí), 需要同時(shí)考慮測(cè)量權(quán)重和估算權(quán)重. 此場(chǎng)景中, 使用S點(diǎn)到G點(diǎn)坐標(biāo)的直線距離作為估算權(quán)重. 估算權(quán)重的作用就像牽引風(fēng)箏的繩子, 使得每次選取的候選節(jié)點(diǎn), 盡量是靠往終點(diǎn)方向. golang之如何使用圖的最短路徑 A*(A-Star)算法

流程

給定若干頂點(diǎn), 以及頂點(diǎn)間的若干條邊, 尋找從指定起點(diǎn)srcNode到指定終點(diǎn)dstNode的最小權(quán)重路徑
設(shè)定srcNode的權(quán)重為0, 其他頂點(diǎn)的權(quán)重為無(wú)窮大
計(jì)算所有節(jié)點(diǎn)到dstNode節(jié)點(diǎn)的估算距離, 以x,y坐標(biāo)的直線距離作為估算值
節(jié)點(diǎn).總權(quán)重 = 節(jié)點(diǎn).測(cè)量權(quán)重 + 節(jié)點(diǎn).估算權(quán)重
將srcNode節(jié)點(diǎn)送入候選堆
for 候選堆不為空:

從候選堆pop頂點(diǎn)node, node是總權(quán)重最小的候選節(jié)點(diǎn)
如果node.id == dstNode.id, 循環(huán)結(jié)束
遍歷從node出發(fā)的所有邊, 將邊的終點(diǎn)to的測(cè)量權(quán)重, 更新為min(to.測(cè)量權(quán)重, node.測(cè)量權(quán)重+邊.權(quán)重)
如果to.測(cè)量權(quán)重 > node.測(cè)量權(quán)重+邊.權(quán)重, 說(shuō)明更新有效
如果更新有效, 判斷to是否在堆中, 如果是, 則上浮以維護(hù)堆秩序, 否則, 將to節(jié)點(diǎn)push入候選堆

判斷dstNode的測(cè)量權(quán)重是否被更新(!=無(wú)窮大), 如果是則說(shuō)明存在最短路徑
反向查找最短路徑:

設(shè)定當(dāng)前節(jié)點(diǎn)current = 終點(diǎn)
push節(jié)點(diǎn)current進(jìn)路徑隊(duì)列
遍歷終點(diǎn)為current的邊, 查找符合條件的node:邊的起點(diǎn).測(cè)量權(quán)重 = current.測(cè)量權(quán)重-邊.權(quán)重
push節(jié)點(diǎn)node進(jìn)路徑隊(duì)列
循環(huán)1-4, 直到current == srcNode, 查找完成

設(shè)計(jì)

INode: 頂點(diǎn)接口, 支持xy坐標(biāo)和估算權(quán)重
ILine: 邊接口
IPathFinder: 最短路徑查找算法接口
IComparator: 頂點(diǎn)比較接口
IHeap: 頂點(diǎn)堆接口
tNode: 頂點(diǎn), 實(shí)現(xiàn)INode
tLine: 邊, 實(shí)現(xiàn)ILine
tNodeWeightComparator: 基于權(quán)重的頂點(diǎn)比較器, 實(shí)現(xiàn)IComparator接口
tArrayHeap: 堆的實(shí)現(xiàn)
tAStarPathFinder: A*算法的實(shí)現(xiàn), 使用xy坐標(biāo)的直線距離作為估算權(quán)重

單元測(cè)試

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è)定頂點(diǎn)
	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),
	}

	// 為相鄰點(diǎn)創(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")
}

測(cè)試輸出

$ 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

INode.go

頂點(diǎn)接口, 支持xy坐標(biāo)和估算權(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)

ILine.go

邊接口

package a_star

type ILine interface {
	From() string
	To() string
	Weight() int
}

IPathFinder.go

最短路徑查找算法接口

package a_star

type IPathFinder interface {
	FindPath(nodes []INode, lines []ILine, from string, to string) (bool,[]INode)
}

IComparator.go

頂點(diǎn)比較接口

package a_star

type IComparator interface {
	Less(a interface{}, b interface{}) bool
}

IHeap.go

頂點(diǎn)堆接口

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)
}

tNode.go

頂點(diǎn), 實(shí)現(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)
}

tLine.go

邊, 實(shí)現(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
}

tNodeWeightComparator.go

基于權(quán)重的頂點(diǎn)比較器, 實(shí)現(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")

tArrayHeap.go

堆的實(shí)現(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")

tAStarPathFinder.go

A*算法的實(shí)現(xiàn), 使用xy坐標(biāo)的直線距離作為估算權(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é)點(diǎn)索引
	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é)點(diǎn)的weight為0, 其他節(jié)點(diǎn)的weight為MaxWeight
		if it.ID() == srcID {
			it.SetMeasuredWeight(0)
		} else {
			it.SetMeasuredWeight(MaxWeight)
		}

		// 計(jì)算每個(gè)節(jié)點(diǎn)到dst節(jié)點(diǎn)的估算距離
		if it.ID() == dstID {
			it.SetEstimatedWeight(0)
		} else {
			it.SetEstimatedWeight(me.distance(it.GetX(), it.GetY(), dstNode.GetY(), dstNode.GetY()))
		}
	}


	// 將起點(diǎn)push到堆
	heap := newArrayHeap(newNodeWeightComparator())
	heap.Push(srcNode)

	// 遍歷候選節(jié)點(diǎn)
	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()

到此，相信大家對(duì)“golang之如何使用圖的最短路徑 A*(A-Star)算法”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！

文章標(biāo)題：golang之如何使用圖的最短路徑A*(A-Star)算法
鏈接URL：http://sd-ha.com/article0/popioo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶(hù)體驗(yàn)、網(wǎng)頁(yè)設(shè)計(jì)公司、網(wǎng)站制作、網(wǎng)站策劃、面包屑導(dǎo)航、外貿(mào)建站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

久久久精品一区ed2k-女人被男人叉到高潮的视频-中文字幕乱码一区久久麻豆樱花-俄罗斯熟妇真实视频