مساله معکوس کمترین برشهای چند مبدا - چند مقصد با قید مقدار تحت فاصله همینگ تنگنایی وزندار

Abstract

G=(N,A,C) یک شبکه جهت دار و همبند با مجموعه رئوس N و کمان های A ، c بردارظرفیت و h مبدأ h s2 ,…, ,s1s و l مقصد l,…,t2,t1t ،و k داده شده است، در مساله معکوس کمترین برشهای چند مبدا - چند مقصد با قید مقدار، ما در پی α برش و مقدار ثابت کمترین برشهای جداکنندهی مبداها و α آن هستیم که با حداقل تغییرات ممکن بردار ظرفیت کمانها، برشهای داده شده با ظرفیت مقصدها از یکدیگر باشند. مهمترین ویژگی این مساله در مقایسه با سایر مسالههای معکوس کمترین برش، اضافه کردن قیدی است که در آن بایستی ظرفیت برشهای داده شده برابر مقدار مفروض بشود. در این مقاله، مساله بالا تحت فاصله همینگ تنگنایی وزندار مدل شده و یک الگوریتم چندجملهای قوی برای حل آن ارائه شده است. الگوریتم پیشنهادی برای بهدست آوردن جواب بهینه از جستجوی دودویی بهره برده و در هر تکرار یک مساله جریان شدنی را تحت قیودی مشخص حل میکند.