Кіріспе

Ішкі проблемалардың оңтайлы емес шешімдерін жою арқылы оңтайландыру. Тармақталу және шектеу (ТШ, ТШБ немесе ТнБ) – оңтайландыру мәселелерін кішірек ішкі проблемаларға бөліп, оңтайлы шешімді қамти алмайтын ішкі проблемаларды жою үшін шектеу функциясын қолдану арқылы шешу әдісі. Бұл дискретті және комбинаторлық оңтайландыру, сондай-ақ математикалық оңтайландыру проблемалары үшін алгоритмдік дизайн парадигмасы. Тармақталу және шектеу алгоритмі – күй кеңістігін іздеу арқылы кандидат шешімдерді жүйелі түрде санаудан тұрады: кандидат шешімдер жиынтығы толық жиынтығымен тамырланған ағаш құрайды деп есептеледі. Алгоритм осы ағаштың тармақтарын зерттейді, олар шешім жиынтығының ішкі жиынтығын көрсетеді. Тармақтың кандидат шешімдерін санап шығудан бұрын, ол оңтайлы шешімнің жоғарғы және төменгі бағаланған шектерімен тексеріледі және егер ол алгоритмге дейін табылған ең жақсы шешімнен жақсы шешім бере алмаса, жойылады. Алгоритм іздеу кеңістігінің аймақтары мен тармақтарының төменгі және жоғарғы шектерін тиімді бағалауға байланысты. Егер шектеулер болмаса, алгоритм толық іздеуге айналады. Бұл әдіс алғаш рет 1960 жылы Аилса Лэнд және Элисон Дойг Лондон экономика мектебінде Британдық мұнай компаниясының қолдауымен дискретті бағдарламалау бойынша зерттеу жүргізген кезде ұсынды және NP қиын оңтайландыру мәселелерін шешу үшін ең көп қолданылатын құралға айналды.

Шолу

Бранш және байланған алгоритмнің мақсаты – белгілі бір S рұқсат етілген немесе кандидаттық шешімдер жиынтығының ішінде объективті функция деп аталатын f(x) нақты бағаланған функцияның мәнін барынша жоғарылату немесе азайту арқылы x мәнін табу. S жиынтығы іздеу кеңістігі немесе мүмкін болатын аймақ деп аталады. Осы бөлімнің қалған бөлігі f(x) функциясын барынша азайту қажет деп есептейді; бұл болжам жалпылықты жоғалтпайды, себебі f(x) функциясының ең жоғары мәнін табу үшін оның ең төменгі мәнін табу жеткілікті. B&B алгоритмі екі принцип бойынша жұмыс істейді:

Ол іздеу кеңістігін рекурсивті түрде кішірек кеңістіктерге бөледі, содан кейін f(x) функциясын осы кішірек кеңістіктерде азайтады; мұндай бөлу тармақталу деп аталады. Тек тармақталу ғана кандидаттық шешімдерді тізімдеп, оларды тексерумен бірдей болар еді. Күшпен іздеудің тиімділігін арттыру үшін B&B алгоритмі іздеуге тырысатын ең төменгі мәннің шектерін қадағалайды және осы шектеулерді пайдаланып іздеу кеңістігін "қырқуға" қолданады, яғни оңтайлы шешімді қамтымайтынын дәлелдей алатын кандидаттық шешімдерді жояды. Бұл принциптерді нақты оңтайландыру мәселесі үшін нақты алгоритмге айналдыру үшін кандидаттық шешімдер жиынтығын көрсететін дерек құрылымы қажет. Мұндай көрсету мәселенің мысалы деп аталады. I мысалының кандидаттық шешімдер жиынтығын SI арқылы белгілейік. Мысал көрсетуі үш операциямен бірге келуі керек:

branch(I) – SI жиынтығының әрқайсысы кіші жиынтығын көрсететін екі немесе одан көп мысалдарды жасайды. (Көбінесе, алгоритмнің бірдей кандидаттық шешімді екі рет қарауын болдырмау үшін кіші жиынтықтар бөлек болады, бірақ бұл міндетті емес. Дегенмен, SI жиынтығындағы оңтайлы шешім кем дегенде бір кіші жиынтықта болуы керек.) bound(I) – I арқылы көрсетілген кеңістіктегі кез келген кандидаттық шешімнің мәнінің ең төменгі шегін есептейді, яғни, барлық x ∈ SI үшін bound(I) ≤ f(x). solution(I) – I жалғыз кандидаттық шешімді көрсететінін анықтайды. (Егер көрсетпесе, операция SI жиынтығынан кез келген мүмкін шешімді қайтаруы мүмкін.) Егер solution(I) шешімді қайтарса, онда f(solution(I)) бүкіл мүмкін шешімдер кеңістігіндегі оңтайлы объективті мәннің ең жоғарғы шегін береді. Осы операцияларды пайдалана отырып, B&B алгоритмі тармақталу операциясы арқылы құрылған мысалдар ағашы арқылы жоғарыдан төменге рекурсивті іздеуді жүргізеді. I мысалын қарағанда, ол bound(I) қазіргі ең жоғарғы шекке тең немесе одан үлкен екенін тексереді; егер солай болса, I іздеуден қауіпсіз түрде шығарылуы мүмкін және рекурсия тоқтатылады. Бұл қырқу қадамы әдетте осыған дейін қарастырылған барлық мысалдар арасындағы ең төменгі ең жоғарғы шекті сақтайтын жаһандық айнымалыны қолдану арқылы жүзеге асырылады.

Жағдайдың жақсаруы

When is a vector of , бұтақтап іздеу және байлау алгоритмдері интервалдық талдау және шектеу техникаларымен үйлестіріліп, жаһандық минимумның сенімді шекараларын табуға мүмкіндік береді.

Басқа алгоритмдермен байланысы

Нау және басқалар тармақтап іздеу және шектеу әдісінің жалпылама нұсқасын ұсынады, ол A*, B* және альфа-бета іздеу алгоритмдерін де қамтиды.