موضوع مقاله: مسئله مسافر کانادایی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله مسافر کانادایی | مقدمه: به عبارت دیگر، گراف نازل شده‌است در حالی که گراف هنوز در حال کاوش است، و گره‌های طی می‌شوند حتی اگر آن‌ها کمکی برای رسیدن به مسیر نهایی نکنند. | ## بخش 1: مسئله مسافر کانادایی | این مسئله بهینه‌سازی توسط کریستوس پاپادیمیتریو و میهالیس یاناکاکیس به همراه مسائل گوناگون دیگر از سال ۱۹۸۹ مورد مطالعه قرار گرفته و معرفی شده‌است. اسم مسئله ظاهراً از گفتگوی برنامه‌نویسها کامپیوتری با راننده‌های کانادایی که از مشکل بارش برف که جاده‌ها را به‌طور تصادفی مسدود می‌کرد گرفته شده‌است. مقدمه فرض کنید که یک نقشه راه داده می‌شود که در آن چند جاده به همراه زمان گذشتن از آن جاده‌ها مشخص است. با این حال، این نقشه راه نامطمئن است، برخی از جاده‌ها ممکن است برای سفر در زمان‌های خاص نامناسب باشند و توسط برف مسدود شوند؛ و تنها پس از رسیدن به آخر جاده می‌توان نشان داد که به انتها رسیده‌است یا خیر. مسئله مسافر کانادایی یک تدبیر استراتژی سفر است که یک مسیر خوب را تضمین می‌کند با توجه به اینکه عدم قطعیت بر مسئله حاکم است. متغییرها در درجه اول، پنج پارامتر تعیین‌کننده تعداد متغیرهای مسئله مسافر کانادایی وجود دارد. اولین پارامتر، چگونگی ارزش گذاری مسیر یک سیاست برای یک مثال یا تحقق مشخص می‌شود. برای مسئله مسافر کانادایی، کار، به حداقل رساندن نسبت رقابتی مسیر می‌باشد، یعنی به حداقل رساندن تعداد دفعات، هر چقدر مسیر ایجادشده طولانی‌تر باشد، کوتاهترین مسیر را در تحقق داریم. پارامتر دوم، چگونگی ارزیابی یک سیاست با توجه به تحققهای مختلف همراه با یک مثال موردنظر می‌باشد. | ## بخش 2: مسئله مسافر کانادایی | در یک مسئله مسافر کانادایی باید به بررسی بدترین مورد و در SSPPR، به مورد متوسط پرداخت. پارامتر سوم محدود به نسخه‌های تصادفی بوده و در مورد فرضیه‌هایی در رابطه با توزیع تحققها و چگونگی نمایش تحققها در ورودی می‌باشد. در مسئله مسافر کانادایی تصادفی و مسئله یافتن کوتاهترین مسیر تصادفی مستقل از گره (i-SSPPR)، هر گره نامشخصی (یا هزینه) احتمال محقق شدن را دارد و حتی اینکه گره گراف، مستقل از محقق شدن دیگر گره‌ها می‌باشد. متغیر دیگر، عدم وجود فرضیه در مورد توزیع است، اما هر محقق را باید با احتمال غیرصفر مشخص کرد (مثل احتمال ۰٫۱ مجموعه گره‌های ،، احتمال ۰٫۲) که به آن مسئله یافتن کوتاهترین مسیر تصادفی توزیع می‌گوید و NP کامل است. اولین متغیر سخت‌تر از دومی است، چون مورد اول می‌تواند در فضای لگاریتمی، توزیعی را نشان دهد که دومی، در فضای خطی نشان می‌دهد. این مسئله را می‌توان در یک زمان چندجمله‌ای با کاهش آن تا یک فرایند تصمیم مارکو (Markov) با افق چندجمله‌ای، حل کرد. تعمیم مارکو، که تحقق گراف ممکن است روی تحقق بعدی تأثیر بگذارد، بسیار سخت‌تر است. در متغیرهای قدیمی CTP، عامل، وزن دقیق گره را از طریق رسیدن به رأس کناری، مشخص نمی‌کند. متغیر جدیدی اخیراً پیشنهاد شده که یک عامل توانایی سنسور راه دور را از هر مکانی روی تحقق دارد. | ## بخش 3: مسئله مسافر کانادایی | یک شکل مشخص و گروهی از اشکال غیرجهت‌دار را در نظر گرفت که می‌توانند با اضافه‌کردن یک یا چند گره از یک مجموعه خاص، ساخته شوند. به‌طور رسمی است؛ که E را گره‌هایی می‌گیریم که در گراف وجود دارد و F گره‌هایی است که ممکن است در گراف داشته باشیم. بعلاوه، یک ماتریس هزینه مورد نظر داریم، ω، که هزینه رفتن از رأس i به j می‌باشد و فرض کنید این گره، در تحقق باشد. به این مسئله آفلاین (off-line) می‌گویند چون الگوریتم چنین مسئله‌ای، اطلاعات کامل هندسی دارد. می‌گوییم که استراتژی برای رهگیری چنین شکلی، از تا E ادامه دارد، جایی که ، مجموعه توانی X را نشان می‌دهد. به عبارت دیگر، سیاست را براساس گره‌هایی محقق کنیم که در گراف هستند و گره‌هایی که در باشند. آن گره‌هایی که در شکل هستند، صرف نظر از بودن گره‌ها، به اضافه می‌شوند و از مجموعه گره‌های ناشناخته خارج می‌شوند. اگر به هدف برسیم، هزینه مسیر را بعنوان مجموع هزینه‌های گره‌های طی شده تعریف می‌کنیم. | ## جمع‌بندی | پاپادیمیتریو و یاناکاکیس اظهار داشتند که در این مسئله یک بازی دونفره (نظریه بازیها) داریم که بازیگران در هزینه مسیرهای مربوط به خود را رقابت می‌کنند و مجموعه گره توسط بازیگر دوم انتخاب می‌شود.