Answer

问题及解答

中国邮递员问题

Posted by haifeng on 2018-05-10 18:27:58 last update 2018-05-10 18:41:27 | Edit | Answers (0)

问题描述:

邮递员发送邮件时, 要从邮局出发, 经过他投递范围内的每条街道至少一次, 最后返回邮局. 邮递员希望能选择一条行程最短的路线.


 

模型

这里用点表示交叉路口, 点与点之间的连线(边)表示街道. 每条边赋予一个数(权)表示街道的长度.

 

这个问题是遍历所有边且使得权最小的问题.

 

Remark:

由于此问题是由中国的管梅谷教授首先研究的, 国际上通称为中国邮递员问题.

 

 


References:

赵静、但琦主编《数学建模与数学实验》(第四版)P.104

宋增民 主编 《图论及其应用》1.1.2