从给定顶点查找图中所有闭合路径的算法

问题描述 投票:0回答:0

我有一个无向图,没有多边/平行边,每条边都用距离加权。我希望在图中找到某个最小总距离和最大总距离之间的封闭行走。我也希望能对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]
}

以下是我目前为加速算法所做的事情:

  1. 不是找到所有循环,而是根据给定的启发式查找前几个循环。
  2. 修剪图形以尽可能删除几乎所有度数为 2 的节点,用权重 = 原始两条边之和的单个边替换它们。
  3. 使用切片来存储重复的边,而不是地图。
  4. 使用 Dijkstra 算法找到从起始节点到每个其他节点的最短距离。如果一条路线无法在这段距离内返回,请立即丢弃它。 (算法实现的代码不包含在帖子中,因为它只占运行时间的 ~4%)

根据 Go 分析器,route.go 中的 WithAddedNode 方法占运行时间的 68%,该方法的时间大致平均分配给 runtime.memmove 和 runtime.makeslice(调用 runtime.mallocgc)。本质上,我相信大部分时间都花在了复制 Routes 上。对于如何改进该算法的运行时间或任何可能的替代方法的任何反馈,我将不胜感激。如果我可以提供任何其他信息,请告诉我。非常感谢!

go graph-theory
© www.soinside.com 2019 - 2024. All rights reserved.