Локално търсене
За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. |
Локално търсене (на английски: local search) е термин от компютърните науки и в частност математическата оптимизация, с който се означава метаевристичен метод за решаване на изчислително сложни оптимизационни задачи. Методът може да се използва за задачи, чиято формулировка се свежда до откриване измежду набор от кандидат-решения на едно решение с максимална стойност по даден критерий. Алгоритмите за локално търсене претърсват пространството на решенията, като прилагат локални промени на параметрите, докато не се открие решение, което се смята за оптимално, или докато не бъде достигнат предварително определен времеви праг. Алгоритми за локално търсене се прилагат към множество изчислително сложни задачи от областта на изкуствения интелект, математиката, изследване на операциите, биоинформатиката, инженерните науки. Примери за алгоритми с локално търсене са:
- Задача за пътуващия търговец (travelling salesman problem);
- Задача за определяне на график на медицински сестри (nurse scheduling problem);
- Задача за покритие на върховете на граф (vertex cover problem);
- Задача за удовлетворимост на булева функция (boolean satisfiability problem);
- Метод за клъстеризация с използване на представителни обекти (k-медоиди), и други.
Описание
[редактиране | редактиране на кода]- Формулировка на задачата
Локалното търсене изисква задачата за решаване да се формулира като цел над пространство на търсене с критерии, по които трябва да се извърши многокритериална оптимизация. Например, задачата за търговския пътник изисква да се намери минималният по дължина маршрут, по който да се придвижва търговски пътник, като се обходят всички измежду дадено множество градове точно по веднъж и маршрутът завърши в началната точка. Тази задача се формулира над граф, като целта е да се открие такъв цикъл в графа, който съдържа всички възли на графа (максимизиращ критерий) с минимална дължина на цикъла (минимизиращ критерий).
Алгоритъмът за локално търсене започва от едно кандидат-решение и итеративно обхожда съседните решения в търсене на по-добро. Това е възможно, ако в пространството на търсене е въведена релацията за съседство. Например, едно покритие на граф е съседно на друго покритие, ако двете покрития се различават само по един връх (възел) на графа. В задачата за удовлетворимост на булева функция съседна на една логическа интерпретация, която удовлетворява дадена булева формула (т.е. задава такива стойности на променливите, при които булевата формула се изчислява като „истина“), е друга удовлетворяваща формулата интерпретация, която отново се различава от първата само по оценката на една от променливите на функцията. Една и съща задача може да има множество различни съседства, дефинирани над нея; локална оптимизация със съседства, които включват промяна на най-много k променливи на решението често се нарича k-opt.
Обичайно всяко кандидат-решение има повече от едно съседно решение; изборът кое да е следващото разгледано решение се прави на базата само на информация за решенията в съседство на текущото (откъдето идва терминът „локално търсене“). Когато изборът на съседно решение се прави само на базата на един, локално максимизиращ, критерий, тогава алгоритъмът се нарича метод на най-бързото изкачване (hill climbing. Когато в съответната област на съседство на решенията локалното търсене не открие по-добро решение от текущо, то алгоритъмът е достигнал локален оптимум, което само по себе си може да бъде проблем, ако това не е глобалният оптимум. Проблемът с локалните оптимуми се преодолява, като се правят многократни локални търсения с различни начални условия, или се въведе елемент на случайност, както при метода на симулираното закаляване (т.нар. стохастична оптимизация).
- Условия за край
Условието за край на алгоритъма може да бъде въведено ограничение по време. Друго обичайно условие за край е алгоритъмът да спре, ако текущо най-доброто открито решение не бъде подобрено в рамките на определен брой последващи итерации на алгоритъма.
Алгоритмите за локално търсене са с неопределена продължителност на действието, като валидно решение може да бъде генерирано по всяко време преди прекратяването на алгоритъма. Това са типично апроксимационни алгоритми, при които търсенето може да спре, дори ако най-доброто открито от алгоритъма решение не е оптималното. Причините могат да са или в невъзможност да се подобри текущото решение, или ако оптималното решение в пространството на решенията се намира далеч от областта на съседство, обхождана от алгоритъма.
За специални задачи е възможно да се дефинират области на съседство, които са много големи, потенциално в експоненциален мащаб. Ако в съседство от такъв порядък може ефективно да бъде открито решение, алгоритъмът се нарича large-scale neighborhood search algorithm.
Тази страница частично или изцяло представлява превод на страницата Local search в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.
ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни. |