Question

求问一道最短路径的数学建模问题

图片在下面。
节点一是出发节点。需要经过每一条弧，弧上有方向。每条弧经过不止一次。求怎样走可以使最后路径总和最小。
如果能为我提供解题方法，不甚感激。
如果不能，那请问我指出：
1.这道题的设计的数学模型是什么。
2.应该查找什么方面的资料，具体某一方面。我已经知道是运筹学中的的网络模型的最短路径模型。可是我看到的资料都是求某两点之间的最短路径而不是每条路都要走的路径总和最短。
3.您有没有类似的题目的网址可以让我参考。
4.可以用更方便的方法比如MATLAB或者Lingo来解决吗？如果可以的话，您有相关程序或者网站让我参考吗？

我不想不劳而获，如果您可以为我回答以上四个问题或者之后的一些问题，不甚感激。如果您能针对我的题目为我提供查询与学习的思路和方向，我会更加感谢您。

Answer 1

题目不是很清楚：

需要经过每一条弧

每条弧【可以】经过不止一次？

是否是需要回到出发点呢？

追问

每条弧可以经过不止一次，不需要回到出发点。但是要保证总路程最短。我昨天晚上看书，将运筹图论看到最小生成树的求法，这是我的现在水平~我上图片吧

追答

你的想法都不对，其实就是一笔画问题

追问

哦哦哦~对的对的 我现在直接看一笔画可以吗？有两天时间。您觉得这道题难吗 还是说学会一笔画一计算方法就可以直接做出来呢 但是它的边有方向有权，还是一笔画吗。有向图的邮路模型，这个对不对呢

追答

有向图的邮路模型，也不对

其实你这个问题，就是使除了两个结点外，所有结点的出度等于入度，剩下的两个结点，一个是始点，出度比入度大1，一个是终点，入度比出度大1

这样就需要增加一些边，使得增加的边的权重最小

追问

您好，我现在已经把基本概念过了一遍。我没有在图论书上看到有关带权有向的一笔画的内容呢，您能帮我指出吗？
这道题不能一笔画， 奇顶点也不是两个，怎么能画出来呢？多笔画的话，路径如何相连呢
这个模型是中国邮路问题
给定一个连通图 G,其中边 e 上分别赋权 w( e)(非负)构成一个网络。今求 G 的一个圈μ (不一定是简单的),过每边至少一次且 μ的总权数 ∑ 最小。

追答

就是让你增加一定的边，使其奇数顶点只有两个。而在这些增加的边中，其权值的总和最小

Answer 2

题目不是很清楚：需要经过每一条弧每条弧【可以】经过不止一次？是否是需要回到出发点呢？

Answer 3

这个题目最后是用蚁群算法做的么