CSP and Genetic Flashcards
Видове ограничения
- Унарни - A = green
- Бинарни - A = B
- По-висок ред
- Предпочитания/Меки ограничения
CSP
Присвояване на входните променливи възможно най-добри стойности - с най-малко конфликти. Взимаме променливата с най-много конфликти и я местим на възможно най-добро място. Интересува се може ли да постигнем целта, а не как я постигаме
Примери за задачи за CSP
- Времеви рамки
- Транспортни
- Планиране
Подходи към CSP
- Backtracking (DFS)
- Constraint Propagation
- Hill climbing
Constraint Propagation в Судоку:
Начално състояние: Някои клетки на дъската вече са попълнени с числа. Тези числа поставят ограничения за останалите клетки в съответния ред, колона и 3x3 квадрат.
Разпространение на ограничения: Въз основа на вече попълнените числа, можем да изключим определени стойности за празните клетки. Например, ако едно поле в 3x3 квадрат вече съдържа числото 5, тогава никое друго поле в същия квадрат не може да бъде 5.
Итеративно изчистване: Тази процедура се повтаря, като постепенно намалява възможните стойности за всяка празна клетка, докато не се намери решение или не може да се направи повече прогрес.
Генетичен алгоритъм
Стохастичен local beam search + генериране на наследници
Как се изгражда поколение 0 при генетичните алгоритми?
Случайно се генерират k състояния.
Ползи от генетичен алгоритъм
Оптимизационни локално търсещи задачи
Селекция
Естествен подбор - най-силните индивиди имат най-голям шанс за репродукция
Мутация
Промяна на произволен ген с малка вероятност
Генетичен Сравнение с Local Beam Search
- Информирани и локално търсещи
- неоптимални
- генетичния е метаевристичен
Детерминистични игри
Без зарче, без вероятност
Недетерминистични игри
Със зарче, със елемент на случайност
Игри с Перфектна информация
Знаем възможните ходове на противника, знаем му картите
Игри с Неперфектна информация
Не знаем възможните ходове на противника
Характеристики на MiniMax
- Пълен, за крайни дървета
- Оптимален срещу оптимален опонент
α-β pruning
α - най-добрата стойност за MAX
β - най-добрата стойност за MIN
α-β pruning ефективност
Зависи от реда на обхождане на наследниците
Фрейм
Описва даден обект, като информацията се запазва в слотове, в които може да се запише конкретна стойност. Някои слотове могат да играят роля на активатори на действие
Фрейм на Сграда:
- Име на Сграда: [Име]
- Брой етажи: [Число]
- Предназначение: [Жилищна / Офис / Търговска]
- Наличие на асансьор: [Да / Не]
- Година на построяване: [Година]
Типове дъги на семантичните мрежи
- Тип подмножество (клас-суперклас)
- Тип елемент (обект-клас)
- тип функция (свойствата на обекти и класове)
Експертна система
Програма, която моделира действията на експерт. Изпълнява продукционни правила (if-then-else). Представяне на знания, с което може да се разсъждава в конкретна предметна област
Моделиране на действията на експерт: Експертните системи са проектирани да имитират начина, по който експертите в дадена област мислят и вземат решения. Това включва разбирането и интерпретацията на сложни данни и ситуации.
Изпълнение на продукционни правила: Те използват продукционни правила, които са форма на представяне на знанията. Тези правила обикновено са във формат “ако-то” (if-then), където “ако” частта представлява условие и “то” частта - действие или заключение.
Представяне на знания: Експертните системи съдържат обширна база от знания за конкретна предметна област. Тази база от знания включва факти, концепции, отношения и евристики, които са от съществено значение за областта.
Способност за разсъждение: Освен съхраняването на знания, експертните системи също могат да използват различни методи за разсъждение за анализиране на информацията и вземане на решения.
Агент
Функция, която получава входна информация от околната среда и като резултат взима решение за действие
Типове агенти
- Прост рефлексивен
- Рефлексивен агент с памет
- Агент с цел
- utility-based agent
