我有一个无向图,没有多边/平行边,每条边都用距离加权。我希望在图中找到某个最小总距离和最大总距离之间的封闭行走。我也希望能对walk中的重复距离设置一个限制,比如一条10的边遍历两次,重复距离为10。设置重复距离为0应该会找到closed图中的路径(与步行相反)。最后,虽然很高兴找到 all 封闭行走,但我不确定这对于有数千/数百万条潜在路线的较大图形是否可行,因为我相信这将花费指数时间。因此,我目前正在尝试根据启发式函数找到一些最佳的封闭行走,以便算法在合理的时间内完成。
这是我目前的做法:
图.go:
package graph
import (
"fmt"
"github.com/bgadrian/data-structures/priorityqueue"
)
// A Graph struct is a collection of nodes and edges represented as an adjacency list.
// Each edge has a weight (float64).
type Edge struct {
HeuristicValue int // Lower heuristic = higher priority
Distance float64
}
type Graph struct {
Edges map[int]map[int]Edge // adjacency list, accessed like Edges[fromId][toId]
}
func (g *Graph) FindAllLoops(start int, minDistance float64, maxDistance float64, maxRepeated float64, routesCap int) []Route {
// Find all loops that start and end at node start.
// A loop is a closed walk through the graph.
loops := []Route{}
loopCount := 0
queue, _ := priorityqueue.NewHierarchicalHeap(100, 0, 100, false)
queue.Enqueue(*NewRoute(start), 0)
size := 1
distanceToStart := getDistanceToStart(g, start)
for size > 0 {
// Pop the last element from the stack
temp, _ := queue.Dequeue()
size--
route := temp.(Route)
// Get the last node from the route
lastNode := route.LastNode()
// If the route is too long or has too much repeated distance,
// don't bother exploring it further
if route.Distance + distanceToStart[route.LastNode()] > maxDistance || route.RepeatedDistance > maxRepeated {
continue
}
// Now we need to efficiently check if the total repeated distance is too long
// If the last node is the start node and the route is long enough, add it to the list of loops
if lastNode == start && route.Distance >= minDistance && route.Distance <= maxDistance {
loops = append(loops, route)
loopCount++
if loopCount >= routesCap {
return loops
}
}
// Add all the neighbours of the last node to the stack
for neighbour := range g.Edges[lastNode] {
// newRoute will be a copy of the current route, but with the new node added
newRoute := route.WithAddedNode(neighbour, g.Edges[lastNode][neighbour])
queue.Enqueue(newRoute, newRoute.Heuristic())
size++
}
}
return loops
}
路线.go:
package graph
import (
"fmt"
)
// A route is a lightweight struct describing a route
// It is stored as a sequence of nodes (ints, which are the node ids)
// and a distance (float64)
// It also counts the total distance that is repeated (going over the same
// edge twice)
// To do this, it stores a list of edges that have been traversed before
type Route struct {
Nodes []int
Distance float64
Repeated []IntPair // two ints corresponding to the nodes, orderedd by (smallest, largest)
RepeatedDistance float64
Heuristic int // A heuristic for the type of Routes we would like to generate
LastWay int
}
type IntPair struct {
A int
B int
}
// WithAddedNode adds a node to the route
func (r *Route) WithAddedNode(node int, edge Edge) Route {
newRoute := Route{Nodes: make([]int, len(r.Nodes) + 1), Distance: r.Distance, Repeated: make([]IntPair, len(r.Repeated), len(r.Repeated) + 1), RepeatedDistance: r.RepeatedDistance, Ways: r.Ways, LastWay: r.LastWay}
copy(newRoute.Nodes, r.Nodes)
copy(newRoute.Repeated, r.Repeated)
newRoute.Nodes[len(r.Nodes)] = node
newRoute.Distance += edge.Distance
// Get an IntPair where A is the smaller node id and B is the larger
var pair IntPair
if newRoute.Nodes[len(newRoute.Nodes)-2] < node {
pair = IntPair{newRoute.Nodes[len(newRoute.Nodes)-2], node}
} else {
pair = IntPair{node, newRoute.Nodes[len(newRoute.Nodes)-2]}
}
// Check if the edge has been traversed before
found := false
for _, p := range newRoute.Repeated {
if p == pair {
newRoute.RepeatedDistance += edge.Distance
found = true
break
}
}
if !found {
newRoute.Repeated = append(newRoute.Repeated, pair)
}
// Current heuristic sums heuristics of edges but this may change in the future
newRoute.Heuristic += edge.HeuristicValue
return newRoute
}
func (r *Route) Heuristic() int {
return r.Heuristic
}
func (r *Route) LastNode() int {
return r.Nodes[len(r.Nodes)-1]
}
以下是我目前为加速算法所做的事情:
根据 Go 分析器,route.go 中的 WithAddedNode 方法占运行时间的 68%,该方法的时间大致平均分配给 runtime.memmove 和 runtime.makeslice(调用 runtime.mallocgc)。本质上,我相信大部分时间都花在了复制 Routes 上。对于如何改进该算法的运行时间或任何可能的替代方法的任何反馈,我将不胜感激。如果我可以提供任何其他信息,请告诉我。非常感谢!