Методы искусственного интеллекта
Документы на этом сайте, имеющие в пути директорию /ai/, посвящены искусственному интеллекту и компьютерным наукам. Несмотря на довольно широкий круг вопросов, отбирались только те темы, которые интересны автору. Кроме рассмотрения теоретических вопросов, приведено много программного кода на JavaSript и некоторые примеры, встроенные в html-страницу, являются интерактивными. Материалы, готовые к настоящему времени, имеют следующее содержание:
Структуры данных
- JavaScript для ИИ - вводный раздел, посвящённый основам языка, их которого, возможно, станет ясно почему для задач искусственного интеллекта будет использоваться JavaScript.
- Рекурсия - обсуждается базовая технология программирования и описания алгоритмов. Разбирается вычисление факториала, задача расстановки ферзей, чисел Фибоначчи и алгоритм упаковки рюкзака.
- Метод грубой силы (или метод полного перебора) применяется к задаче коммивояжёра, хотя как раз к ней он не очень и применим :). Обсуждаются способы генерации перестановок и проведение длительных вычислений в таймере.
- Списки - являются базовой структурой данных в задачах искусственного интеллекта. Подробно разбирается реализация класса List и анализируется его быстродействие.
- Бинарный поиск позволяет быстро находить данные, благодаря их упорядочиванию. Рассмотрены соответствующие алгоритмы, реализованные в классе BSTree и их сравнение с встроенными в язык возможностями.
- Приоритетная очередь - важнейший инструмент при проведении направленного поиска в многих задачах ИИ. Приведена простейшая реализация очереди при помощи бинарной кучи.
- Деревья - реализованы в классе Tree, имеющем широкие возможности по различному визуальному представлению данных с древовидной организацией.
- Графы - это основная модель описания пространства состояний в задачах поиска оптимального решения задач. Обсуждаются струтура данных, способы генерации графов и некоторые теоретические вопросы.
Поиск
- Пространство состояний - является основной концепцией в задачах поиска решений. Будет построено пространство состояний пятнашек и Ханйоской головоломки. Обсуждаются способы описания состояний в различных моделях.
- Поиск на деревьях - рассмотрены три базовых алгоритма поиска целевого узла на деревьях: поиск в глубину, ширину и поиск с итеративным углублением.
- Поиск на графах - рассмотрены методы поиска кратчайшего пути на графах. Кроме поиска в ширину в одном направлении и во встречных, обсуждается метод направленного поиска. Он не гарантирует наиболее эффективного решения, но вряде случаев оказывается существенно более быстрым и "человеческим" подходом к решению задачи.
- Пятнашки - классическая головоломка, являющаяся полигоном для различных эвристик направленного поиска. В документе описан класс Fifteen, умеющий рисовать игровое поле и взаимодействовать с мышкой.
- Эвристики в пятнашках
- Задача коммивояжёра - класс Salesman.
- Жадный поиск в задача коммивояжёра.
- Метод ветвей и границ в задача коммивояжёра.
- Ханойские башни - ещё одна головоломка, решение которой можно получить очень изящным образом при помощи рекурсии. Как и в случае с пятнашками, будет написан класс Hanoi, отображающий ханойские башни и анимирующий решение головоломки.
Пообщаться со мной можно по электронному адресу: "steps"+((1/α)|0)+"@gmail.com",
где α - постоянная тонкой структуры.