Searches

Question 1

Пълнота/Completeness

Answer 1

Дали винаги намира решение, ако има такова

Question 2

Greedy search

Answer 2

Избира най-доброто следващо състояние. Оценъчната функция често е евристичната. Работят бързо, но не оптимално.

Question 3

Предимства на Best First Search

Answer 3

• Бързина: По-бърз от БФС, ДФС, защото се фокусира върху по-обещаващите пътища
• Ефективен по памет: По-малко от БФС, защото не пази всички разклонения на пътя.

Question 4

Недосатъци на Best First Search

Answer 4

• Не гарантира оптимално решение: Може да пропусне най-добрия път, тъй като следва пътя, който в момента изглежда най-добър, без да разглежда алтернативи.
• Зависи от евристиката: Качеството на решението и ефективността на търсенето силно зависят от избраната евристична функция.
• Риск от зацикляне: В графи с цикли алгоритъмът може да зацикли, особено ако няма механизъм за откриване и предотвратяване на повторно посещение на вече посетени възли.

Question 5

Примери за Uninformed Cost Search/Blind Search

Answer 5

Dijkstra, BFS, DFS, Iterative Deepening Search

Question 6

Информирано търсене

Answer 6

Имат информация за целта, по-ефективни са имат евристична функция

Question 7

Beam search

Answer 7

Пази най-добрите l състояния в приоритетна опашка. O(n) по време и памет, може да не намери оптимално решение, може да отреже решението

Question 8

Предимства на Beam Search

Answer 8

• Ефективно използване на памет: Beam Search ограничава броя на възлите, които се съхраняват и разглеждат, което води до по-ниска консумация на памет в сравнение със стандартния BFS.
• Скорост: Ограничаването на броя на възлите, които се разширяват, може значително да ускори търсенето, особено в големи пространства на търсене.
• Подходящ за намиране на добри решения в големи пространства на търсене: Често намира добри, ако не и оптимални решения, без да разглежда цялото пространство на търсене.

Question 9

Недостатъци на Beam Search

Answer 9

• Не гарантира оптималност: Beam Search не гарантира намирането на най-доброто или най-краткото решение, тъй като много пътища се отхвърлят в процеса на търсене.
• Чувствителност към ширината на лъча: Резултатите от Beam Search могат значително да варират в зависимост от избраната ширина на лъча; твърде малък лъч може да пропусне важни пътища, докато твърде голям лъч увеличава изчислителната натовареност.
• Възможност за зацикляне или пропускане на решения: В някои случаи, алгоритъмът може да зацикли или да пропусне валидни решения, особено ако най-обещаващите възли не водят към целта.

Question 10

Алгоритми за informed search

Answer 10

Beam search

Question 11

Евристична функция

Answer 11

Функция, която оценява колко добро е дадено състояние - колко е близо до финалното. Функцията трябва да е бърза и да ни насочва обхождането на кои върхове би увеличило вероятността да стигнем до финално състояние

Question 12

Консистентна евристика

Answer 12

По-малка или равна за всяко следващо състояние от предишното и в целевите състояния =0

Question 13

Приемлива евристика

Answer 13

<= от реалната цена на състоянието

Question 14

Beam search локално или глобално търсещ

Answer 14

Локално

Question 15

Пълен ли е Beam Search

Answer 15

Не

Question 16

Hill climbing

Answer 16

beam search l = 1. Използва случайност за избягване на локални екстремуми. Избираме след колко итерации да спре.

Question 17

Hill climbing локално или глобално търсещ

Answer 17

Локално

Question 18

Пълен ли е Hill Climbing

Answer 18

No

Question 19

A*

Answer 19

Избягва твърде скъпи пътища.
f(n) = g(n) + h(n)
f(n) - приближение на цената на пътя до n
g(n) - цената на пътя до сега
h(n) - приближение на цената до n

Question 20

Предимства на A*

Answer 20

• Оптималност: A* гарантира намирането на най-краткия път, ако използваната евристика е допустима (никога не надценява истинската стойност).
• Пълнота: A* ще намери решение, ако такова съществува, при условие че разполага с достатъчно памет.
• Ефективност: При правилна евристика, A* е по-ефективен от други търсещи алгоритми като чисто BFS или DFS.

Question 21

Недостатъци на A*

Answer 21

• Зависимост от евристиката: Качеството и ефективността на A* зависят силно от избраната евристична функция.
• Използване на памет: Може да изисква значително количество памет, особено в големи пространства на търсене, тъй като запазва всички разглеждани възли в паметта.
• Изчислително изискване: Въпреки че е по-ефективен от други алгоритми за търсене, A* все още може да бъде изчислително интензивен, особено в сложни пространства на търсене с много възли.

Question 22

Каква евристика използва A*

Answer 22

Дистанцията до текущото състояние

Question 23

Пълен и оптимален ли е A*

Answer 23

Пълен и оптимален е

Question 24

Iterative deepening A*

Answer 24

Използва A* за оценка като място, до което да спре да разширява

Question 25

Simulated Annealing

Answer 25

Случайно избрани промени с вероятностна функция, която позволява и по-лоши ходове с цел избягване на локални максимуми. Вероятността за приемане на по-лоши ходове намалява постепенно по време на изпълнението на алгоритъма. Склонен да избягва локални максимуми.

Question 26

На какво прилича Genetic algorithm

Answer 26

На Beam Search - пази няколко възможни решения

Question 27

Оптимизира ли Алфа-Бета прюнинг по памет и време

Answer 27

По време оптимизира, но по памет не защото така или иначе в даден момент ще стигне максималната дълбочина