Лекция 2 - 12.10.2010

страницата се нуждае от дописване/преглеждане


Table of Contents

Informed search algorithms
Best-first search, A* search, heuristics


Припомняне от предишния път: Tree search

Информирано (евристично търсене) - търсене, при което имаме допълнителна информация за местонахождението на това, което търсим.

Best-first search: Идеята му се корени в използването на така наречена "оценъчна функция" (още "евристика"), която определя стойността ("desirability") на търсения възел. Чрез нея определяме най-"желания" възел и го обхождаме.

Връщаме се на примера с картата на Румъния. За примитивна оценъчна функция използваме разстоянието по права линия от града до целта (Букурещ). Примерно изпълнение на алгоритъма [pdf].

Свойства на лакомото (greedy) търсене [pdf].


A* search - представлява развитие на BeFS. В него оценъчната функция е двукомпонентна: освен евристиката, в нея като стойност се включва и натрупаната до момента "цена" на пътя. Евристиката е "приемлива" (admissible) - тя е не по-голяма от реалната цена на пътя. Пример за A* [pdf]. Намереният от A* път е оптимален - доказва се с допускане на противното. 2 доказателства [pdf]. Свойства на алгоритъма [pdf].

Още за admissible евристиките: това са такива евристики, които доближават отдолу реалната цена на пътя. Пример с играта 15: една такава евристика е броят на квадратчетата, които не са си на мястото. От това следва, че от две admissible евристики, тази, която дава не по-малка стойност от другата за всяко n, "доминира" над другата. На две евристики f_1 и f_2, една възможна доминантна евристика е max(f_1, f_2). Admissible евристики могат да се извлекат от точното решение на опростен вариант на проблема. Пример с travelling salesperson [pdf].


Алгоритми за локално търсене
Hill climbing, simulated annealing, нещо си

Iterative improvement algorithms - в много случаи, интересува ни крайната цел, а не пътят на достигането `и. [нещо си - slide change].
Пример: търговският пътник. Взимаме едно пълно решение, след което започнаме да правим промяна по двойки (разменяме два съседни възела в пътя). Оказва се, че много бързо - дори за големи графи - се достига много близо до оптималното решение (например в границата от 1%). Така бързо можем да се възползваме от варианти, които са _почти_ оптимални.
Пример: n-queens.Тук започваме с всичките 8 царици, разположени по дъската, и започваме да местим по една царица, стремейки се да намалим броя на конфликтите.

Hill-climbing algorithm [pdf] - движим се по една крива, търсейки максимума. Позволено ни е движение вляво и вдясно [б. а.: проблемът е представен с 2D-крива, но почти сигурно почти тривиално се представя в 3- и повече-мерни пространства]. Кривата има глобален (глобални) максимум(и), локални максимуми, плата, равни отсечки и т. н. [картинка в pdf-а]. С greedy подход най-често се оказваме в локален максимум - има различни стратегии за излизане от (локалната) безизходица и достигане в крайна сметка на глобалния максимум. Стратегиите, общо взето, са разновидности на рестартиране и на грешни стъпки.

Simulated annealing: излизаме от локалните максимуми чрез известен брой "неправилни" стъпки, но се стремим постепенно да намаляваме броя и размера им (размера на грешките, изразен в използваната метрика). Произлиза от контролирания процес на втвърдяване на металите в металургията, където се цели максимален размер на кристалите и минимални дефекти.

Local beam search: при него вместо 1 текущо състояние, използваме k на брой такива. При всяка следваща стъпка излъчваме най-добрите k наследници измежду всички наследници на текущите k възли. Това _не е същото_ като k паралелни търсения. [още работи - pdf].

Генетични алгоритми: стохастично local beam search, след което си създаваме наследници въз основа на двойки състояния [lolwut o.O] [трудноразбираема картинка в pdf-а]. Говорим за "гени" и за вероятност конкретен "ген" да участва в "кръстосване". Възможни са и "мутации" - промени на случаен принцип.

Непрекъснати пространства от състояния: Пример - искаме в Румъния да построим повече летища (не само в Букурещ). Как да ги разположим оптимално? [не чух как - нещо си за градиенти]


Constraint satisfaction problems (CSP)

При CSP търсим такова състояние, което удовлетворява определени ограничения. Не е толкова важно как ще стигнем до него - целим само да го намерим. Едно състояние се характеризира чрез (представлява) набор от променливи от някакво множество на допустими стойности, които променливи тестваме за удовлетворяване на ограниченията. Формализирането на такава задача дава възможност да използваме разглежданите досега алгоритми за нейното решаване.
Класическа задача: боядисване на карта - две съседни държави не трябва да бъдат в един и същи цвят. Същевременно искаме да минимизираме броя на цветовете. Пример: формално описание на условията, променливите и входните данни [pdf]. Решението на една такава задача представлява набор от присвоени стойности, удовлетворяващи поставеното условие (условия).

Constraint graph: ограниченията могат да бъдат описани абстрактно като граф: върховете са променливите, а ребрата са ограниченията върху тях.
Разновидности на CSP: дискретни променливи - крайни множества от допустими стойности(e.g. Boolean CSP), безкрайни МС(e.g. job scheduling - разпределение на работно време / времеви ресурс), непрекъснати променливи (пр. разпределение времеви интервали, в които са изпълнени дадени условия) [повече - в pdf-а].
Разновидности на ограниченията: унарни, бинарни (бинарни релации между променливите), ограничения от по-висок ред (higher-order), предпочитания (различна цена за различни стойности на променливите).
Пример: cryptarithmetic [преведете си го сами]: пъзели от сорта на:
T W O
+
T W O
——
F O U R [подробният пример - в pdf-а].

Още примери: разписание на лекции, конфигурация на система, оптимизация на логистика/спедиция, etc. И понеже светът е жесток и сложен, повечето проблеми имат ограничения от високи редове с променливи-реални числа.

Един възможен (тъп) подход: започваме от състояние, в което никоя променлива няма присвоена стойност. Функцията на наследниците присвоява стойност на неинициализирана променлива, което не противоречи на ограниченията. Ако не съществува такова решение, функцията фейлва. [още нещо - в pdf-а].

Backtracking search: [разни простотии в pdf-а]. Формално описание на алгоритъма [пак там]. Примерно изпълнение на алгоритъма за map colouring […].
Чрез подобрения може съществено да увеличим производителността на алгоритъма. Те идват под формата на стратегии за избор на променлива, която трябва да получи стойност на следващата стъпка, и на подходяща стойност за нея. Освен това се опитваме да предвидим неизбежните провали възможно най-рано и да се възползваме от същността на проблема.

Пример: map colouring -> minimum remaining values - избираме променливата, за която има най-малко възможни подходящи стойности. Като имаме държава/щат, за която има само един възможен цвят - оцветяваме я/го. Когато имаме различни променливи с минимални стойности, можем да приложим евристика за tie breaker - избираме променливата с най-голям брой наложени върху нея ограничения.
След като си изберем променлива: least constraint value - избираме тази стойност, която налага най-малко ограничения за възможните стойности на останалите променливи.
Trivia: с такива механизми става възможно да се реши (за разумно време?) задачата за 1000 кралици.

Forward checking: Идеята се състои в следене на броя валидни стойности за всяка оставаща променлива. Когато някоя променлива удари нулата - прекъсваме търсенето. Илюстрован пример [pdf].
Constraint propagation: техниката forward checking не може да открива провали в ранен стадий. Constraint propagation [по един неразбран все още от мен начин] върши това, като непрекъснато прилага върху съседните променливи новите ограничения, произтекли от нашия избор (откривайки бъдещи задънени улици?).
Arc consistency: проста форма на CProp - дали за всяка стойност на единия край на реброто има поне една валидна стойност за другия?

Структура на проблема: вършим неща като разделяне на проблема на по-малки независими проблемчета. Така сложността на проблема може да намалее експоненциално [за това последното не съм сигурен].
Друг подход е да опитаме да направим constraint графа дървовиден. Теорема за сложността в дървовиден граф [pdf, следващия път].

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License