Темы рефератов:
 
Бесплатные рефераты
 

 

 

 

 

 

     
 
Метад галін і межаў
     

 

Агульная апісанне метаду галін і межав арганізацыі повнага перабору магчымасцяв.
Рашэнне задачы аб коміваяжоры метадам галін і межав: асновная схема.
Няхай - канчатковае мноства і - матэрыяльна-значны функцыя на ім; патрабуецца
знайсці мінімум гэтай функцыі і элемент мноства, на якім гэты мінімум
дасягаецца.
Калі маецца тая ці іншая дадатковая інфармацыя пра мноства, рашэнне гэтай
задачы часам атрымовваецца ажыццявіць без повнага перабору элементав усяго мноства
M. Але часцей за
за всё повны перабор вырабляць прыходзіцца. У гэтым выпадку абавязкова взнікае
задача, як лепш перабор арганізаваць.
Метад галін і межав - гэта адзін з метадав арганізацыі повнага перабору. Ён
выкарыстовваецца і в дачыненні не завсёды, а толькі тады, калі выконваюцца спецыфічныя
дадатковыя вмовы на мноства M і минимизируемую на ім функцыю. А менавіта,
-
выкажам здагадку, што маецца матэрыяльна-значны функцыя j на мностве падмноства
мноства M з наступнымі дзвюма власцівасцямі:
для (тут - мноства, якое складаецца з адзінага элемента);
2) калі і, то.
У гэтых умовах можна арганізаваць перабор элементав мноства M з мэтай
мінімізацыі функцыі на гэтым мностве так:
разаб'ем мноства M на часткі (любым спосабам) і абярэм тую з яго частак W1, на
якой функцыя j мінімальная; затым разаб'ем на некалькі частак мноства W1 і
абярэм тую з яго частак W2, на якой мінімальная функцыя j; затым разаб'ем W2
на некалькі частак і абярэм тую з іх, дзе мінімальная j, і гэтак далей, пакуль не
прыйдзем да якога-небудзь одноэлементному мностве.
Гэта одноэлементное мноства называецца рэкордам.
Функцыя j, якой мы пры гэтым выбары карыстаемся, называецца ацэначнай.
Відавочна, што рэкорд не абавязаны даставляць мінімум функцыі f; аднак, вось якая
магчымасць взнікае скараціць перабор пры спрыяльных абставінах.
Апісаны вышэй працэс пабудовы рэкорды складався з паслядовных этапав, на
кожным з якіх фіксавалася некалькі мноствав і выбіралася затым адно з
іх. Няхай - падмноства мноства M, якія взніклі на перадапошнім этапе
пабудовы рэкорду, і хай мноства аказалася абраным з дапамогай ацэначнай
функцыі. Менавіта пры разбіцці і взнік рэкорд, які цяпер для
пэвнасці пазначым праз. Паводле сказанага вышэй,,; акрамя таго, па
вызначэнню ацэначнай функцыі,.
Выкажам здагадку, што; тады для любога элемента m мноства M, які належыць
мноства, будуць верныя няровнасці; гэта значыць, што пры повным пераборы
элементав з M элементы з ужо наогул не трэба разглядаць. Калі ж
няровнасць не будзе выканана, то все элементы з трэба паслядовна
паравнаць з знойдзеным рэкордам і як толькі адшукаецца элемент, які дае меншае
значэнне оптимизируемой функцыі, трэба ім замяніць рэкорд і працягнуць перабор.
Апошняе дзеянне...
     
 
     
Белорусские рефераты
 
Рефераты
 
Бесплатные рефераты
 

 

 

 

 

 

 

 
 
 
  Все права защищены. Перепечатка учебных материалов только с письменного разрешения администрации сайта.