مسئله مسافر کانادایی: تفاوت میان نسخه‌ها

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

این [[مسأله بهینه سازی]] توسط [http://en.wikipedia.org/wiki/Christos_Papadimitriou Christos Papadimitriou] و [http://en.wikipedia.org/wiki/Mihalis_Yannakakis Mihalis Yannakakis] به همراه مسائل گوناگون دیگر از سال ۱۹۸۹ مورد مطالعه قرار گرفته و معرفی شده‌است. اسم مسأله ظاهرا از گفتگوی برنامه نویسها کامپیوتری با راننده‌های کانادایی که از مشکل بارش برف که جاده‌ها را به طور تصادفی مسدود می‌کرد سرچشمه گرفته شده‌است. نسخه تصادفی، که در آن هر یک از گره‌های آن با احتمال از مستقل بودن در گراف همراه شده‌است، توجه قابل ملاحظه‌ای در[[تحقیق در عملیات]] تحت نام [[مسأله یافتن کوتاهترین مسیر تصادفی با منابع]] (به [[زبان انگلیسی| انگلیسی]]: the Stochastic Shortest Path Problem with Recourse , به اختصار: SSPPR) داشته‌است.

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

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

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

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

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