Common Questions

Question 1

Кои са двете условия (съответно при дървета и при графи с цикли), на които трябва да отговаря евристичната функция, за да може A* да е оптимален?

Answer 1

Дървета
- h(N) ≤ c(P, N) + h(P)
P е родител на N, h е евристичната функция, а c(P, N) цената на прехода от P към N.
# Графи
- Евристичната функция не трябва никога да надценява действителната минимална цена от целевия до финалния връх.
- h(N) ≤ h(N), където h(N) е истинският минимален разход от N до целевия възел.

Question 2

Ако имаме две приемливи евристични функции, как можем да определим, коя е по-добра от тях?

Answer 2

h2(n) ≥ h1(n) for all n
Given any admissible heuristics ha, hb,
h(n) = max(ha(n), hb(n)) is also admissible and dominates ha
, hb

1. Точност на Евристиката:
   
   • по-близка до истинската минимална стойност, без да я надценява
2. Брой Разглеждани Възли:
   
   • Ако една евристична функция води до по-малък брой разглеждани възли от друга преди намирането на решение, тя се счита за по-ефективна
3. Сложност на Изчисленията
4. Консервативност и Оптимизъм:
   
   • Консервативните евристики обикновено са по-близки до реалната стойност и водят до по-малко изследване, но могат да пропуснат някои оптимални пътища. Оптимистичните евристики могат да изследват повече пътища, което увеличава шанса да намерят оптималния път, но и увеличава общото време за изчисление.

Изборът на “по-добрата” евристична функция зависи от спецификата на проблема и от баланса между точността на оценката и изчислителната ефективност.

Question 3

Какъв е най-големият недостатък на A*?

какво оптимизира IDA*

Answer 3

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

Question 4

Constraint satisfaction problem

Answer 4

Състояние - променливи X_i състойности от домейна D_i (всяко поле си има домейн)
Целеви тест - дали всяка стойност е в домейна си

Question 5

Видове ограничения в CSP

Answer 5

• Унарни - SA = 5
• Бинарни - SA < BA
• От по-висок ред - SA < WA + AB
• Предпочитания (червеното е по-яко от зелено)

Question 6

Генетичен Алгоритъм

Answer 6

Стохастичен Beam Search + създаване на наследнци от двойки състояния
- Има евристика, и се приближаваме с най-обещаващите състояния. Имаме краен брой състояния (размер на поколението)

Question 7

Какво оптимизира Алфа-бета отрязването - сложност по време и/или сложност по памет?

Answer 7

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

Question 8

Има ли нещо, което определя дали ще оптимизираме повече или по-малко с алфа-бета отрязването?

Answer 8

Подредба на Ходовете. Ако разглеждаме първо най-добрите ходове ще оптимизираме много повече

Question 9

Защо е Наивен наивния Бейсов класификатор?

Answer 9

Предполага, че всички характеристики са условно независими.

Question 10

Разлика между учене със и без учител?

Answer 10

• Имаме/нямаме етикети на данните
• Клъстеризация вс Класификация

Question 11

Видове йерархично клъстеризиране?

Answer 11

• Агломеративно - отдолу нагоре
  
  • Всеки обект си е сам клъстер
• Разделително - отгоре надолу
  
  • Всички започват като един клъстер