Zakázané prohledávání (Tabu search) je heuristická optimalizační metoda využívající metody lokálního prohledávání. Vytvořil ji Fred W. Glover v roce 1986 a formalizoval v roce 1989.
Lokální prohledávání vezme potenciální řešení problému a kontroluje jeho bezprostřední sousedy (tj. řešení, která jsou si až na několik málo drobností podobná) v naději, že najde lepší řešení. Metody lokálního prohledávání mají tendenci uvíznout v oblastech lokálních minim nebo na plošinách, kde je mnoho řešení stejně vhodných.
Zakázané prohledávání zvyšuje efektivitu lokálního prohledávání tím, že v prováděném kroku lze přijmout i horší návrh, pokud není k dispozici žádný lepší návrh, tj. když se hledání zasekne v lokálním minimu, tj. umožňuje přeskočení lokálního minima. Navíc jsou zavedeny zákazy (odtud termín tabu), zakazující návrat k dříve navštíveným řešením.
Implementace zakázaného prohledávání používá paměťové struktury, které popisují navštívená řešení nebo uživatelem zadané množiny pravidel, tj. pokud bylo potenciální řešení v určitém krátkodobém období již dříve navštíveno nebo pokud porušilo nějaké pravidlo, je označeno jako „tabu“ (zakázané), aby algoritmus tuto možnost opakovaně nezvažoval.
Reference
Optimalizace