中國郵遞員問題 中國郵遞員問題是郵遞員在某一地區(qū)的信件投遞路程問題。郵遞員每天從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問題是他應(yīng)如何安排送信的路線可以使所走的總路程最短。這個問題由中國學(xué)者管梅谷在1960年首先提出，并給出了解法——“奇偶點圖上作業(yè)法”，被國際上統(tǒng)稱為“中國郵遞員問題”。用圖論的語言描述，給定一個連通圖G，每邊e有非負權(quán))，要求一條回路經(jīng)過每條邊至少一次，且滿足總權(quán)最小。

基本解釋

著名圖論問題之一。郵遞員從郵局出發(fā)送信，要求對轄區(qū)內(nèi)每條街，都至少通過一次，再回郵局。在此條件下，怎樣選擇一條最短路線?此問題由中國數(shù)學(xué)家管梅谷于1960年首先研究并給出算法，故名。

網(wǎng)絡(luò)解釋

中國郵遞員問題

中國郵遞員問題是郵遞員在某一地區(qū)的信件投遞路程問題。郵遞員每天從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問題是他應(yīng)如何安排送信的路線可以使所走的總路程最短。這個問題由中國學(xué)者管梅谷在1960年首先提出，并給出了解法——“奇偶點圖上作業(yè)法”，被國際上統(tǒng)稱為“中國郵遞員問題”。用圖論的語言描述，給定一個連通圖G，每邊e有非負權(quán))，要求一條回路經(jīng)過每條邊至少一次，且滿足總權(quán)最小。