ปัญหาบุรุษไปรษณีย์จีนแบบผสม (MCPP หรือ MCP)คือการค้นหาเส้นทางที่สั้นที่สุดของกราฟที่มีเซตของจุดยอด V เซตของขอบที่ไม่มีทิศทาง E ที่มีน้ำหนักเชิงตรรกะบวก และเซตของส่วนโค้งที่มีทิศทาง A ที่มีน้ำหนักเชิงตรรกะบวก ซึ่งครอบคลุมขอบหรือส่วนโค้งแต่ละอันอย่างน้อยหนึ่งครั้งด้วยต้นทุนที่น้อยที่สุด^{[ 1 ]}ปัญหานี้ได้รับการพิสูจน์แล้วว่าเป็นปัญหาNP -completeโดยPapadimitriou ^{[ 2 ]}ปัญหาบุรุษไปรษณีย์จีนแบบผสมมักเกิดขึ้นในปัญหาการกำหนดเส้นทางส่วนโค้งเช่น การไถหิมะ ซึ่งถนนบางสายแคบเกินไปที่จะสัญจรได้ทั้งสองทิศทาง ในขณะที่ถนนสายอื่นเป็นแบบสองทิศทางและสามารถไถได้ทั้งสองทิศทาง

การตรวจสอบ กราฟผสมที่มีเส้นทางการเดินทางของบุรุษไปรษณีย์ขนาดใดก็ได้นั้นทำได้ง่ายโดยการตรวจสอบว่ากราฟนั้นเชื่อมต่อกันอย่างแน่นหนาหรือไม่ ปัญหาดังกล่าวเป็นปัญหา NP-hard หากเราจำกัดเส้นทางการเดินทางของบุรุษไปรษณีย์ให้ผ่านส่วนโค้งแต่ละส่วนเพียงครั้งเดียว หรือหากเราจำกัดให้ผ่านขอบแต่ละขอบเพียงครั้งเดียว ดังที่พิสูจน์โดย Zaragoza Martinez ^{[ 3 ] [ 4 ]}

ปัญหาดังกล่าวเป็นปัญหาที่ซับซ้อนกว่าปัญหา บุรุษไปรษณีย์ชาวจีน

นิยามทางคณิตศาสตร์คือ:

อินพุต: กราฟแบบผสมที่มีการเชื่อมต่ออย่างแน่นหนาโดยมีค่าใช้จ่ายสำหรับทุกขอบและค่าใช้จ่ายสูงสุด ${\displaystyle G=(V,E,A)}$${\displaystyle c(e)\geq 0}$${\displaystyle e\subset E\cup A}$${\displaystyle c_{max}}$

คำถาม: มีเส้นทางท่องเที่ยว (แบบมีทิศทาง) ที่ผ่านขอบทุกเส้นและส่วนโค้งทุกส่วนอย่างน้อยหนึ่งครั้งและมีค่าใช้จ่ายสูงสุดหรือไม่? ^{[ 5 ]}${\displaystyle E}$${\displaystyle A}$${\displaystyle c_{max}}$

ความยากลำบากหลักในการแก้ปัญหา Mixed Chinese Postman อยู่ที่การเลือกทิศทางสำหรับขอบ (ที่ไม่มีทิศทาง) เมื่อเรามีงบประมาณจำกัดสำหรับการเดินทางและสามารถเดินทางผ่านแต่ละขอบได้เพียงครั้งเดียวเท่านั้น จากนั้นเราต้องกำหนดทิศทางของขอบและเพิ่มส่วนโค้งเพิ่มเติมเพื่อให้ได้กราฟออยเลอร์แบบมีทิศทาง นั่นคือเพื่อให้ทุกจุดยอดสมดุล หากมีขอบหลายเส้นที่เชื่อมต่อกับจุดยอดเดียว การกำหนดทิศทางที่ถูกต้องของแต่ละขอบไม่ใช่เรื่องง่าย^{[ 6 ]}นักคณิตศาสตร์ Papadimitriou ได้วิเคราะห์ปัญหานี้ด้วยข้อจำกัดเพิ่มเติมว่า "MIXED CHINESE POSTMAN เป็นปัญหา NP-complete แม้ว่ากราฟอินพุตจะเป็นกราฟระนาบ แต่ละจุดยอดมีดีกรีไม่เกินสาม และแต่ละขอบและส่วนโค้งมีค่าใช้จ่ายหนึ่ง" ^{[ 7 ]}

กระบวนการตรวจสอบว่ากราฟผสมเป็นออยเลอร์หรือไม่นั้นมีความสำคัญต่อการสร้างอัลกอริทึมเพื่อแก้ปัญหา Mixed Chinese Postman ดีกรีของกราฟผสม G ต้องเป็นเลขคู่จึงจะมีวัฏจักรออยเลอร์ได้ แต่แค่นี้ยังไม่เพียงพอ^{[ 8 ]}

ข้อเท็จจริงที่ว่าปัญหา Mixed Chinese Postman เป็นปัญหา NP-hard ทำให้เกิดการค้นหาอัลกอริทึมเวลาพหุนามที่เข้าใกล้คำตอบที่เหมาะสมที่สุดจนถึงเกณฑ์ที่สมเหตุสมผล Frederickson ได้พัฒนาวิธีการที่มีปัจจัย 3/2 ที่สามารถนำไปใช้กับกราฟระนาบได้^{[ 9 ]}และ Raghavachari และ Veerasamy พบวิธีการที่ไม่จำเป็นต้องเป็นกราฟระนาบ^{[ 10 ]}อย่างไรก็ตาม เวลาพหุนามไม่สามารถหาต้นทุนของการเดินทางเปล่า เวลาที่รถไถหิมะใช้ในการไปถึงถนนที่จะไถ หรือเวลาที่รถกวาดถนนใช้ในการไปถึงถนนที่จะกวาดได้^{[ 11 ] [ 12 ]}

กำหนดให้กราฟผสมที่มีการเชื่อมต่ออย่างแน่นหนาโดยมีเซตของจุดยอด, เซตของขอบ, เซตของส่วนโค้งและต้นทุนที่ไม่เป็นลบสำหรับแต่ละจุดยอด ปัญหา MCPP ประกอบด้วยการค้นหาเส้นทางที่มีต้นทุนต่ำสุดซึ่งผ่านแต่ละลิงก์อย่างน้อยหนึ่งครั้ง ${\displaystyle G=(V,E,A)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle A}$${\displaystyle c_{e}}$${\displaystyle e\in E\cup A}$${\displaystyle e\in E\cup A}$

กำหนดให้, , , แทนเซตของขอบที่มีจุดปลายเพียงจุดเดียวใน, และ. กำหนดให้จุดยอด , (indegree) แทนจำนวนส่วนโค้งที่เข้าสู่, (outdegree) คือจำนวนส่วนโค้งที่ออกจาก, และ(degree) คือจำนวนลิงก์ที่เชื่อมต่อกับ. ^{[ 13 ]}โปรดทราบว่า. กราฟผสมเรียกว่า กราฟผสม แม้ว่าจุดยอดทั้งหมดจะมีดีกรีคู่ เรียกว่ากราฟสมมาตรถ้าสำหรับแต่ละจุดยอด, และเรียกว่ากราฟสมดุลถ้าเมื่อกำหนดเซตย่อยของจุดยอดใดๆ ผลต่างระหว่างจำนวนส่วนโค้งที่ชี้จากไปยัง, , และจำนวนส่วนโค้งที่ชี้จาก ไปยัง, , ไม่มากกว่าจำนวนขอบที่ไม่มีทิศทางที่เชื่อมและ, . ${\displaystyle S\subset V}$${\displaystyle \delta ^{+}(S)=\{(i,j)\in A:i\in S,j\in V\backslash S\}}$${\displaystyle \delta ^{-}(S)=\{(i,j)\in A:i\in V\backslash S,j\in S\}}$${\displaystyle \delta (S)}$${\displaystyle S}$${\displaystyle \delta ^{\star }=\delta (S)\cup \delta ^{+}(S)\cup \delta ^{-}}$${\textstyle i}$${\displaystyle d_{i}^{-}}$${\displaystyle i}$${\displaystyle d_{i}^{+}}$${\textstyle i}$${\displaystyle d_{i}}$${\displaystyle i}$${\displaystyle d_{i}=|\delta ^{\star }(\{{i}\})|}$${\displaystyle G=(V,E,A)}$${\displaystyle d_{i}^{-}=d_{i}^{+}}$${\textstyle i}$${\displaystyle S}$${\displaystyle S}$${\displaystyle V\backslash S}$${\displaystyle |\delta ^{+}(S)|}$${\displaystyle V\backslash S}$${\displaystyle S}$${\displaystyle |\delta ^{-}(S)|}$${\displaystyle S}$${\displaystyle V\backslash S}$${\displaystyle |\delta (S)|}$

เป็นที่ทราบกันดีว่ากราฟผสมจะเป็นแบบออยเลอร์ก็ต่อเมื่อเป็นกราฟคู่และสมดุล^{[ 14 ]}โปรดสังเกตว่าถ้าเป็นกราฟคู่และสมมาตร G ก็จะเป็นกราฟสมดุล (และแบบออยเลอร์) ด้วย ยิ่งไปกว่านั้น ถ้าเป็นกราฟคู่ ปัญหาสามารถแก้ได้อย่างแม่นยำในเวลาพหุนาม^{[ 15 ]}${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle MCPP}$

1. กำหนดให้กราฟผสมที่มีจำนวนสมาชิกเท่ากันและเชื่อมต่อกันอย่างแน่นหนาให้เป็นเซตของส่วนโค้งที่ได้จากการสุ่มกำหนดทิศทางให้กับขอบในและ โดยมีค่าใช้จ่ายเท่ากัน จงคำนวณสำหรับแต่ละจุดยอด i ในกราฟทิศทาง จุดยอด ที่มีจะถือว่าเป็นแหล่งผลิต (แหล่งรับ) ที่มีอุปสงค์ และอุปทาน โปรดทราบว่าเนื่องจากเป็นกราฟที่มีจำนวนสมาชิกเท่ากัน อุปทานและอุปสงค์ทั้งหมดจึงเป็นจำนวนคู่ (ศูนย์ถือเป็นจำนวนคู่)${\displaystyle G=(V,E,A)}$${\displaystyle A_{1}}$${\displaystyle E}$${\displaystyle s_{i}=d_{i}^{-}-d_{i}^{+}}$${\displaystyle (V,A\คัพ A_{1})}$${\textstyle i}$${\displaystyle s_{i}>0(s_{i}<0)}$${\displaystyle s_{i}(-s_{i})}$${\displaystyle G}$
2. ให้เป็นเซตของส่วนโค้งในทิศทางตรงกันข้ามกับส่วนโค้งในและ โดยมีค่าใช้จ่ายเท่ากับขอบที่สอดคล้องกันเหล่านั้น และให้เป็นเซตของส่วนโค้งที่ขนานกับโดยมีค่าใช้จ่ายเป็นศูนย์${\displaystyle A_{2}}$${\displaystyle A_{1}}$${\displaystyle A_{3}}$${\displaystyle A_{2}}$
3. เพื่อตอบสนองความต้องการของจุดยอดทั้งหมด ให้แก้ปัญหาการไหลที่มีต้นทุนต่ำสุดในกราฟโดยที่แต่ละส่วนโค้งในมีความจุอนันต์ และแต่ละส่วนโค้งในมีความจุ 2 ให้เป็นการไหลที่เหมาะสมที่สุด${\displaystyle s_{i}}$${\displaystyle (V,A\cup A_{1}\cup A_{2}\cup A_{3})}$${\displaystyle A\cup A_{1}\cup A_{2}}$${\displaystyle A_{3}}$${\displaystyle x_{ij}}$
4. สำหรับแต่ละส่วนโค้งในdo: ถ้าให้กำหนดทิศทางของขอบที่สอดคล้องกันในจากไป(ทิศทางจากไปที่กำหนดให้กับขอบที่เกี่ยวข้องในขั้นตอนที่ 1 นั้น "ผิด"); ถ้าให้กำหนดทิศทางของขอบที่สอดคล้องกันในจากไป(ในกรณีนี้ ทิศทางในขั้นตอนที่ 1 นั้น "ถูกต้อง") โปรดทราบว่ากรณีเป็นไปไม่ได้ เนื่องจากค่าการไหลทั้งหมดผ่านส่วนโค้งในเป็นเลขคู่${\displaystyle (i,j)}$${\displaystyle A_{3}}$${\displaystyle x_{ij}=2}$${\displaystyle G}$${\displaystyle i}$${\displaystyle j}$${\displaystyle j}$${\displaystyle i}$${\displaystyle x_{ij}=0}$${\displaystyle G}$${\displaystyle j}$${\displaystyle i}$${\displaystyle x_{ij}=1}$${\displaystyle A_{3}}$
5. เพิ่ม จำนวน สำเนาของส่วนโค้งแต่ละส่วนในกราฟ กราฟที่ได้จะเป็นกราฟคู่และสมมาตร${\displaystyle G}$${\displaystyle x_{ij}}$${\displaystyle A\cup A_{1}\cup A_{2}}$

เมื่อกราฟแบบผสมไม่ใช่กราฟคู่ และโหนดทั้งหมดไม่ได้มีดีกรีเป็นเลขคู่ กราฟนั้นสามารถแปลงเป็นกราฟคู่ได้

• ให้ G เป็นกราฟผสมที่มีการเชื่อมต่ออย่างแน่นหนาจงหาโหนดที่มีดีกรีคี่โดยไม่สนใจทิศทางของส่วนโค้ง และหาการจับคู่ที่มีต้นทุนน้อยที่สุด จากนั้นเพิ่มขอบจากผลการจับคู่ที่มีต้นทุนน้อยที่สุดลงในกราฟเพื่อสร้างกราฟคู่${\displaystyle \mathrm {G=\{V,E,A\}} }$${\displaystyle \mathrm {G'=\{V',E',A'\}} }$
• กราฟนี้เป็นกราฟคู่แต่ไม่สมมาตร และกราฟผสมแบบออยเลอร์เป็นกราฟคู่และสมมาตร จงแก้ปัญหาการไหลที่มีต้นทุนต่ำสุดเพื่อให้ได้กราฟสมมาตรซึ่งอาจไม่ใช่กราฟ คู่${\displaystyle G'}$${\displaystyle G''}$
• ขั้นตอนสุดท้ายคือการทำให้กราฟสมมาตรเป็นกราฟคู่ ติดป้ายกำกับโหนดที่มีดีกรีคี่ค้นหาวัฏจักรที่สลับกันระหว่างเส้นในเซตส่วนโค้งและเส้นในเซตขอบที่เริ่มต้นและสิ้นสุดที่จุดใน ส่วนโค้งในควรพิจารณาว่าเป็นขอบที่ไม่ระบุทิศทาง ไม่ใช่ส่วนโค้งที่ระบุทิศทาง${\displaystyle G''}$${\displaystyle V_{O}}$${\displaystyle A''\backslash A}$${\displaystyle E''}$${\displaystyle V_{O}}$${\displaystyle A''\backslash A}$

บทความที่ตีพิมพ์โดย Hua Jiang และคณะ ได้วางโครงร่างอัลกอริทึมทางพันธุกรรมเพื่อแก้ปัญหาบุรุษไปรษณีย์ชาวจีนแบบผสมโดยดำเนินการกับประชากร อัลกอริทึมนี้ทำงานได้ดีเมื่อเทียบกับอัลกอริทึมการประมาณค่าอื่นๆ สำหรับ MCPP ^{[ 16 ]}

• ปัญหาการกำหนดเส้นทางส่วนโค้งที่มีความจุ