Алгоритми с backtracking: Проблемът – реконструиране
Достига до добри решения , но е непредвидимо бавен, поради връщанията. Пример: подреждане на мебели в къща. спира се на различни етапи и се кара до изчерпване. Проблемът – реконструиране (приложение Физика, молекулярна Биология..)
Нека имам N точки: p1,p2…pN подредени по оста x.
Дадени разстоянията N(N – 1) / 2. Нека x1 = 0
Ако имахме дадени координатите, лесно можем да изчислим разстоянията. O(N² )
Нека дистанциите са дадени сортирано.
Задачата е: да се реконструират координатите на точките от дистанциите.
дадени: D ={1,2,2,2,3,3,3,4,5,5,5,6,7,8,10}
D e 15, N=6 нека x1 = 0 очевидно x6 = 10
най-голямата оставаща дист. е 8, следоват или x2=2 или x5=8 откъдето и да тръгнем все ще стигнем (връщанията от неуспех са равновероятни).
Нека x5=8. тогава x6-x5=2; x5-x1 = 8
7 е най-голямото разст. Или x4=7 или x2=3 (за да има разст. = 7 от
x2 до x6).
Ако x4 = 7 – проверяваме разст. до x6 и x5 и виждаме че ги има във вектора с разст.
Ако решим x2=3, то 3-x1=3; x5-3=5 - също са във вектора. Значи и това става.
Избираме едното за да продълж. Нека x4=7
Сега макс. разст. е 6, така че или x3=6 или x2=4. Проверяваме x3=6
не може. Проверяваме x2=4 – не може.Връщане назад.x4=7 отпадна. Сега опитваме x2=3
сега остава да изберем или x4=6 или x3=4. x3=4 е невъзможно. Значи остава x4=6:
остана x3=5, x1 = 0, x2 = 3, x3 = 5 x4 = 6 x5 = 8 x6 = 10 D = {}край!
ето граф на решенията:
*избраното решение води до разст. ,които липсват в D.
** върхът има само неуспяващи деца, следоват. този път да се изостави.
Поради backtracking анализът е вероятностен от… до... Ако няма връщане O(N ²logN),ако има – достигаме до O (N ²),
Сподели с приятели: |
