中国邮递员问题
问题描述:
邮递员发送邮件时, 要从邮局出发, 经过他投递范围内的每条街道至少一次, 最后返回邮局. 邮递员希望能选择一条行程最短的路线.
模型
这里用点表示交叉路口, 点与点之间的连线(边)表示街道. 每条边赋予一个数(权)表示街道的长度.
这个问题是遍历所有边且使得权最小的问题.
Remark:
由于此问题是由中国的管梅谷教授首先研究的, 国际上通称为中国邮递员问题.
References:
赵静、但琦主编《数学建模与数学实验》(第四版)P.104
宋增民 主编 《图论及其应用》1.1.2