مسئله مسافر کانادایی

در علوم کامپیوتر و نظریه گراف، مسئله مسافر کانادایی (به انگلیسی: Canadian Traveller Problem , به اختصار: CTP) یک کلیت از مسئله یافتن کوتاهترین مسیر در گراف‌ها است. به عبارت دیگر، گراف نازل شده‌است در حالی که گراف هنوز در حال کاوش است، و گره‌های طی می‌شوند حتی اگر آن‌ها کمکی برای رسیدن به مسیر نهایی نکنند.

این مسئله بهینه‌سازی توسط کریستوس پاپادیمیتریو و میهالیس یاناکاکیس به همراه مسائل گوناگون دیگر از سال ۱۹۸۹ مورد مطالعه قرار گرفته و معرفی شده‌است. اسم مسئله ظاهراً از گفتگوی برنامه‌نویسها کامپیوتری با راننده‌های کانادایی که از مشکل بارش برف که جاده‌ها را به‌طور تصادفی مسدود می‌کرد گرفته شده‌است. نسخه تصادفی، که در آن هر یک از گره‌های آن با احتمال از مستقل بودن در گراف همراه شده‌است، توجه قابل ملاحظه‌ای درتحقیق در عملیات تحت نام مسئله یافتن کوتاهترین مسیر تصادفی با منابع (به انگلیسی: the Stochastic Shortest Path Problem with Recourse , به اختصار: SSPPR) داشته‌است.

مقدمه

فرض کنید که یک نقشه راه داده می‌شود که در آن چند جاده به همراه زمان گذشتن از آن جاده‌ها مشخص است. با این حال، این نقشه راه نامطمئن است، برخی از جاده‌ها ممکن است برای سفر در زمان‌های خاص نامناسب باشند و توسط برف مسدود شوند؛ و تنها پس از رسیدن به آخر جاده می‌توان نشان داد که به انتها رسیده‌است یا خیر. مسئله مسافر کانادایی یک تدبیر استراتژی سفر است که یک مسیر خوب را تضمین می‌کند با توجه به اینکه عدم قطعیت بر مسئله حاکم است. پاپادیمیتریو و یاناکاکیس ثابت کردند که اگر تعدادی از جاده‌ها ممکن است مسدود شوند و ثابت نباشند، پس استراتژی ای مسئله از نوع PSPACE completeاست.

متغییرها

در درجه اول، پنج پارامتر تعیین‌کننده تعداد متغیرهای مسئله مسافر کانادایی وجود دارد. اولین پارامتر، چگونگی ارزش گذاری مسیر یک سیاست برای یک مثال یا تحقق مشخص می‌شود. در مسئله یافتن کوتاهترین مسیر تصادفی با منابع، هدف به حداقل رساندن هزینه مسیر می‌باشد (بعنوان مجموع کل مرزهای قیمت گره ضرب در تعداد دفعاتی که گره گرفته شد). برای مسئله مسافر کانادایی، کار، به حداقل رساندن نسبت رقابتی مسیر می‌باشد، یعنی به حداقل رساندن تعداد دفعات، هر چقدر مسیر ایجادشده طولانی‌تر باشد، کوتاهترین مسیر را در تحقق داریم.

پارامتر دوم، چگونگی ارزیابی یک سیاست با توجه به تحققهای مختلف همراه با یک مثال موردنظر می‌باشد. در یک مسئله مسافر کانادایی باید به بررسی بدترین مورد و در SSPPR، به مورد متوسط پرداخت. برای تحلیل مورد متوسط، باید توزیع پیشین را در تحققها مشخص کرد.

پارامتر سوم محدود به نسخه‌های تصادفی بوده و در مورد فرضیه‌هایی در رابطه با توزیع تحققها و چگونگی نمایش تحققها در ورودی می‌باشد. در مسئله مسافر کانادایی تصادفی و مسئله یافتن کوتاهترین مسیر تصادفی مستقل از گره (i-SSPPR)، هر گره نامشخصی (یا هزینه) احتمال محقق شدن را دارد و حتی اینکه گره گراف، مستقل از محقق شدن دیگر گره‌ها می‌باشد. حتی اگر این مسئله یک ساده‌سازی قابل توجه باشد، مسئله هنوز کلاس پی خواهد بود. متغیر دیگر، عدم وجود فرضیه در مورد توزیع است، اما هر محقق را باید با احتمال غیرصفر مشخص کرد (مثل احتمال ۰٫۱ مجموعه گره‌های الگو:۳٬۴،الگو:۱٬۲، احتمال ۰٫۲) که به آن مسئله یافتن کوتاهترین مسیر تصادفی توزیع می‌گوید و NP کامل است. اولین متغیر سخت‌تر از دومی است، چون مورد اول می‌تواند در فضای لگاریتمی، توزیعی را نشان دهد که دومی، در فضای خطی نشان می‌دهد.

پارامتر چهارم و آخر، چگونگی تغییر شکل گراف در طول زمان است. در CTP و SSPPR، تحقق ثابت می‌شود، اما مشخص نیست. در مسئله یافتن کوتاهترین مسیر تصادفی با منابع یا مسئله یافتن کوتاهترین مسیر مورد انتظار، تحقق جدیدی از توزیع بعد از هر مرحله از سیاست، انتخاب می‌شود. این مسئله را می‌توان در یک زمان چندجمله‌ای با کاهش آن تا یک فرایند تصمیم مارکو (Markov) با افق چندجمله‌ای، حل کرد. تعمیم مارکو، که تحقق گراف ممکن است روی تحقق بعدی تأثیر بگذارد، بسیار سخت‌تر است.

یک پارامتر بعدی، چگونگی کشف دانش جدید در تحقق است. در متغیرهای قدیمی CTP، عامل، وزن دقیق گره را از طریق رسیدن به رأس کناری، مشخص نمی‌کند. متغیر جدیدی اخیراً پیشنهاد شده که یک عامل توانایی سنسور راه دور را از هر مکانی روی تحقق دارد. در این متغیر، باید هزینه حرکت را بعلاوه هزینه عملیات سنسور به حداقل رساند.

تعریف رسمی

متغیر را از سال ۱۹۸۹ تعریف کردیم. هدف، به حداقل رساندن نسبت رقابتی در بدترین مورد است. باید با معرفی عبارات خاص شروع کرد. یک شکل مشخص و گروهی از اشکال غیرجهت‌دار را در نظر گرفت که می‌توانند با اضافه‌کردن یک یا چند گره از یک مجموعه خاص، ساخته شوند.

به‌طور رسمی ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$ است؛ که E را گره‌هایی می‌گیریم که در گراف وجود دارد و F گره‌هایی است که ممکن است در گراف داشته باشیم. می‌گوییم که $G\in {\mathcal {G}}(V,E,F)$ 'تحقق' طرح گراف است. بعلاوه، یک ماتریس هزینه مورد نظر داریم، ω، که $w_{ij}$ هزینه رفتن از رأس i به j می‌باشد و فرض کنید این گره، در تحقق باشد.

برای هر رأس v در V, $E_{B}(v,V)$ را گره مجاور با توجه به مجموعه B روی V می‌نامیم. بعلاوه، برای تحقق $G\in {\mathcal {G}}(V,E,F)$ , $d_{B}(s,t)$ را هزینه کوتاهترین مسیر به شکل s تا t بگیرید. به این مسئله آفلاین (off-line) می‌گویند چون الگوریتم چنین مسئله‌ای، اطلاعات کامل هندسی دارد. می‌گوییم که استراتژی $\pi$ برای رهگیری چنین شکلی، از $({\mathcal {P}}(E),{\mathcal {P}}(F),V)$ تا E ادامه دارد، جایی که ${\mathcal {P}}(X)$، مجموعه توانی X را نشان می‌دهد. هزینه $c(\pi ,B)$ استراتژی $\pi$ را با توجه به تحقق مخصوص $G=(V,B)$ تعریف می‌کنیم.

 Let $v_{0}=s,E_{0}=E$ and $F_{0}=F$.
 For $i=0,1,2,...$, define
   $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$,
   $F_{i+1}=F_{i}-E_{F}(v_{i},V)$, and
   $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$.
 If there exists a T such that $v_{T}=t$, then
  $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$, otherwise let $c(\pi ,B)=\infty$.

به عبارت دیگر، سیاست را براساس گره‌هایی محقق کنیم که در گراف ($E_{i}$) هستند و گره‌هایی که در ($F_{i}$) باشند. وقتی گامی را در گراف جلو می‌رویم، گره مجاور مکان جدید خود را خواهیم شناخت. آن گره‌هایی که در شکل هستند، صرف نظر از بودن گره‌ها، به $E_{i}$ اضافه می‌شوند و از مجموعه گره‌های ناشناخته $F_{i}$ خارج می‌شوند. اگر هدف هیچ وقت نائل نگردد، می‌گوییم که یک هزینه نامحدود داریم. اگر به هدف برسیم، هزینه مسیر را بعنوان مجموع هزینه‌های گره‌های طی شده تعریف می‌کنیم.

سرانجام، مسئله مسافر کانادایی را تعریف می‌کنیم.

با مثال CTP $(V,E,F,s,t,r)$، سیاستی $\pi$ وجود دارد که برای هر تحقق $(V,B)\in {\mathcal {G}}(V,E,F)$، هزینه $c(\pi ,B)$ سیاست،

دیگر بیش‌تر از r برابر بهینه آفلاین (off-line) $d_{B}(s,t)$ نیست.

پاپادیمیتریو و یاناکاکیس اظهار داشتند که در این مسئله یک بازی دونفره (نظریه بازیها) داریم که بازیگران در هزینه مسیرهای مربوط به خود را رقابت می‌کنند و مجموعه گره توسط بازیگر دوم انتخاب می‌شود.

پیچیدگی

تجزیه و تحلیل مسئله مسافر کانادایی در مورد پیچیدگی نشان می‌دهد که این مسئله از نوع PSPACEکامل (PSPACE-complete) باشد. اما همچنین در مورد اینکه این مسئله از نوع P-hard# باشد؛ بحث است. در هر صورت این بحث هنوز به نتیجه‌ای نرسیده‌است.

نسخهٔ تصادفی این مسئله هم در تحقیق در عملیات، به عنوان مسئله یافتن کوتاهترین مسیر تصادفی با منابع شناخته شده‌است.

جستارهای وابسته

• مسئله یافتن کوتاهترین مسیر
• پیمایش گراف

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Canadian Traveller Problem». در دانشنامهٔ ویکی‌پدیای انگلیسی.