I.9. Пространство на състоянията – основни понятия и задачи
I. Обща част · Тема 9 · Подготовка по конспекта на СУ / ФМИ № 19, 2026/2027
Обхват от конспекта
Пространство на състоянията – основни понятия и задачи. Формулировка на задачата за търсене на път до определена цел. Основни стратегии за неинформирано търсене. Методи за информирано търсене на път до определена цел.
Цел на подготовката
Да можеш самостоятелно да обясниш понятията и връзките между тях, да дадеш собствен пример и да приложиш изброените подходи в задача.
Примерна писмена разработка
Авторски образец за подготовка по тази тема. Не е официален отговор, утвърден от СУ, и не задава задължителен обем или схема за оценяване. Чети го за разбиране; упражнявай възпроизвеждане със собствени примери и сверявай с пълния обхват на конспекта.
Формулиране на задачата
Пространството на състоянията е множество от възможни състояния и допустими преходи между тях. Задача за търсене се задава чрез начално състояние, приложими действия и модел на преход, тест за цел и цена на път. Решението е последователност от действия, водеща до цел. Състоянието описва ситуация, а възелът в дървото на търсене съдържа и пътна информация: родител, действие, дълбочина и натрупана цена. Едно състояние може да бъде достигнато по няколко пътя.
Алгоритъмът поддържа граница от възли за разглеждане. При графово търсене се следят вече достигнатите състояния, за да се ограничат циклите и повторенията. Оценката включва пълнота — намира ли решение, ако съществува; оптималност — намира ли решение с минимална цена; време и памет. Тези свойства изискват уточняване на разклоненост, цени и начин за обработка на повторни състояния.
Неинформирано търсене
Търсенето в ширина използва FIFO граница и разглежда пътищата по дълбочина. При крайна разклоненост е пълно за решение на крайна дълбочина и е оптимално по брой стъпки при еднаква цена. Паметта му може да е експоненциална в дълбочината. Търсенето в дълбочина използва стек, пази по-малка граница, но може да попадне в безкраен клон и не гарантира оптимално решение. Ограничаването по дълбочина отстранява безкрайното спускане, но може да пропусне по-дълбока цел. Итеративното задълбочаване повтаря ограниченията и комбинира малка памет с пълнота при крайна разклоненост.
Търсенето с равномерна цена избира най-малката натрупана цена g(n), а не най-малката дълбочина. Оптималността и пълнотата му се формулират при неотрицателни цени и подходящи допълнителни условия; обичайна достатъчна предпоставка за пълнота в безкрайни пространства е положителна долна граница на цената на действие. Целта се приема при изваждане на подходящия минимален възел, а не просто при първото ѝ генериране.
Информирано търсене
Евристиката h(n) оценява оставащата цена до целта. Алчното търсене използва h(n) и може да избере привидно близка, но скъпа цел. A* използва f(n)=g(n)+h(n). Допустима евристика не надценява истинската минимална оставаща цена. Съгласуваната евристика удовлетворява h(n)≤c(n,n′)+h(n′) за всеки преход и обичайно h(goal)=0. Съгласуваността е достатъчна за стандартното графово A* без повторно отваряне; само допустимост може да изисква отваряне отново при намерен по-добър път.
При движение по четири посоки с единична цена Манхатънското разстояние е естествена долна оценка, ако препятствията могат само да удължат пътя. Евристиката трябва да съответства на допустимите действия. Главният извод е, че формулирането на състоянията и доказването на свойствата на стратегията са толкова важни, колкото реализацията на границата.
Литературна опора
За сверяване с литературата от конспекта: позиции 8 в библиографията. Допълнително: Russell и Norvig — Artificial Intelligence: A Modern Approach (допълнителен източник извън библиографията на СУ).
Уроци за четене
- Пространство на състоянията и задача за път
- Неинформирано търсене — BFS, DFS и равномерна цена
- Ограничена дълбочина и итеративно задълбочаване
- Информирано търсене — евристика, greedy и A*
Учебник и справочник по тема I.9 — Нишева и Шишков (1995), официален източник № 8; точни страници и ред за четене.
Литература
Библиографски сведения и източници · Официален конспект. Конкретните раздели и страници ще се посочват към всеки разработен урок.
Примери и упражнения
Всеки урок има самостоятелна задача с четири отговора за самопроверка.
Писмена разработка и устни въпроси
Формулировката на темата може да служи като заглавие за тренировъчна писмена разработка, а подточките — като контролен списък за обхвата. Следният план е учебна препоръка, не официална схема за оценяване на СУ:
- Въведение: предмет, предназначение и място на темата.
- Точни определения, означения и основни понятия.
- Последователно изложение на подточките от конспекта и връзките между тях.
- Собствен пример, схема, алгоритъм или заявка според темата; обосновка на избора.
- Важни свойства, ограничения, сравнения и типични грешки.
- Кратко обобщение.
Опорният план е за преговор. Развитият отговор трябва да обяснява и обосновава, а не само да изброява термини. По конспекта писменият изпит включва два въпроса; не е уточнено как точно ще бъде формулиран билетът. При конкретен въпрос се води по неговото условие. Няма потвърдено изискване за определен брой страници.