Алгоритми/"Бектрекинг"

Бектрекинг је општа техника у алгоритмима која доводи у обзир све могуће комбинације како би решила проблем оптимизације. Бектрекинг је такође познат по називу прво-у-дубину или сепарација и евалуација. Имајући више знања о проблему, бинарно стабло претраге може бити упрошћено, како би се заобишли случајеви који не изгледају обећавајуће. Док је бектрекинг користан за тешке проблеме, за које не захтевамо ефикаснија решења, оно је лоше решење за свакодневне проблеме које друге технике много боље решавају. Међутим, динамичко програмирање и похлепи алгоритми се могу посматрати као оптимизација код бектрекинга, тако да општа техника бектрекинга је корисна за разумевање ових напреднијих концепата. Учење и разумевање бектрекинг технике пре свега даје добар "први корак унапред" до тих напреднијих техника, јер онда не морате да учите свих пар нових концепата одједном.

Метод бектрекинг Сагледати узимање решења као секвенцу избора За сваки избор, сагледати сваку опцију рекурзивно Вратити најбоље пронађено решење

Ова методологија је довољно генеричка да се може применити у већини проблема. Међутим, чак и да хоћемо да унапредимо бектрекинг алгоритам, идаље би се извршавао у експоненциалном времену пре него у полиноиалном времену. Уз то, анализирање тачног времена бектрекинг алгоритма може бити јако компликовано: уместо тога, дате су једноставније горње границе које нису чврсте.

Најдужа заједничка подсеквенца (исцрпна верзија)

Приметити да је решење проблема најдуже заједничке подсеквенце (НЗП) није довољно ефикасан. Међутим, корисно је за разумевање динамичког програмирања. НЗП проблем је сличан оном који Unix "diff" програм ради. Diff команда у Unix-у узима два текстуална фајла A и B, као улаз и излази разликују линију по линију од A и B. На пример, diff може показати да линије које недостају из фајла A треба додати у фајл B и линије приказане у фајлу A треба обрисати из фајла B. Циљ је добити листу додавања и брисања која би се могла искористити како бисмо трансформисали фајл A у фајл B. Превише конзервативно решење овог проблема би било да се све линије из фајла A обришу и да се све линије из фајла B додају. Док ово решава проблем на сиров начин, нас занима минималан број додавања и брисања како бисмо успешно достигли трансформацију. Сами размислите како бисте имплементирали решење овог проблема.

НЗП проблем, уместо што дели линије у текстуалним фајловима,се сматра и да проналази заједничке елементе између два различита низа. На пример,

let a := array {"The", "great", "square", "has", "no", "corners"}
let b := array {"The", "great", "image", "has", "no", "form"}

Желимо да нађемо најдужу подсеквенцу могућу од елемената које су пронашли и у низу a и у низу b у истом редоследу. НЗП од a и b је

"The", "great", "has", "no"

Сада посматрајмо две нове секвенце:

let c := array {1, 2, 4, 8, 16, 32}
let d := array {1, 2, 3, 32, 8}

Овде постоје две најдуже заједничке подсеквенце низа c и низа d:

1, 2, 32; and

1, 2, 8

Приметити да:

1, 2, 32, 8

није заједничка подсеквенца, јер је валидна подсеквенца само низа d, а не низа c (јер c има 8 пре 32). Тако можемо да закључимо да за неке случајеве, решења НЗП проблема нису јединствена. Ако бисмо имали више информација о доступним секвенцама, више бисмо волели једну подсеквенцу у односу на другу: на пример, ако су секвенце линије текстова у рачунарском програму, можда бисмо изабрали подсеквенцу која би задржала дефиницију функције.

На горњем нивоу, наш проблем је имплементирати следећу функцју:

// lcs -- враћа најдужу заједничку подсеквенцу од a и b
function lcs(array a, array b): array

која узима два низа као улаз и подсеквенце низа као излаз.

Како решавате овај проблем? Можете почети од тога да приметите да ли две секвенце почињу истом речју, онда најдужа заједничка подсеквенца увек саржи ту реч. Аутоматски можете да ставите ту реч у листу и тако бисте скратили проблем налажења најдуже заједничке подсеквенце остатка двеју листи. Тако је проблем постао мањи, што је добро, јер показује да постоји неки напредак.

Али ако две листе не почињу истом речју, онда једна, или обе од првог елемента из низа или првог елемемента из низа не припадају најдужој заједничкој подсеквенци. Али ипак, један од њих може бити. Како одређујете који ћете, ако неки јесте, да додате?

Решење можете посматрати у два смисла бектрекинг методе: Пробајте ова начина и видите! Свакако, два подпроблема су манипулисање мањим листама, како бисте знали да ће се рекурзија кад тад завршити. Чији год је резултат процеса најдужа заједничка подсеквенца је победник. Уместо што бисте "избацили" елемент брисањем из низа, користите парче низа. На пример, парче:

a[1,..,5]

представља елементе:

{a[1], a[2], a[3], a[4], a[5]}

низа као посебног низа. Ако Ваш програмски језик не подржава парчиће, онда морате да прођете почетак и/или крај индекса кроз цео низ. Овде су парчићи једино у форми:

a[1,..]

која када користите 0 као индекс првог елемента у низу, резултира да у низу парчића не постоји нулти елемент. (Тако, верзија овог алгоритма која нема парчиће мора проћи почетак валидног индекса и вредност би требало бити одузета од целе дужине низа како бисте добили дужину псеудо-парчади.)

// lcs -- враћа најдужу заједничку подсеквенцу од a и b
function lcs(array a, array b): array
  if a.length == 0 OR b.length == 0:
    // ако смо на крају било било које листе, онда је lcs празан
    
    return new array {}
  else-if a[0] == b[0]:
    // ако је почетни елемент исти у оба низа, онда је на lcs,
    // тако да само рекурзивно вратимо остатке обе листе.
    
    return append(new array {a[0]}, lcs(a[1,..], b[1,..]))
  else
    // не знамо која листу треба да одбацимо. Пробајте оба начина,
    // изаберите онај који је бољи.
    
    let discard_a := lcs(a[1,..], b)
    let discard_b := lcs(a, b[1,..])
    
    if discard_a.length > discard_b.length:
      let result := discard_a
    else
      let result := discard_b
    fi
    return result
  fi
end

Проблем најкраћег пута

Да се побољша Дајкстрин алгоритам у следећем поглављу.

Гранично претраживање

Ако сте већ нашли нешто "боље" и да ако сте на грани која никада неће бити добра као она коју сте већ видели, можете прекинути раније ту грану. (Пример за коришћење: збир бројева почевши од 1 2, а затим сваки број који следи је збир било којег броја плус проследњи број. Покажите побољшања перформанси..)

Ограничено 3-бојење

Овај проблем не личи непосредно на самог себе, тако да мора прбо бити уопштен. Методологија: Ако проблем не личи на самог себе, покушајте да га уопштите док не почне да личи.

Проблем трговачког путника

Овде је бектрекинг техника најбоље могуће решење.