ในทฤษฎีกราฟและการเพิ่มประสิทธิภาพเชิงการจัดเรียงปัญหาเส้นทางของกวน ปัญหา บุรุษไปรษณีย์จีน ปัญหาการเดินทางของบุรุษไปรษณีย์ หรือปัญหาการตรวจสอบเส้นทางคือการหาเส้นทางปิดหรือวงจรที่สั้นที่สุดที่เยี่ยมชมขอบทุกขอบของกราฟแบบไม่มีทิศทาง (ที่เชื่อมต่อกัน) อย่างน้อยหนึ่งครั้ง เมื่อกราฟมีวงจรแบบออยเลอร์ (เส้นทางปิดที่ครอบคลุมขอบทุกขอบหนึ่งครั้ง) วงจรนั้นจะเป็นคำตอบที่เหมาะสมที่สุด มิฉะนั้นปัญหาการเพิ่มประสิทธิภาพคือการหาจำนวนขอบกราฟที่น้อยที่สุดที่จะทำซ้ำ (หรือเซตย่อยของขอบที่มีน้ำหนักรวมน้อยที่สุดเท่าที่จะเป็นไปได้) เพื่อให้มัลติกราฟ ที่ได้ มีวงจรแบบออยเลอร์^{[ 1 ]}สามารถแก้ไขได้ในเวลาพหุนาม [ ^{2 ] ซึ่ง}แตกต่างจากปัญหาพนักงานขายเดินทางซึ่งเป็น ปัญหา NP-hard [ ^{3 ] แตก}ต่างจากปัญหาพนักงานขายเดินทางตรงที่พนักงานขายเดินทางไม่สามารถเยี่ยมชมโหนดซ้ำได้และไม่จำเป็นต้องเยี่ยมชมขอบทุกขอบ

ปัญหาดังกล่าวได้รับการศึกษาครั้งแรกโดยนักคณิตศาสตร์ชาวจีนMeigu Guanในปี 1960 ซึ่งบทความภาษาจีนของเขาได้รับการแปลเป็นภาษาอังกฤษในปี 1962 ^{[ 4 ]}ชื่อเดิม "ปัญหาบุรุษไปรษณีย์ชาวจีน" ได้รับการตั้งขึ้นเพื่อเป็นเกียรติแก่เขา แหล่งข้อมูลต่างๆ ระบุว่าผู้ตั้งชื่อนี้คือAlan J. GoldmanหรือJack Edmondsซึ่งทั้งสองคนทำงานอยู่ที่สำนักงานมาตรฐานแห่งชาติของสหรัฐอเมริกาในขณะนั้น^{[ 5 ] [ 6 ]}

การวางนัยทั่วไปนี้รับอินพุตเป็นเซตT ใดๆ ที่มีจำนวนจุดยอดเป็นเลขคู่ และต้องสร้างเอาต์พุตเป็นเซตของขอบที่มีน้ำหนักน้อยที่สุดในกราฟ โดยที่จุดยอดที่มีดีกรีเป็นเลขคี่ของเซตนั้นตรงกับจุด ยอดใน Tเอาต์พุตนี้เรียกว่าT -join ปัญหา T -join นี้ สามารถแก้ไขได้ในเวลาพหุนามด้วยวิธีการเดียวกันกับที่ใช้แก้ปัญหาบุรุษไปรษณีย์

ปัญหาการตรวจสอบเส้นทางแบบไม่มีทิศทางสามารถแก้ไขได้ในเวลาพหุนามโดยใช้อัลกอริทึมที่อิงตามแนวคิดของT -join ให้Tเป็นเซตของจุดยอดในกราฟ เซตของขอบJเรียกว่าT -joinถ้ากลุ่มของจุดยอดที่มีจำนวนขอบที่เชื่อมต่อกับJเป็นจำนวนคี่ คือเซตT T - join จะมีอยู่เมื่อใดก็ตามที่ส่วนประกอบที่เชื่อมต่อกันทุกส่วนของกราฟมีจำนวนจุดยอดในT เป็นจำนวนคู่ ปัญหา T-joinคือการหาT -join ที่มีจำนวนขอบน้อยที่สุดหรือมีน้ำหนักรวมน้อยที่สุด

สำหรับT ใดๆ การเชื่อมต่อ Tที่เล็กที่สุด(ถ้ามี) จะประกอบด้วยเส้นทางที่เชื่อมต่อจุดยอดของTเป็นคู่ๆ เส้นทางเหล่านั้นจะมีความยาวรวมหรือน้ำหนักรวมน้อยที่สุดเท่าที่จะเป็นไปได้ ในคำตอบที่ดีที่สุด เส้นทางสองเส้นใดๆ ก็จะไม่ใช้ขอบร่วมกัน แต่พวกมันอาจมีจุดยอดร่วมกันได้ การเชื่อมต่อ T ที่เล็กที่สุด สามารถหาได้โดยการสร้างกราฟสมบูรณ์บนจุดยอดของTโดยมีขอบที่แสดงถึงเส้นทางที่สั้นที่สุดในกราฟอินพุตที่กำหนด จากนั้นจึงหาการจับคู่ที่สมบูรณ์แบบที่มีน้ำหนักน้อยที่สุดในกราฟสมบูรณ์นี้ ขอบของการจับคู่นี้แสดงถึงเส้นทางในกราฟดั้งเดิม ซึ่งการรวมกันของเส้นทางเหล่านั้นจะสร้างการ เชื่อมต่อ T ที่ต้องการ ทั้งการสร้างกราฟสมบูรณ์และการหาการจับคู่ในกราฟนั้นสามารถทำได้ใน ^ขั้น ตอนการคำนวณ O( n³ ) ${\displaystyle {\tfrac {1}{2}}|T|}$

สำหรับปัญหาการตรวจสอบเส้นทาง ควรเลือก Tเป็นเซตของจุดยอดที่มีดีกรีคี่ทั้งหมด ตามสมมติฐานของปัญหา กราฟทั้งหมดเชื่อมต่อกัน (มิฉะนั้นจะไม่มีเส้นทาง) และตามเลมมาการจับมือกัน กราฟจะมีจำนวนจุดยอดคี่เป็นเลขคู่ ดังนั้นT -join จึงมีอยู่เสมอ การเพิ่มขอบของT -join เป็นสองเท่าจะทำให้กราฟที่กำหนดกลายเป็นมัลติกราฟออยเลอร์ (กราฟที่เชื่อมต่อกันซึ่งทุกจุดยอดมีดีกรีเป็นเลขคู่) จากนั้นจึงสรุปได้ว่ามีเส้นทางออยเลอร์ซึ่งเป็นเส้นทางที่เยี่ยมชมขอบแต่ละขอบของมัลติกราฟเพียงครั้งเดียว เส้นทางนี้จะเป็นคำตอบที่ดีที่สุดสำหรับปัญหาการตรวจสอบเส้นทาง^{[ 7 ] [ 2 ]}

บนกราฟแบบมีทิศทาง แนวคิดทั่วไปเดียวกันนี้ใช้ได้ แต่ต้องใช้เทคนิคที่แตกต่างกัน หากกราฟแบบมีทิศทางเป็นกราฟออยเลอร์ ก็เพียงแค่หาวัฏจักรออยเลอร์ หากไม่ใช่ ก็ต้องหาT -joins ซึ่งในกรณีนี้หมายถึงการหาเส้นทางจากจุดยอดที่มีดีกรีขาเข้ามากกว่าดีกรีขาออกไปยังจุดยอดที่มีดีกรีขาออกมากกว่าดีกรีขาเข้าเพื่อให้ดีกรีขาเข้าของทุกจุดยอดเท่ากับดีกรีขาออก ปัญหานี้สามารถแก้ไขได้ในรูปแบบของปัญหาการไหลต้นทุนต่ำสุดซึ่งมีอุปทานหนึ่งหน่วยสำหรับดีกรีขาเข้าส่วนเกินทุกหน่วย และความต้องการหนึ่งหน่วยสำหรับดีกรีขาออกส่วนเกินทุกหน่วย ดังนั้นจึงสามารถแก้ไขได้ในเวลา O(| V | ² | E |) คำตอบจะมีอยู่ก็ต่อเมื่อกราฟที่กำหนดเป็นกราฟ ที่เชื่อมต่อ กันอย่างแน่นหนา^{[ 2 ] [ 8 ]}

ปัญหาเชิงการจัดเรียงต่างๆ ได้รับการลดทอนให้เหลือเพียงปัญหาบุรุษไปรษณีย์จีน ซึ่งรวมถึงการค้นหาการตัดสูงสุดในกราฟระนาบและวงจรความยาวเฉลี่ยต่ำสุดในกราฟที่ไม่มีทิศทาง^{[ 9 ]}

มีการศึกษารูปแบบต่างๆ ของปัญหาบุรุษไปรษณีย์จีนและพบว่าเป็นปัญหาNP -complete ^{[ 10 ]}

• ปัญหาบุรุษไปรษณีย์ลมแรงเป็นรูปแบบหนึ่งของปัญหาการตรวจสอบเส้นทางซึ่งอินพุตเป็นกราฟแบบไม่มีทิศทาง แต่ละขอบอาจมีต้นทุนที่แตกต่างกันสำหรับการเดินทางในทิศทางหนึ่งเมื่อเทียบกับการเดินทางในอีกทิศทางหนึ่ง ตรงกันข้ามกับวิธีแก้ปัญหาสำหรับกราฟแบบมีทิศทางและไม่มีทิศทาง ปัญหานี้เป็นปัญหาNP- complete ^{[ 11 ] [ 12 ]}
• ปัญหาบุรุษไปรษณีย์จีนแบบผสม : สำหรับปัญหานี้ ขอบบางส่วนอาจเป็นแบบมีทิศทาง ดังนั้นจึงสามารถเยี่ยมชมได้จากทิศทางเดียวเท่านั้น เมื่อปัญหาต้องการการเดินทางขั้นต่ำของไดกราฟ (หรือมัลติไดกราฟ) จะเรียกว่า "ปัญหาคนกวาดถนนนิวยอร์ก" ^{[ 13 ]}
• ปัญหาบุรุษไปรษณีย์ชาวจีนkตัว : จงหาเส้นทาง kเส้นทางที่เริ่มต้นจากตำแหน่งที่กำหนด โดยที่แต่ละเส้นทางจะต้องผ่านอย่างน้อยหนึ่งเส้นทาง เป้าหมายคือการลดต้นทุนของเส้นทางที่แพงที่สุดให้เหลือน้อยที่สุด
• ปัญหา "บุรุษไปรษณีย์ชนบท": แก้ปัญหาโดยที่ขอบบางส่วนไม่จำเป็น^{[ 12 ]}

• ปัญหาพนักงานขายเดินทาง
• การกำหนดเส้นทางส่วนโค้ง
• ปัญหาบุรุษไปรษณีย์ชาวจีนผสม

• ไวส์สไตน์, เอริก ดับเบิลยู. , "ปัญหาบุรุษไปรษณีย์จีน" , MathWorld
• สื่อที่เกี่ยวข้องกับปัญหาการตรวจสอบเส้นทางในวิกิมีเดียคอมมอนส์