Евристичний пошук

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Чорноморський національний університет
імені Петра Могили

Факультет комп’ютерних наук

Кафедра інженерії програмного забезпечення

ЗВІТ

З лабораторної роботи №1

122.ПРБД.ЛР.01-402.1610205

Студент

                                                                .    К,П.Восков                          .

        (підпис)        (ПІБ)

                                               12.02.2020                                        / 

(дата)

Керівник

                                                     д.т.н. Гожий О.П.                                 .

        (підпис)        (посада, ПІБ)

                                               12.02.2020                                                  / 

(дата)

Миколаїв – 2020

Практична робота №1

Евристичний пошук.

1)Завдання:

Створити дерево пошуку для гри “8”. Реалізувати в програмному коді алгоритм вирішення задачі з використанням однієї з стратегій пошуку. Навести кількість кроків, необхідних для вирішення задачі та вивести їх послідовність. Передбачити можливість відсутності рішення та можливість зміни цільового стану.

[pic 1]

2) Эвристика – любое правило или ограничение сокращающее полный перебор.

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

Типы стратегий - различают два основных типа стратегий управления, безвозвратный и пробный.

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

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

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

Основные типы методов и алгоритмов эвристического поиска:

• Жадные алгоритмы (Hill Climbing, наискорейшого спуска, Best First Search)
• A-алгоритм
• D-алгоритм
• Метод МИНИМАКСА  
• Метод Альфа-Бета отсечения

В безвозвратном режиме управления выбирается применимое правило и используется необратимо, без возможности пересмотра в дальнейшем.