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

Практический Курс по Python:
Stepik: https://stepik.org/a/126242
Udemy: https://www.udemy.com/course/avecoder-advanced-python/?referralCode=270C5D0661A966B53743

Аве, Кодер!
Добро пожаловать вновь на введение в искусственный интеллект с 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 код наискорейшее восхождение к вершине hospitals.py
29:25 алгоритм Имитация отжига (simulated annealing)
37:04 варианты использования. Задача коммивояжера
40:23 Линейное программирование (linear programming)
43:11 пример: минимизация затрат при том, что есть ограничения, надо наколбасить 90 единиц продукции
46:48 есть ряд алгоритмов для решения таких типов задач (линейные неравенства с ограничениями). Популярные алгоритмы: Симплекс метод (simplex), Метод внутренней точки (interior-point)
47:26 код production.py
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 — schedule0.py
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: https://t.me/avecoder_ru
VK: https://vk.com/avecoder
Instagram: https://www.instagram.com/avemundi/

Файлы:
https://github.com/AveCoders/CS50-AI_with_Python_Files/tree/master/Lecture03_Optimization

Плейлист целиком:
https://www.youtube.com/playlist?list=PLPPIc-4tm3YQrvK3Kpo-S_7ZkOGKH0r_5

Благодарности и атрибуции:
David J. Malan
https://cs.harvard.edu/malan
malan@harvard.edu
Оригинал:https://www.youtube.com/watch?v=WbzNRTTrX0g&list=PLhQjrBD2T382Nz7z1AEXmioc27axa19Kv&index=2

*Публикуется с согласия Дэвида Мэлана и Гарвардского университета на редистрибуцию оригинальной работы с внесением изменений по соответствующей лицензии.

Поддержи проект:
https://www.donationalerts.com/r/avecoder
paypal.me/avecoder
https://www.patreon.com/avecoder

BTС: 1BmLvUFiJaVpCAwhzW3ZwKzMGWoQRfxsn4
ETH: 0x6f1A488c9b12E782AEF74634a40A79b1631237aB

История Технологий:
https://www.youtube.com/c/АвеТех
______________________
Аве Кодер!
Меня зовут V и я кодер. Я экспортирую из Англии: актуальные туториалы, computer science, брейнхаки, лайфхаки, здоровье кодера, тревэл он нью левэл, английский для кодера, как кодеру не помереть с голоду, юмор и многое другое.
Так что ставь императорский палец вверх, подписывайся и бей в колокол!