مسئله مسافر کانادایی
در علوم کامپیوتر و نظریه گراف، مسئله مسافر کانادایی (به انگلیسی: Canadian Traveller Problem , به اختصار: CTP) یک کلیت از مسئله یافتن کوتاهترین مسیر در گراف‌ها است. به عبارت دیگر، گراف نازل شده‌است در حالی که گراف هنوز در حال کاوش است، و گره‌های طی می‌شوند حتی اگر آن‌ها کمکی برای رسیدن به مسیر نهایی نکنند.
این مسئله بهینه‌سازی توسط کریستوس پاپادیمیتریو و میهالیس یاناکاکیس به همراه مسائل گوناگون دیگر از سال ۱۹۸۹ مورد مطالعه قرار گرفته و معرفی شده‌است. اسم مسئله ظاهراً از گفتگوی برنامه‌نویسها کامپیوتری با راننده‌های کانادایی که از مشکل بارش برف که جاده‌ها را به‌طور تصادفی مسدود می‌کرد گرفته شده‌است. نسخه تصادفی، که در آن هر یک از گره‌های آن با احتمال از مستقل بودن در گراف همراه شده‌است، توجه قابل ملاحظه‌ای درتحقیق در عملیات تحت نام مسئله یافتن کوتاهترین مسیر تصادفی با منابع (به انگلیسی: the Stochastic Shortest Path Problem with Recourse , به اختصار: SSPPR) داشته‌است.
فرض کنید که یک نقشه راه داده می‌شود که در آن چند جاده به همراه زمان گذشتن از آن جاده‌ها مشخص است. با این حال، این نقشه راه نامطمئن است، برخی از جاده‌ها ممکن است برای سفر در زمان‌های خاص نامناسب باشند و توسط برف مسدود شوند؛ و تنها پس از رسیدن به آخر جاده می‌توان نشان داد که به انتها رسیده‌است یا خیر. مسئله مسافر کانادایی یک تدبیر استراتژی سفر است که یک مسیر خوب را تضمین می‌کند با توجه به اینکه عدم قطعیت بر مسئله حاکم است. پاپادیمیتریو و یاناکاکیس ثابت کردند که اگر تعدادی از جاده‌ها ممکن است مسدود شوند و ثابت نباشند، پس استراتژی ای مسئله از نوع "PSPACE complete"است.
در درجه اول، پنج پارامتر تعیین‌کننده تعداد متغیرهای مسئله مسافر کانادایی وجود دارد. اولین پارامتر، چگونگی ارزش گذاری مسیر یک سیاست برای یک مثال یا "تحقق" مشخص می‌شود. در مسئله یافتن کوتاهترین مسیر تصادفی با منابع، هدف به حداقل رساندن هزینه مسیر می‌باشد (بعنوان مجموع کل مرزهای قیمت گره ضرب در تعداد دفعاتی که گره گرفته شد). برای مسئله مسافر کانادایی، کار، به حداقل رساندن نسبت رقابتی مسیر می‌باشد، یعنی به حداقل رساندن تعداد دفعات، هر چقدر مسیر ایجادشده طولانی‌تر باشد، کوتاهترین مسیر را در "تحقق" داریم.
پارامتر دوم، چگونگی ارزیابی یک سیاست با توجه به "تحقق"های مختلف همراه با یک مثال موردنظر می‌باشد. در یک مسئله مسافر کانادایی باید به بررسی بدترین مورد و در SSPPR، به مورد متوسط پرداخت. برای تحلیل مورد متوسط، باید توزیع پیشین را در "تحقق"ها مشخص کرد.
پارامتر سوم محدود به نسخه‌های تصادفی بوده و در مورد فرضیه‌هایی در رابطه با توزیع "تحقق"ها و چگونگی نمایش "تحقق"ها در ورودی می‌باشد. در مسئله مسافر کانادایی تصادفی و مسئله یافتن کوتاهترین مسیر تصادفی مستقل از گره (i-SSPPR)، هر گره نامشخصی (یا هزینه) احتمال محقق شدن را دارد و حتی اینکه گره گراف، مستقل از محقق شدن دیگر گره‌ها می‌باشد. حتی اگر این مسئله یک ساده‌سازی قابل توجه باشد، مسئله هنوز کلاس پی خواهد بود. متغیر دیگر، عدم وجود فرضیه در مورد توزیع است، اما هر محقق را باید با احتمال غیرصفر مشخص کرد (مثل احتمال ۰٫۱ مجموعه گره‌های ،، احتمال ۰٫۲) که به آن مسئله یافتن کوتاهترین مسیر تصادفی توزیع می‌گوید و NP کامل است. اولین متغیر سخت‌تر از دومی است، چون مورد اول می‌تواند در فضای لگاریتمی، توزیعی را نشان دهد که دومی، در فضای خطی نشان می‌دهد.
پارامتر چهارم و آخر، چگونگی تغییر شکل گراف در طول زمان است. در CTP و SSPPR، "تحقق" ثابت می‌شود، اما مشخص نیست. در مسئله یافتن کوتاهترین مسیر تصادفی با منابع یا مسئله یافتن کوتاهترین مسیر مورد انتظار، "تحقق" جدیدی از توزیع بعد از هر مرحله از سیاست، انتخاب می‌شود. این مسئله را می‌توان در یک زمان چندجمله‌ای با کاهش آن تا یک فرایند تصمیم مارکو (Markov) با افق چندجمله‌ای، حل کرد. تعمیم مارکو، که "تحقق" گراف ممکن است روی "تحقق" بعدی تأثیر بگذارد، بسیار سخت‌تر است.
یک پارامتر بعدی، چگونگی کشف دانش جدید در "تحقق" است. در متغیرهای قدیمی CTP، عامل، وزن دقیق گره را از طریق رسیدن به رأس کناری، مشخص نمی‌کند. متغیر جدیدی اخیراً پیشنهاد شده که یک عامل توانایی سنسور راه دور را از هر مکانی روی "تحقق" دارد. در این متغیر، باید هزینه حرکت را بعلاوه هزینه عملیات سنسور به حداقل رساند.
متغیر را از سال ۱۹۸۹ تعریف کردیم. هدف، به حداقل رساندن نسبت رقابتی در بدترین مورد است. باید با معرفی عبارات خاص شروع کرد. یک شکل مشخص و گروهی از اشکال غیرجهت‌دار را در نظر گرفت که می‌توانند با اضافه‌کردن یک یا چند گره از یک مجموعه خاص، ساخته شوند.
به‌طور رسمی formula_1 است؛ که "E" را گره‌هایی می‌گیریم که در گراف وجود دارد و "F" گره‌هایی است که ممکن است در گراف داشته باشیم. می‌گوییم که formula_2 'تحقق' طرح گراف است. بعلاوه، یک ماتریس هزینه مورد نظر داریم، "ω"، که formula_3 هزینه رفتن از رأس "i" به "j" می‌باشد و فرض کنید این گره، در "تحقق" باشد.
برای هر رأس "v" در "V", formula_4 را گره مجاور با توجه به مجموعه "B" روی "V" می‌نامیم. بعلاوه، برای "تحقق" formula_2 , formula_6 را هزینه کوتاهترین مسیر به شکل "s" تا "t" بگیرید. به این مسئله آفلاین (off-line) می‌گویند چون الگوریتم چنین مسئله‌ای، اطلاعات کامل هندسی دارد. می‌گوییم که استراتژی formula_7 برای رهگیری چنین شکلی، از formula_8 تا "E" ادامه دارد، جایی که formula_9، مجموعه توانی "X" را نشان می‌دهد. هزینه formula_10 استراتژی formula_7 را با توجه به "تحقق" مخصوص formula_12 تعریف می‌کنیم. به عبارت دیگر، سیاست را براساس گره‌هایی محقق کنیم که در گراف (formula_22) هستند و گره‌هایی که در (formula_23) باشند. وقتی گامی را در گراف جلو می‌رویم، گره مجاور مکان جدید خود را خواهیم شناخت. آن گره‌هایی که در شکل هستند، صرف نظر از بودن گره‌ها، به formula_22 اضافه می‌شوند و از مجموعه گره‌های ناشناخته formula_23 خارج می‌شوند. اگر هدف هیچ وقت نائل نگردد، می‌گوییم که یک هزینه نامحدود داریم. اگر به هدف برسیم، هزینه مسیر را بعنوان مجموع هزینه‌های گره‌های طی شده تعریف می‌کنیم.
سرانجام، مسئله مسافر کانادایی را تعریف می‌کنیم. پاپادیمیتریو و یاناکاکیس اظهار داشتند که در این مسئله یک بازی دونفره (نظریه بازیها) داریم که بازیگران در هزینه مسیرهای مربوط به خود را رقابت می‌کنند و مجموعه گره توسط بازیگر دوم انتخاب می‌شود.
تجزیه و تحلیل مسئله مسافر کانادایی در مورد پیچیدگی نشان می‌دهد که این مسئله از نوع "PSPACEکامل" (PSPACE-complete) باشد. اما همچنین در مورد اینکه این مسئله از نوع P-hard# باشد؛ بحث است. در هر صورت این بحث هنوز به نتیجه‌ای نرسیده‌است.
نسخهٔ تصادفی این مسئله هم در تحقیق در عملیات، به عنوان مسئله یافتن کوتاهترین مسیر تصادفی با منابع شناخته شده‌است.
مسئله یافتن کوتاهترین مسیر
پیمایش گراف