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

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

مقدمه

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

متغییرها

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

پیچیدگی

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