HARVARD CS50 - “Оптимизация“ - Лекция 3 - Искусственный Интеллект с Python

Аве, Кодер! Добро пожаловать вновь на введение в искусственный интеллект с Python. В прошлый раз мы говорили о таких вещах как: условная вероятность, правило Байеса, байесовская сеть, цепи Маркова, и о многом другом. На этот раз мы рассмотрим основные принципы оптимизации задач, рассмотрим графы, алгоритмы локального поиска, задачи удовлетворения ограничений, линейные программы, поиск с возвратом (backtracking search), а также многое другое. Enjoy! Тайм-коды: 0:55 оптимизация - выбор наилучшего варианта из набора возможных вариантов 1:25 алгоритм Локальный поиск (local search) те случаи, когда выяснение того, что именно является решением и как именно выглядит цель - суть задачи 2:34 пример на практике: дома и больницы 4:07 задачи поиска в пространстве состояний (state-space landscape). Целевая функция. Функция стоимости 7:26 алгоритм Восхождение к вершине (hill climbing) 14:41 ограничение этого алгоритма - не всегда результат - самое оптимальное решение 17:51 разновидности hill climbing: 1) Наискорейшее восхождение к вершине 18:34 2) Стохастическое восхождение к вершине 19:11 3) Восхождение к вершине по первому лучшему совпадению 19:39 случайное возобновление 20:23 4) Локальный лучевой поиск 20:57 код наискорейшее восхождение к вершине 29:25 алгоритм Имитация отжига (simulated annealing) 37:04 варианты использования. Задача коммивояжера 40:23 Линейное программирование (linear programming) 43:11 пример: минимизация затрат при том, что есть ограничения, надо наколбасить 90 единиц продукции 46:48 есть ряд алгоритмов для решения таких типов задач (линейные неравенства с ограничениями). Популярные алгоритмы: Симплекс метод (simplex), Метод внутренней точки (interior-point) 47:26 код 50:58 Задачи удовлетворения ограничений (constraint satisfaction problem) CSP 51:37 пример: студенты. Граф Ограничений 55:00 пример: игра судоку 56:49 разные формы ограничений: жёсткие, мягкие 58:04 классификация ограничений: 1) унарные ограничения (зависят от констант), 2) бинарные (двоичные) ограничения (зависят от 2 величин) 59:07 условия: 1) проблемный узел сделать согласованным (удовлетворять всем унарным ограничениям) 1:03:06 другой тип согласованности - 2) согласованность дуги (удовлетворять всем бинарным ограничениям) 1:06:43 псевдокод: согласованность дуги 1:09:01 алгоритм AC-3 (задача удовлетворения всем ограничениям) 1:13:33 Граф ограничений 1:14:40 задача поиска состоит из частей... 1:15:07 формулировка CSP как подтип задач поиска 1:16:18 способы улучшить алгоритм, используя структуру задачи 1:16:53 алгоритм Поиск с возвратом (backtracking search). Рекурсивная функция. Псевдокод 1:20:21 пример на практике: поиск с возвратом 1:25:00 код поиск с возвратом scheduling -- 1:27:44 существуют библиотеки, реализующие этот алгоритм 1:29:33 алгоритм Поддержания согласованности дуги. Идеи логического вывода (inference). Использование согласованности дуг, без возврата 1:33:34 псевдокод 1:35:10 улучшенные варианты (select-unassigned-var). Какую переменную рассматривать дальше 1:37:17 пример на практике 1:39:25 функция domain_values Значения домена. Для какой переменной (выбор переменной, оставляющей наименьшее количество таких же вариантов в других переменных) 1:43:07 Вывод. Есть несколько различных способов сформулировать задачу. 1) задача в виде локального поиска, 2) в виде линейных программ, 3) задача удовлетворения ограничений За тайм-коды огромная благодарность пользователю Iritaka! #авекодер #cs50 #harvard #искусственныйинтеллект #нейросети Telegram: VK: Instagram: Файлы: Плейлист целиком: Благодарности и атрибуции: David J. Malan malan@ Оригинал: *Публикуется с согласия Дэвида Мэлана и Гарвардского университета на редистрибуцию оригинальной работы с внесением изменений по соответствующей лицензии. Поддержи проект: BTH: 1BmLvUFiJaVpCAwhzW3ZwKzMGWoQRfxsn4 ETH: 0x6f1A488c9b12E782AEF74634a40A79b1631237aB Ave Coder на английском: ______________________ Аве Кодер! Меня зовут V и я кодер. Я экспортирую из Англии: актуальные туториалы, computer science, брейнхаки, лайфхаки, здоровье кодера, тревэл он нью левэл, английский для кодера, как кодеру не помереть с голоду, юмор и многое другое. Так что ставь императорский палец вверх, подписывайся и бей в колокол!