在访问每个节点的有向加权图中查找最短路径，且不限制重新访问节点和边

Question

我正在使用NetworkX Python库。对我试图解决的问题的更广泛的描述在这里。

我想找到1）至少访问每个节点一次的有效路径和2）基于边权重的至少访问每个节点一次的最短路径。

这听起来像是旅行推销员问题的一个变种。另一个值得注意的是，图几乎是无向的——大多数节点是双向连接的，只有少数几个节点是双向连接的(

我研究了NetworkX算法，但似乎没有一个能满足这个问题。

用于生成图形的代码为：

    def generate_graph(self):
        ind = (12, 0)
        self.ball = ind
        locs = [ind]
        while len(locs):
            next_loc = locs.pop()
            if not self.nodes[next_loc]:
                self.nodes[next_loc] = AmazeGameLocation(next_loc)
                self.paths.add_node(self.nodes[next_loc])

            moves = [("U", (-1, 0)), ("D", (1, 0)), ("L", (0, -1)), ("R", (0, 1))]
            for move in moves:
                next_move_loc = add_tuples(move[1], next_loc)
                if self.is_move_possible(next_move_loc):
                    next_attempt = add_tuples(move[1], next_move_loc)
                    weight = 1
                    while self.is_move_possible(next_attempt):
                        next_move_loc = next_attempt
                        next_attempt = add_tuples(move[1], next_move_loc)
                        weight += 1
                    if not self.nodes[next_move_loc]:
                        self.nodes[next_move_loc] = AmazeGameLocation(next_move_loc)
                        self.paths.add_node(self.nodes[next_move_loc])
                        locs.append(next_move_loc)
                    self.paths.add_edge(self.nodes[next_loc], self.nodes[next_move_loc], weight=weight)
                    self.nodes[next_loc].dirs[move[0]] = self.nodes[next_move_loc]

这里有一个示例图。

有关此图表和问题的更多信息，请访问我的GitHub。

Answer 1

我想找到1）至少访问每个节点一次的有效路径和2）基于边权重的至少访问每个节点一次的最短路径。

对于1）：这非常简单，例如，您可以尝试找到图形的生成树。然后，您可以通过遍历生成树来构建访问图中所有顶点的路径。

对于2）：让G成为您的图形，然后您可以构建G的G的“度量完成”，这意味着G'的顶点是G的顶点，对于任何一对顶点u，v，在G'中都有一条边u，v，使用G中从u到v的最短路径的权重进行加权
那么您所要做的就是在G'上求解TSP，以获得您在G上寻找的解决方案。