lab1_2
.docxМИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра вычислительной техники
Отчет по лабораторным работам №1-2
по дисциплине «Введение в искусственный интеллект»
Студент гр. |
|
Преподаватель |
Родионов С.В. |
Тема: Методы неинформированного (слепого) поиска. Методы информированного (эвристического) поиска.
Вариант 7
1 лабораторная
Цель работы: практическое закрепление понимания общих идей поиска в пространстве состояний и стратегий слепого поиска.
Задачи:
Формализовать состояния (выбрать структуру данных). Определить функцию последователей и функцию достижения целевого состояния.
Реализовать на любом императивном языке программирования алгоритм поиска решения головоломки «8-ка» с использованием двух заданных стратегий для заданных исходного и целевого состояний.
Отладить программу.
Провести эксперемент. Далее экспериментальным путем оценить временную и емкостную сложность решения задачи для двух заданных стратегий. Сравнить теоретический анализ порядка сложности с экспериментальным
2 лабораторная
Цель работы: практическое закрепление теоретических основ информированного (эвристического) поиска.
Задачи:
- Формализовать состояния (выбрать структуру данных). Определить функцию последователей и функцию достижения целевого состояния.
- Реализовать на любом императивном языке программирования алгоритм поиска решения головоломки «8-ка» с использованием стратегии A* для заданных исходного и целевого состояний.
- Отладить программу.
- Провести эксперемент. Далее экспериментальным путем оценить временную и емкостную сложность решения задачи для двух заданных стратегий.
Вариант 7
Начальное Конечное состояние состояние
4, 8, 1, 1, 2, 3,
0, 3, 6, -> 8, 0, 4,
2, 7, 5 7, 6, 5
Стратегии поиска: в ширину, двунаправленный.
Постановка задачи
Состояние представляется массивом из 9 элементов, в котором пустое место обозначается нулем.
Для реализации алгоритмов был выбран язык программирования Python, так как он гораздо проще остальных ООП-языков синтаксически, а также в него встроен сборщик мусора, так что при написании алгоритмов не придётся отвлекаться на ручное управление памятью. Хочется отметить, что язык использует свой менеджмент памяти, поэтому показанные результаты можно интерпретировать с большой погрешностью, но все же они подходят для оценки временной и емкостной сложностей. Описание выбранных структур данных
Структура |
Описание |
Node |
Пользовательская структура, описывающая узел. Его поля – current_state - начальное состояние; parent_node - указатель на родительский узел; previous_action - действие, которое было применено к родительскому узлу для формирования данного узла; path_cost – стоимость пути; depth – глубина узла; node_id – уникальный идентификатор узла; nodes_count – статический счетчик узлов |
Список |
Используется для хранения всех когда либо созданных узлов |
Словарь |
Словарь используется для хранения узлов. В качестве ключа в словаре используется глубина, по ключу можно получить список (на основе массива), который будет содержать узлы на этом уровне. |
Хешированное множество |
Set используется для хранения хэшей состояний, а также открытых и закрытых списков в алгоритме A*. Таким образом, за O(1) можно проверить, что такое состояние уже существует. |
Приоритетная очередь на основе кучи |
Используется для получения узла с наименьшей оценочной стоимостью f за O(1). |
Функция достижения конечного состояния check_final проверяет, является ли текущее состояние конечным
#O(1) def check_final(current_state: list) -> bool:
return current_state == get_finish_state()
Функция определения последователей (они же дети) get_new_states генерирует все возможные состояния
def get_new_states(current_state: list) -> dict[Action, list[Node]]:
#В словаре ключ - действие для получения состояния, значение - само состояние
new_states = {}
pos = current_state.index(0)
# up
if pos not in (0, 1, 2):
state_swap(new_states, current_state, pos, pos-3, Action.UP)
# down
if pos not in (6, 7, 8):
state_swap(new_states, current_state, pos, pos+3, Action.DOWN)
# right
if pos not in (2, 5, 8):
state_swap(new_states, current_state, pos, pos+1, Action.RIGHT)
# left
if pos not in (0, 3, 6):
state_swap(new_states, current_state, pos, pos-1, Action.LEFT)
return new_states
Описание алгоритмов (1 лабораторная)
Поиск в ширину
Суть его такова: сначала раскрывается корневая вершина, затем – его потомки в порядке очереди (первый зашел, первый вышел).
Поиск в ширину гарантирует нахождение решение, если оно существует и всегда находит решение минимальной глубины.
Однако такой поиск имеет большую сложность (O( SUM[C^i, i=0..N] ) = O( 1/2*(C^(N+1) - 1) ) = O(C^N))
Получается порядок временной сложности поиска – O(C^N). Ёмкостная сложность равна временной O(C^N).
Двунаправленный поиск
В основе двунаправленного поиска лежит идея, что можно проводить два поиска из начального и конечного состояний, остановившись после встречи двух деревьев. Дело в том, что значение 2 * C^(N/2) гораздо меньше С^N.
Двунаправленный поиск реализуется с помощью метода, в котором предусматривается проверка в одном или обоих процессах поиска каждого узла перед его развертыванием для определения того, не находится ли он на периферии другого дерева поиска; в случае положительного результата проверки решение найдено.
Такой поиск берет преимущества поиска в ширину и имеет меньшую сложность. Временная сложность – O(C^(N/2)), емкостная сложность - O(C^(N/2)).
Описание алгоритмов (2 лабораторная)
Эвристика h1 (кол-во фишек не на своих местах):
Для реализации этого алгоритма используется приоритетная очередь, где приоритет определяется как количество фишек не на своих местах, на следующем шаге выбирается вершина с наименьшим количеством фишек не на своих местах. Далее в этой вершине открываются потомки с расчетом их приоритета и проверяются на соответствие их искомому варианту, а также на повторяющееся значение и добавляются в очередь приоритета и ждут своей очереди согласно приоритету.
Эвристика h2(манхэттенское расстояние):
Так же как и h1, метод реализован с помощью приоритетной очереди, и соответствует эвристическому алгоритму h1, с тем отличием, что приоритет определяется как сумма модулей разностей координат карточек текущей и конечной вершин (Манхэттенское расстояние).
Алгоритм А*
Реализованы два варианта алгоритма: на основе эвристических функций h1 и h2. Реализовано с использованием очереди с приоритетом, приоритет рассчитывается как f(n) = g(n) + h1(n) или f(n) = g(n) + h2(n), где h1 и h2 — вычисленные значения. на основе эвристики, а g(n) — значение глубины, на которой расположена вершина. Алгоритмы соответствуют алгоритмам эвристики h1 и h2, за исключением определения приоритета, где добавляется значение глубины g(n).
Результаты работы программ
Рисунок 1. Обход в ширину
Рисунок 2. Обход в ширину по шагам
Рисунок 3. Результат двунаправленного поиска
Рисунок 4. Результат работы А* с функцией h1
Рисунок 5. Результат работы А* с функцией h2
Рисунок 6. Результат работы А* с функцией h2 с обходом шагов
Сравнительные оценки сложности алгоритмов поиска
|
Неинформированный поиск |
Поиск алгоритмом А* |
||
Поиск в ширину |
Двунаправленный поиск |
g + h1 |
g + h2 |
|
Временная сложность |
266 мс, 64243 итерации |
16 мс, 622 итерации |
78 мс, 6094 итерации |
16 мс, 670 итераций |
Емкостная сложность |
51 008 кБ, 64246 узлов |
22932 кБ, 3415 узлов |
27 144 кБ, 9983 узлов |
22 392 кБ, 1146 узлов |
Во всех случаях итераций меньше, чем узлов, т.к. за одну итерацию раскрывается более одного узла
Вывод
Информированный поиск выдает меньшую временную и емкостную сложность, как и ожидалось. Поиск по эвристике h2 работает быстрее эвристики h1 и имеет самую меньшую сложность из представленных: будем считать, временная сложность двунаправленного поиска и второй эвристики эквивалентны из-за округлений языка Python. Таким образом, если подобрать подходящую эвристическую функцию, можно в разы уменьшить сложность в информированном поиске.
Санкт-Петербург
2022