حداقل با چندبار جابه‌جايي مي‌توان بشكه‌ها را جابه‌جا كرد؟ ... سؤال همراه با جواب
سؤال
يك شركت بشكه‌هايي از چهار ماده‌ي شيميايي مختلف به‌نام‌هاي A، B، C و D توليد و در انبارهاي خود ذخيره مي‌كند. اين شركت 4 انبار دارد كه در هر انبار 4 بشكه از انواع A، B، C و D موجود است (از هر ماده يك بشكه).
اين مواد شيميايي در صورتي كه با هم مخلوط شوند، خطرناك هستند. به‌همين دليل شركت تصميم دارد بشكه‌ها را بين اين انبارها طوري جابه‌جا كند كه در نهايت هر انبار حاوي 4 بشكه از يك نوع ماده‌ي شيميايي باشد.
براي اين كار از يك كاميون استفاده مي‌شود. اين كاميون مي‌تواند در هر بار جابه‌جايي حداكثر 2 بشكه را از يك انبار به يكي ديگر از انبارهاي شركت انتقال دهد. حداقل با چندبار جابه‌جايي مي‌توان اين كار را انجام داد؟
جواب
معلوم است كه كاميون از انبار 1 كه قرار است از حالت ABCD به حالت AAAA تبديل شود، حداقل دو بار خارج و حداقل دو بار به آن انبار وارد خواهد شد.
انبارهاي 2، 3 و 4 نيز چنين وضعيتي را دارند. بنابراين حداقل جابه‌جايي‌هاي لازم برابر 8 مي‌باشد.
اگر كاميون با الگوريتم زير حركت كند با 8 بار جابه‌جايي مي‌تواند به هدف برسد:
| 1. بشكه‌هاي BC را از انبار 1 به انبار 2، منتقل كند. |
| 2. بشكه‌هاي CC را از انبار 2 به انبار 3، منتقل كند. |
| 3. بشكه‌هاي BD را از انبار 3 به انبار 4، منتقل كند. |
| 4. بشكه‌هاي BB را از انبار 4 به انبار 2، منتقل كند. |
| 5. بشكه‌هاي AD را از انبار 2 به انبار 1، منتقل كند. |
| 6. بشكه‌هاي DD را از انبار 1 به انبار 4، منتقل كند. |
| 7. بشكه‌هاي AC را از انبار 4 به انبار 3، منتقل كند. |
| 8. بشكه‌هاي AA را از انبار 3 به انبار 1، منتقل كند. |