Търсене с налучкване
Категория: Интернет
понеделник, 10 Февруари 2003 0:00ч
За да е възможно на всяка стъпка да изберем измежду k (kОN) налични възможности, трябва да разполагаме с функция int random(k), връщаща произволно цяло число между 0 и k-1. Тук няма да обсъждаме как и доколко е възможно да бъде съставена “прецизна” функция random() (подробна дискусия по проблема може да бъде намерена в [Knuth,1969]). Ще приемем, че стандартната реализация, съдържаща се в заглавния файл
Пример 1: В началото на почти всички курсове по алгоритми и структури от данни се разглежда задачата: Да се провери дали дадено число m се среща като елемент на даден масив a[n]. Тъй като числата в масива са подредени по произволен начин и не можем да приложим двоично търсене, се спираме на стандартния подход: сравняваме последователно всеки елемент a[i] (i = 1,2,...,n) с m. Този алгоритъм има средна сложност O(n), каквато е сложността му и в най-лошия случай. Едва ли би ни хрумнала идеята за прилагане на търсене с налучкване. Все пак един такъв алгоритъм би могъл да изглежда така:
Избираме произволен елемент a[i] от масива: i = random(n).
1) Ако a[i] == m, то сме намерили търсения елемент и приключваме.
2) Ако a[i] != m, повтаряме стъпка 1.
Забелязваме, че сложността и на този алгоритъм в средния случай е O(n) - вероятността на всяка стъпка да попаднем на търсения елемент е 1/n. Сложността в най-лошия случай обаче не може да се определи: Без да налагаме допълнителни ограничения на функцията random() не бихме могли да си гарантираме, че елементът, който търсим, някога ще бъде “уцелен”, независимо от това колко дълго работи програмата. Но каквато и функция random() да изберем, все едно, ще изпаднем в безкраен цикъл, ако елементът изобщо липсва. Горният алгоритъм не съобразява това и ще извършва проби до безкрайност. С последния проблем можем да се справим, например като въведем битов масив taken[n], инициализиран с нули, и променлива number, показваща колко различни елементи сме проверили до момента. Нека на текущата стъпка е бил избран елементът i, ако taken[i]==0 (т.е. елементът не е разглеждан до момента), повдигаме съответния бит taken[i]==1 и увеличаваме number с 1. Така, ако number стане равно на n, следва, че сме проверили всички елементи, и алгоритъмът приключва.
Пример 2: Аналогичен пример е задачата за проверка дали даден граф е Хамилтонов (т.е. съдържа Хамилтонов цикъл - такъв, който минава през всеки връх точно по веднъж). Едно възможно решение е да избираме произволни пермутации от върхове и да проверяваме дали някоя пермутация не образува Хамилтонов цикъл. Така можем да го намерим още на първата стъпка, но може и въобще да не го открием.
Двата примера трудно могат да ни убедят, че прилагането на алгоритъм за търсене с налучкване е по-добър подход от съответното систематично изследване. Забелязахме, че ако “нямаме късмет”, и при двата алгоритъма можем да попаднем в безкрайно търсене на решение. Въпреки това съществуват случаи, когато алгоритмите за търсене с налучкване могат да постигнат много добри резултати:
Пример 3: Всяка NP пълна или изискваща пълно изчерпване задача се решава с обхождане на дървото на кандидатите за решение. При методичното изследване, например търсене с връщане, се извършва претърсване в дълбочина, докато при търсенето с налучкване се изследват произволни клонове.
За примера от фиг. 1 нека решението на задачата е пътят D-D2-D6-D7, а поддървото с корен D1 е прекалено голямо (по брой върхове, а не по височина), за да може да бъде изследвано изцяло. В този случай алгоритъмът за търсене в дълбочина никога няма да намери решението, ако се насочи първо към поддървото на D1. От друга страна, нека приложим алгоритъм, който търси решението с налучкване по следния начин: започва от корена и на всяка стъпка избира произволен наследник, по който да продължи. Когато достигне до листо, проверява дали построеният път е решение и ако не е - започва от корена построяване на нов (произволен) път. Вероятността този алгоритъм да тръгне по върха D2 вместо по D1 e 0,5. При проверка на два кандидата тази вероятност е 0,75, при три кандидата е 0,875 (Защо?) и т.н., т.е. можем да очакваме с голяма вероятност, че ще открием решението още с първите няколко опита.
Изобщо основното предимство на алгоритмите, извършващи търсене с налучкване, е разнообразието от изследвани възможности. По този начин може да се избегне изследването на огромен брой еднотипни (и безперспективни) случаи, а това води до задоволителни резултати при много практически задачи. В следващите точки ще разграничим няколко основни типа търсене с налучкване и ще покажем някои техни приложения.
