Question

一个图论问题

有一堆点，任意两点相连线，每个点有个权，每条线有个权。需找一种方式，从一点出发，经过所有点。要求从该点出发后经过的点和线的权相加，在权和到达一个值之前回到初始点，将权和记下，然后权和清零，重新开始记权。用这种方式遍历全部点。找出所有可行路线中记下的权和的和的最小值。
相当于出去玩，，，玩到一定时间必须回来下。。。然后再出去玩

玩遍所有地方

需要的最小时间

请提示怎么求解
最后回到原点

Answer 1

这个在图论上是一个非常难的问题。
（对于数学问题来讲，非常难的意思就是基本上别想解了。）
图论中的“旅行商”问题与这个类似，但要比这个简单的多。旅行商问题中，只有每条线有权，也就是每个点的权是零，而且那个必须回来的阈值是无穷大，也就是一次游完所有地方。即使这样，旅行商问题也是非常困难的问题，是著名的 NP-hard 问题之一。所以你就可想而知你的问题了，基本上想都不要想了。