Lower and upper competitive bounds for online directed graph exploration

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