中国邮递员问题
維基百科,自由的 encyclopedia
中国邮递员问题(也称路线检查问题,Route Inspection Problem)是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑,且此路徑需通過所有邊至少一次。现实意义中,中国邮递员问题就是在一個已知的地區,郵差要設法找到一條最短路徑,走過此地區所有的街道,且最後要回到出發點。
此問題是圖遍歷問題的一種。无向图的中国邮递员问题是容易解决的,是P问题;而有向图的中国邮递员问题是NP完全问题。中国邮递员问题由管梅谷教授在1960年提出,而美國國家標準和技術研究院(NIST)的 Alan Goldman 首先將此問題命名为中国邮递员问题。[1]