בעיית הדוור הסיני

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Chinespostman 1.png

בעיית הדוור הסיני היא בעיה בתורת הגרפים, העוסקת בדוור, שבמסגרת תפקידו עליו לצאת מבית הדואר העירוני, לעבור על פני כל הרחובות בעיר, כדי לחלק מכתבים לדיירי רחובות אלה, ולחזור לבית הדואר העירוני. יש למצוא כיצד יעבור הדוור על כל הרחובות (הנפגשים בצמתים, שבהם אפשר לעבור לרחוב אחר) במסלול הקצר ביותר. במונחים של תורת הגרפים דורשת הבעיה למצוא את המסלול הסגור הקצר ביותר העובר על כל הקשתות של גרף ממושקל בלתי מכוון.

בעיה מקבילה בתורת הגרפים היא בעיית הסוכן הנוסע, שבה נדרש מסלול העובר על כל הצמתים שבגרף.

בעיית הדוור הסיני נוסחה על ידי המתמטיקאי הסיני מיי-קו קואן בשנת 1962, ושמה ניתן לה על ידי אלן גולדמן[1].

כאשר בגרף יש מסלול אוילרי, שהוא מסלול בגרף העובר בכל קשת בו בדיוק פעם אחת, מסלול זה הוא כמובן הקצר ביותר.

בגרף שבו יש מסלול אוילרי, כל הצמתים הם מסדר זוגי (כלומר בכל צומת עובר מספר זוגי של קשתות), ולכן כאשר בגרף אין מסלול אוילרי, יש בו צמתים בסדר אי-זוגי. על פי תוצאה בתורת הגרפים, מספר הצמתים הללו הוא זוגי. כדי לעמוד בתנאי הבעיה, יש לעבור פעמיים על קשתות היוצאות מצמתים אלה. לשם כך נכפיל קשתות המחברות בין שני צמתים מסדר אי-זוגי (צעד השקול למעבר פעמיים על אותה קשת), ובכך נהפוך את המסלול לאוילרי. בעת הכפלת הקשתות נבחר את אלה שאורכן הכולל הוא הקצר ביותר, ונקבל מסלול אוילרי הפותר את הבעיה.

וריאציות[עריכת קוד מקור | עריכה]

נחקרו גם וריאציות אחדות של הבעיה, שנמצאו כבעיות NP-שלמות[2]:

  • בעיית הדוור הסיני בגרף מעורב: בווריאציה זו, חלק מהקשתות מכוונות, כלומר ניתן לנוע בהן רק בכיוון אחד.
  • בעיית הדוור הסיני ב-k מסלולים: מציאת k מסלולים היוצאים כולם מצומת מסוימת, כך שכל קשת נכללת במסלול אחד לפחות. המטרה היא להוזיל את מחירו של המסלול היקר ביותר.
  • בעיית הדוור הכפרי: נתונה גם תת-קבוצה של צמתים. יש למצוא מסלול המילטוני שכולל לפחות את כל הצמתים הללו.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Chinese Postman Problem
  2. ^ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. A compendium of NP optimization problems. KTH NADA, Stockholm.