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