lab1_2

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра вычислительной техники

Отчет по лабораторным работам №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 лабораторная)

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. Двунаправленный поиск

В основе двунаправленного поиска лежит идея, что можно проводить два поиска из начального и конечного состояний, остановившись после встречи двух деревьев. Дело в том, что значение 2 * C^(N/2) гораздо меньше С^N.

Двунаправленный поиск реализуется с помощью метода, в котором предусматривается проверка в одном или обоих процессах поиска каждого узла перед его развертыванием для определения того, не находится ли он на периферии другого дерева поиска; в случае положительного результата проверки решение найдено.

Такой поиск берет преимущества поиска в ширину и имеет меньшую сложность. Временная сложность – O(C^(N/2)), емкостная сложность - O(C^(N/2)).

Описание алгоритмов (2 лабораторная)

1. Эвристика h1 (кол-во фишек не на своих местах):

Для реализации этого алгоритма используется приоритетная очередь, где приоритет определяется как количество фишек не на своих местах, на следующем шаге выбирается вершина с наименьшим количеством фишек не на своих местах. Далее в этой вершине открываются потомки с расчетом их приоритета и проверяются на соответствие их искомому варианту, а также на повторяющееся значение и добавляются в очередь приоритета и ждут своей очереди согласно приоритету.

2. Эвристика h2(манхэттенское расстояние):

Так же как и h1, метод реализован с помощью приоритетной очереди, и соответствует эвристическому алгоритму h1, с тем отличием, что приоритет определяется как сумма модулей разностей координат карточек текущей и конечной вершин (Манхэттенское расстояние).

3. Алгоритм А*

Реализованы два варианта алгоритма: на основе эвристических функций 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