مساله ۴۰. عبور سگ‌ها از پل
۶ تا سگ با وزن‌های ۱، ۲، ۴، ۶، ۸، و ۹ میخوان در شب از یه پل عبور کنن. همچنین ظرفیت پل ۱۴ کیلو هست و همه نمی‌تونن با هم عبور کنن. موقع عبور از پل هم باید یکیشون فانوس داشته باشه تا از رو پل نیافتن، ولی کلا یک فانوس بیشتر ندارن. وقتی هم که چندتا با هم عبور می‌کنن، مدت زمان عبور برابر با ماکزیمم وزن‌هاشونه.
کمترین زمانی که همشون بتونن عبور کنن چند دقیقه است؟
لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1705107724927967690
کمترین زمان ۲۴ دقیقه است.
در مرحله اول، ۱ و ۲ و ۴ از پل رد می‌شوند (۴ دقیقه). در مرحله دوم، ۱ برمی‌گردد (۱ دقیقه). در مرحله سوم، ۶ و ۸ از پل رد می‌شوند (۸ دقیقه).
در مرحله چهارم، ۲ برمی‌گردد (۲ دقیقه). و بالاخره در مرحله پنجم ۱ و ۲ و ۹ رد می‌شوند (۹ دقیقه).
برای بررسی اینکه این کمترین زمان است، می‌توان مساله را به صورت گرافی مدل کرد که هر حالت ممکن از اینکه چه کسانی در سمت مقصد هستند و فانوس کدام سمت است یک گره می‌سازیم. و اگر از حالتی به حالت دیگر بتوان رفت بین آن‌ها یال قرار می‌دهیم و وزن آن را طبق صورت مساله قرار می‌دهیم. سپس بین حالتی که همه سمت چپ هستند و فانوس سمت چپ هست و حالتی که همه سمت راست هستند و فانوس سمت راست است، کوتاهترین مسیر را با استفاده از الگوریتم دایکسترا پیدا می‌کنیم.