У овом упутству ћете научити шта је алгоритам за враћање уназад. Такође ћете пронаћи пример приступа повраћају уназад.
Алгоритам повратног праћења је алгоритам за решавање проблема који користи грубу силу за проналажење жељеног резултата.
Приступ грубе силе искушава сва могућа решења и бира жељена / најбоља решења.
Израз враћање уназад сугерише да ако тренутно решење није погодно, вратите се и испробајте друга решења. Дакле, у овом приступу се користи рекурзија.
Овај приступ се користи за решавање проблема који имају више решења. Ако желите оптимално решење, морате се одлучити за динамичко програмирање.
Државно свемирско дрво
Стабло свемирског стања је стабло које представља сва могућа стања (решење или нерешење) проблема од корена као почетног стања до листа као завршног стања.
Државно свемирско дрво
Алгоритам враћања уназад
Бацктрацк (к) ако к није решење ретурн фалсе ако је к ново решење додај на листу бацктрацк решења (прошири к)
Пример приступа за враћање уназад
Проблем: Желите да пронађете све могуће начине како распоредити 2 дечака и 1 девојчицу у 3 клупе. Ограничење: Девојчица не би требало да буде на средњој клупи.
Решење: Укупно их има 3! = 6 могућности. Испробаћемо све могућности и добити могућа решења. Рекурзивно испробавамо све могућности.
Све могућности су:
Све могућности
Следеће стабло свемира стања приказује могућа решења.
Стабло држава са свим решењима
Апликације за поврат алгоритма
- Да бисте пронашли све Хамилтонове стазе присутне у графикону.
- Да бисте решили проблем Н Куеен.
- Решавање проблема у лавиринту.
- Проблем витезове турнеје.
