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

基本解釋

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

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

中國(guó)郵遞員問(wèn)題

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