我有一个无向的图，没有多个/平行的边，每个边都有一个距离。我希望在图中找到一个最小和最大总距离之间的闭合行走。我还希望能够设置行走中重复距离的限制，例如，如果一个10的边被遍历两次，重复距离为10。将重复距离设置为0应能在图形中找到闭合路径最后，虽然找到 * 所有 * 闭合的行走是很好的，但我不确定这对于有数千/数百万潜在路线的较大图是否可行，因为我相信这将需要指数级的时间。所以，我目前正试图找到几个根据启发式函数是最好的封闭行走，以便算法在合理的时间内完成。
编辑：近似性能要求-我用来测试的图目前有17，070个节点和23，026条边。生成的循环包含大约50条边，需要20秒的时间来查找，但是我希望在〈1分钟的时间范围内找到更长距离的循环（约100条边）。
以下是我目前的做法：
graph.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
}

route.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.不是找到所有循环，而是根据给定的启发式算法找到前几个循环。
1.修剪图以尽可能删除几乎所有2度的节点，用权重=原始两条边之和的单条边替换它们。
1.使用切片存储重复边，而不是贴图。
1.使用Dijkstra算法找到从起始节点到每个其他节点的最短距离。如果一条路线无法在这个距离内返回，请立即丢弃它。（算法实现的代码没有包含在帖子中，因为它只占运行时间的4%）
根据Go分析器，route.go中的WithAddedNode方法占运行时的68%，该方法中的时间大约平均分配在runtime.memmove和runtime. makslice之间（调用runtime.mallocgc）。我相信大部分时间都花在复制路由上了。我非常感谢任何关于如何改进此算法的运行时间或任何可能的替代方法的反馈。如果有任何我可以提供的额外信息，请让我知道。非常感谢！