Paratroopers

جدولی mxn داريم که در برخی از خانه های آن درختی قرار گرفته است. در بالای هر ستون و در سمت چپ هر سطر تفنگی قرار گرفته است که با شليک کردن آن تفنگ تمام درختان موجود در آن سطر يا ستون نابود می شوند. شليک کردن هر کدام از تفنگ ها هزينه ای دارد. می خواهيم زيرمجموعه ای از اين تفنگ ها را شليک کنيم به طوری که تمام درختان قطع شوند و حاصل ضرب هزينه ها کمينه شود. (این مساله، یکی از مسائل مسابقه ی انتخابی دانشگاه امیرکبیر در سال 1385 بود. لینک مساله در سایت acm.zju.edu.cn)

ابتدا برای ساده تر کردن مساله، به جای کمينه کردن حاصل ضرب هزينه ها، لگاريتم حاصل ضرب هزينه ها را کمينه می کنيم. در نتيجه مساله تبديل می شود به: زيرمجموعه ای از اين تفنگ ها را انتخاب کنيد به طوری که تمام درختان را قطع کنند و حاصل جمع لگاريتم هزينه ها را کمينه شود. پس می خواهيم عبارت زير را کمينه کنيم:

و در انتها جواب مساله ی اصلی برابر خواهد بود با:

خوب، برای حل کردن اين مساله، گرافی به شکل زير می سازيم:

که در گراف بالا r1 … r6 متناظر با سطرها می باشند و c1 … c9 متناظر با ستون ها می باشند. از s به هر کدام از سطرها يالی وصل می کنيم که وزن اين يال برابر با لگاريتم هزينه ی تفنگ آن سطر می باشد، و از هر کدام از ستون به t يالی وصل می کنيم که وزن اين يال برابر با لگاريتم هزينه ی تفنگ آن ستون می باشد. همچنين بين ri و cj يالی به وزن بی نهايت متصل می کنيم در صورتيکه در مکان [i,j] جدول درختی موجود باشد.

همچنين عمل انتخاب تفنگ يک سطر را متناظر با حذف کردن يال بين s و آن سطر در نظر می گيريم و عمل انتخاب تفنگ يک ستون را متناظر با حذف کردن يال بين آن ستون و t در نظر می گيريم.

حالا انتخابی از تفنگ ها را در نظر بگيريد که تمام درخت ها را قطع کند. خاصيت اين انتخاب چيست؟ خاصيت اين انتخاب اين است که به ازای هر يال ri به cj (که متناظر با يک درخت می باشد) بايد حداقل يکی از يال های s به ri (که متناظر با تفنگ سطر می باشد) و cj به t (که متناظر با تفنگ ستون می باشد) حذف شده باشد (که متناظر با انتخاب شدن آن تفنگ می باشد). نتيجه ی اين عمل چيست؟ نتيجه ی اين عمل اين است که هيچ مسيری از s به t وجود نخواهد داشت که از اين يال ri به cj عبور کند (چون فقط يک مسير اين چنين داشتيم، و حال با حذف حداقل يک يال از آن، اين تنها مسير را هم از بين می بريم.)

پس اگر بخواهيم تمام درخت ها را از بين ببريم، نبايد هيچ مسيری بين s و t باشد.

بنابراين مساله ی ما تبديل شد به حذف کردن تعدادی از يال های گراف مذکور به طريقی که هيچ مسيری بين s و t نباشد و مجموع وزن های اين يال های انتخاب شده کمينه باشد. اين جمله شما را به ياد چه مساله ی مشهوری می اندازد؟

احتمالا اکثر شما با مساله ی مشهور Minimum Cut آشنا هستيد. اگر آشنا نيستيد:

مساله ی Minimum Cut: می خواهيم تعدادی از يال های يک گراف را حذف کنيم به طوری که هيچ مسيری بين مبدا و مقصد نباشد و مجموع هزينه های يال های حذف شده می نيمم باشد.

و اگر با روش حل اين مسال آشنا نيستيد، بايد عرض کنم که جواب اين مساله (کمترين هزينه) با جواب مساله ی Maximum Flow يکی می باشد. اگر با اين مساله و طريقه ی حل آن آشنا نيستيد، به لينک 1 و لينک 2 مراجعه کنيد.

بنابراين برای حل کردن مساله، پس از ساختن گراف مذکور، با يکی از الگوريتم های معروف Maximum Flow، جواب مساله را بدست می آوريم! به همين سادگی و زيبايي!