تعیین اولویت شاخه زنی برای متغیرهای عدد صحیح

اکثر سالورهایی که مسائل مرتبط با متغیرهای integer را حل می کنند، از الگوریتم شاخه و کران یا branch and bound استفاده می کنند (در صورتی که با این الگوریتم آشنایی ندارید می توانید با جستجو مقداری در مورد آن اطلاعات کسب کنید).
در این الگوریتم، در هر نقطه روی یک متغیر شاخه می زند. اینکه کدام متغیر برای شاخه زنی انتخاب شود، به صورت دیفالت توسط خود سالور انتخاب می شود. در صورتی که روی مسئله خود تسلط داشته باشید و به الگوریتم شاخه و کران اشراف داشته باشید، ممکن است متوجه شوید که مثلا در صورتی که اگر اول روی متغیر x شاخه بزنید، ممکن است روند الگوریتم صحیح تر و سریعتر ادامه پیدا کند، می توانید به این متغیر اولویت شاخه زنی دهید. این اولویت دهی یکی از ویژگی های متغیرها است که در توسط .prior مشخص می شود. مثال زیر نشان می دهد که ما به گمز دستور داده ایم که ابتدا متغیر x و سپس متغیر y(‘3’ و سپس متغیر z(i را در اولویت قرار دهد.

integer variables
x,y(j),z(i);
x.prior=1;
y.prior('3')=2;
z.prior(i)=3;

اینکه کدام متغیر باید اولویت اول باشد مسئله ای است که بسته به ساختار مسئله دارد. مثلا در مسائل مکانیابی منطقی تر است که y(k که متغیر احداث است در اولویت اول باشد و متغیر x که متغیر تخصیص است در اولویت دوم (در مکانیابی ابتدا تسهیل احداث شده و سپس نقاط تقاضا به آن تخصیص داده می شوند.)
با تشکر

گمزبوک

این مقاله برای شما مفید بود؟

مطالب مشابه

دیدگاهی دارید؟