בעיית הדוור הסיני
בעיית הדוור הסיני היא בעיה בתורת הגרפים, העוסקת בדוור, שבמסגרת תפקידו עליו לצאת מבית הדואר העירוני, לעבור על פני כל הרחובות בעיר, כדי לחלק מכתבים לדיירי רחובות אלה, ולחזור לבית הדואר העירוני. יש למצוא כיצד יעבור הדוור על כל הרחובות (הנפגשים בצמתים, שבהם אפשר לעבור לרחוב אחר) במסלול הקצר ביותר. במונחים של תורת הגרפים דורשת הבעיה למצוא את המסלול הסגור הקצר ביותר העובר על כל הקשתות של גרף ממושקל בלתי מכוון.
בעיה מקבילה בתורת הגרפים היא בעיית הסוכן הנוסע, שבה נדרש מסלול העובר על כל הצמתים שבגרף.
בעיית הדוור הסיני נוסחה על ידי המתמטיקאי הסיני מיי-קו קואן בשנת 1962, ושמה ניתן לה על ידי אלן גולדמן[1].
כאשר בגרף יש מסלול אוילרי, שהוא מסלול בגרף העובר בכל קשת בו בדיוק פעם אחת, מסלול זה הוא כמובן הקצר ביותר.
בגרף שבו יש מסלול אוילרי, כל הצמתים הם מסדר זוגי (כלומר בכל צומת עובר מספר זוגי של קשתות), ולכן כאשר בגרף אין מסלול אוילרי, יש בו צמתים מסדר אי-זוגי. על פי למת לחיצות הידיים, מספר הצמתים הללו הוא זוגי. כדי לעמוד בתנאי הבעיה, יש לעבור פעמיים על קשתות היוצאות מצמתים אלה. לשם כך נכפיל קשתות המחברות בין שני צמתים מסדר אי-זוגי (צעד השקול למעבר פעמיים על אותה קשת), ובכך נהפוך את המסלול לאוילרי. בעת הכפלת הקשתות נבחר את אלה שאורכן הכולל הוא הקצר ביותר, ונקבל מסלול אוילרי הפותר את הבעיה.
וריאציות
נחקרו גם וריאציות אחדות של הבעיה, שנמצאו כבעיות NP-שלמות[2]:
- בעיית הדוור הסיני בגרף מעורב: בווריאציה זו, חלק מהקשתות מכוונות, כלומר ניתן לנוע בהן רק בכיוון אחד.
- בעיית הדוור הסיני ב-k מסלולים: מציאת k מסלולים היוצאים כולם מצומת מסוימת, כך שכל קשת נכללת במסלול אחד לפחות. המטרה היא להוזיל את מחירו של המסלול היקר ביותר.
- בעיית הדוור הכפרי: נתונה גם תת-קבוצה של קשתות במשקל מינימלי. יש למצוא מסלול מעגלי שכולל לפחות מעבר אחד על כל אחת מקשתות אלו (בנוסף למעבר אפשרי על קשתות נוספות).
ראו גם
קישורים חיצוניים
- בעיית הדוור הסיני, באתר MathWorld (באנגלית)
- Chinese Postman Problem
הערות שוליים
- ^ Chinese Postman Problem
- ^ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH NADA, Stockholm.
35122791בעיית הדוור הסיני