III. Пространство на търсене

Пространство на търсене

Ако се разрешава някакъв проблем, обикновено се търси някакво решение, което да бъде най-добро между останалите. Пространството на възможните решения (тоест обектите между които се намира желаното решение) се нарича пространство на търсене (също п ространство на състоянията). Всяка точка в пространството на търсене представя едно възможно решение. Всяко възможно решение може да бъде "отбелязано" чрез неговата стойност или според вида на проблема. Търси се решение, което е една точка (или повече) м ежду възможните решения - това е една точка в пространството на търсене.

Търсенето на решение тогава е еквивалентно на търсене за екстремум (минимум или максимум) в пространството на търсене. Пространството на търсене може да бъде напълно известно по време решаването на проблема, но обикновено се знаят само няколко точки от н его, генерират се други точки като процеса за намиране на решение продължава.

Пример за пространство на търсене

Проблемът е че търсенето може да бъде много сложно. Не се знае къде да се търси решение и от къде да се започне. Има много методи, как да се открие някое подходящо решение (не задължително най-доброто решение), примерно изкачването на вр ъх, търсене табу, симулирано закаляване и генетичен алгоритъм. Решението намерено чрез тези методи често се смята като добро решение, защото не винаги е възможно доказателство какъв е реалния оптимум.

Проблеми със сложност NP

Пример за сложни проблеми, които не могат да бъдат решени по "традиционен" начин, са проблемите с NP сложност.

Съществуват много задачи за които са известни бързи (полиномни) алгоритми. Съществуват също някои проблеми които е не възможно да се решат алгоритмично. За някои проблеми е доказано че са нерешими в полиномно време.

Но съществуват много важни задачи, за които е много трудно да се намери решение, но веднъж когато го има е лесно да се провери. Този факт е довел до NP-завършени проблеми. NP произлиза от неопределен полиноми (nondeterministic polynomial) и означа ва че е възможно "отгатване" на решението (чрез неопределен алгоритъм) и после да се провери, и двете в полиномно време. Ако се разполага с машина която може да прави предположения, би могло да се намери решение в разумно време.

Изучаването на NP-пълните проблеми за улеснение се ограничава до проблеми, където отговорът може да бъде Да или Не. Защото има задачи с усложнен изход, клас от проблеми наречен NP-трудни проблеми ще бъдат представени. Този клас не е така ограничен както класа на NP-завършените проблеми.

За NP-проблемите е характерно че някой прост алгоритъм за на намиране на решение е очевиден на пръв поглед - просто се опитват всички възможни ситуации. Но този алгоритъм е много бавен (обикновено O(2^n)) и дори за малко по-големи инстанции на проблема е непотребен като цяло.

За сега не се знае дали съществува по бърз алгоритъм. Доказващ или отхвърлящ това остава като голяма задача за новите изследователи (и може би това сте вие :-)). В наши дни много хора мислят, че такъв алгоритъм не съществува и така те търсят някакви алте рнативни методи - пример за тези методи са генетичните алгоритми.

Примери за NP проблеми са задоволствения проблем, проблема за търговския пътник или проблема за раницата. Изложение за NP проблеми може да се открие тук.