中国邮递员问题
维基百科,自由的 encyclopedia
中国邮递员问题(也称路线检查问题,Route Inspection Problem)是一个图论问题。此问题为在一个连通的无向图中找到一最短的封闭路径,且此路径需通过所有边至少一次。现实意义中,中国邮递员问题就是在一个已知的地区,邮差要设法找到一条最短路径,走过此地区所有的街道,且最后要回到出发点。
此问题是图遍历问题的一种。无向图的中国邮递员问题是容易解决的,是P问题;而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出,而美国国家标准和技术研究院(NIST)的 Alan Goldman 首先将此问题命名为中国邮递员问题。[1]