Локална претрага (оптимизација)

У рачунарској науци, локално претраживање је хеуристички метод за решавање рачунарски тешких проблема оптимизације. Локална претрага се може користити за проблеме који се могу формулисати као проналажење решења које максимизира критеријум међу бројним кандидатима решењима. Локални алгоритми претраживања се крећу од решења до решења у простору кандидата решења (простору за претрагу) применом локалних промена, све док се не пронађе решење које се сматра оптималним или док не протекне временско ограничење.

Локални алгоритми претраживања се широко примењују на бројне тешке рачунарске проблеме, укључујући проблеме из рачунарске науке (посебно вештачке интелигенције), математике, операционих истраживања, инжењерства и биоинформатике. Примери алгоритама локалне претраге су WалкСАТ, алгоритам са 2 опције за проблем трговачког путника и Метрополис–Хестингсов алгоритам.

Иако је понекад могуће заменити опадање градијента за локални алгоритам претраге, опадање градијента није у истој породици: иако је то итеративни метод за локалну оптимизацију, он се ослања на градијент функције циља, а не на експлицитно истраживање простора решења .

Литература

• Баттити, Роберто; Мауро Брунато; Францо Масциа (2008). Реацтиве Сеарцх анд Интеллигент Оптимизатион. Спрингер Верлаг. ИСБН 978-0-387-09623-0. Архивирано из оригинала 2012-03-16. г. 
• Хоос, Х.Х. анд Стутзле, Т. (2005) Стоцхастиц Лоцал Сеарцх: Фоундатионс анд Апплицатионс, Морган Кауфманн.
• Вијаy Арyа анд Навеен Гарг анд Рохит Кхандекар анд Адам Меyерсон анд Камесх Мунагала анд Винаyака Пандит, (2004): Лоцал Сеарцх Хеуристицс фор к-Медиан анд Фацилитy Лоцатион Проблемс, СИАМ Јоурнал оф Цомпутинг 33(3).
• Јурај Хромкович: Алгоритхмицс фор Хард Проблемс: Интродуцтион то Цомбинаториал Оптимизатион, Рандомизатион, Аппроxиматион, анд Хеуристицс (Спрингер)
• Wил Мицхиелс, Емиле Аартс, Јан Корст: Тхеоретицал Аспецтс оф Лоцал Сеарцх (Спрингер)