شکل روبهرو نشاندهندهی تعدادی خیابان و تقاطعهای بین آنهاست. خیابانها در جهت فلشها یکطرفه هستند. عرض هر خیابان هم بهاندازه یک ماشین است؛ یعنی ماشینها نمیتوانند از یکدیگر سبقت بگیرند. همچنین ماشینها نمیتوانند در محل تقاطعها بایستند. درنتیجه در هرلحظه هر ماشین فقط میتواند در یک خیابان قرار بگیرد. میدانیم که یک ایستگاه عوارضی در خیابان $B$ قرار دارد و از هر ماشین که عبور میکند مبلغ ۱۰ تومان دریافت میکند. نقطهی $A$ که در شکل دیده میشود یک پارکینگ است. ماشینهای با شمارهی ۱ تا ۶ پشت سر هم قرار دارند. میخواهیم این ماشینها را به پارکینگ $A$ منتقل کنیم. کمترین مجموع مقدار عوارض پرداختی چه قدر است تا این ماشینها به ترتیب شمارههایشان (اول ۱ بعد ۲، …) وارد پارکینگ شوند؟
پاسخ
گزینه (۳) درست است.
بهترین الگوریتم برای حرکت ماشینها به شکل زیر میباشد:
باتوجه به حالتبندی فوق مجموع کل عوارض برابر $60+10+10+20+40$ یعنی ۱۴۰ تومان بهدست آید.