Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

C++. Энциклопедия пользователя - Либерти Дж.

Либерти Дж. C++. Энциклопедия пользователя — Москва, 2001. — 581 c.
Скачать (прямая ссылка): enciklopediyapolzovatelya2001.djvu
Предыдущая << 1 .. 156 157 158 159 160 161 < 162 > 163 164 165 166 167 168 .. 280 >> Следующая

Применение альфа-бета-отсечений
Минимаксная процедура является примером поиска в глубину, потому что она сначала как можно глубже исследует один путь и применяет оценочную функцию к последнему узлу в пути. Затем она поднимается на один уровень вверх и т.д. Подобные процедуры поиска в глубину можно улучшить, используя такие методы, как методы ветвей и границ, описанные выше. Эффективность поиска в глубину можно улучшить, отказавшись от просмотра путей, которые заведомо хуже наилучшего найденного до сих пор пути. В то же время очень важно понять, что на общую производительность этого метода очень сильно влияет порядок анализа путей. Это связано с тем, что если начать анализ с худшего пути, то это сведет на нет всю идею этого метода.
Эту технику поиска лучше всего описать на примере, в котором используется минимаксная процедура в игре Tic-Tac-Toe.
При алъфа-бета-отсечении используются два пороговых значения: альфа и бета. Значение альфа — это нижняя граница значения, которое можно присвоить узлу максимизации. Значение бета — это верхняя граница значения, которое можно присвоить узлу минимизации.
Рассмотрим на примере (рис. 13.9). Предположим, что мы выполняем поиск в глубину: поиск выполнен во всем поддереве узла В, и результаты применения оценочной функции показали, что узлу D соответствует оценка 6, а узлу Е — оценка 9. Таким образом, можно гарантировать, что узлу А соответствует оценка
340
Алгоритмы поиска данных
Глава 13
341
не менее 6. Это значение становится значением альфа для узла А, и его можно использовать для исключения некоторых ветвей всего дерева из просмотра. После анализа узла К мы видим, что его оценка равна 0. Таким образом, узел I содержит оценку не более 0.
Значит, уже не нужно анализировать остальные поддеревья узла I, потому что путь из узла С в узел I заведомо невыгоден, так как переход в узел В дает оценку 6. Теперь предположим, что для узла J получена оценка 10. Таким образом, оценка узла С будет не более 10.
Это бета-значение.
Рассмотрим использование бета-значения, которое является верхней границей узла минимизации. Предположим, что оценка в узле М равняется 15; это больше, чем значение бета для узла С.
Проще говоря, если мы выберем из узла С узел G, то получим оценку 15, которая больше 10 (оценка узла F). Однако в узле С выполняется минимизация оценок, поэтому нет смысла выбирать узел G (оценка которого не меньше оценки узла М, поскольку в узле G выполняется максимизация). В результате можно отказаться от анализа всех остальных поддеревьев узла G. В очень больших деревьях использование альфа-бета-отсечений может привести к значительному сокращению путей поиска и к повышению общей производительности.
При использовании альфа-бета-отсечений на уровне максимизации можно исключить некоторый путь, если становится понятно, что его оценка меньше значения альфа для родительского узла; на уровне минимизации можно исключить путь, если становится понятно, что его оценка больше значения бета для родительского узла.
Как уже упоминалось, эффективность альфа-бета-отсечений зависит от порядка обхода путей. Можно доказать, что при существовании идеального порядка обхода количество просмотренных конечных узлов с применением альфа-бета-отсечений и глубине просмотра d примерно вдвое больше количества просмотренных конечных узлов без использования альфа-бета-отсечений и с глубиной просмотра d/2.
Дальнейшая модификация альфа-бета-отсечений, называемая отсечениями пустот, может обеспечить значительное улучшение производительности. Идея этого вида отсечений состоит в том, что можно исключить дополнительные пути, если ожидаемое улучшение минимально по сравнению с наилучшим найденным в данный момент путем. Смысл в том, что можно потратить больше времени на анализ других путей дерева в надежде найти лучший путь.
Задача коммивояжера
Изложение методов поиска не было бы полным без упоминания задачи коммивояжера. Эта задача заключается в поиске ответа на вопрос среди очень большого количества возможных решений. Для таких задач поиска неприемлем линейный поиск, используемый в других типах задач, потому что задача коммивояжера потребовала бы огромного количества времени для выполнения линейного поиска.
Определение задачи. Дано множество из N городов. Найти кратчайший маршрут, соединяющий все города без посещения одного и того же города более одного раза.
Проведено множество исследований задач такого рода; на данный момент не существует эффективного метода их решения с использованием полного перебора, потому что необходимо искать решение среди большого количества маршрутов, каждый из которых может быть очень длинный в зависимости от значения N.
Если предположить, что коммивояжер может перемещаться только между определенными парами городов, то эту задачу можно представить с помощью графа. Тогда задача будет состоять в поиске цикла. Существует несколько способов решения этой задачи, но ни один из них не является достаточно эффективным. Первый метод заключается в применении полного перебора. Полный перебор можно выполнить с помощью разновидности поиска в глубину, если не просто помечать просмотренные узлы, но и снимать пометки с узлов, если путь привел в тупик. Другими словами, выполняется поиск в глубину, и на просмотренных узлах ставятся пометки (чтобы не просматривать их повторно). Если текущий путь приводит в тупик, необходимо выполнить возврат и попробовать другой маршрут. Такой возврат требует снятия пометок с узлов, которые уже были просмотрены на маршруте. После этого можно попробовать другую ветвь. Такой полный перебор может потребовать очень много времени, особенно на полном графе.
Предыдущая << 1 .. 156 157 158 159 160 161 < 162 > 163 164 165 166 167 168 .. 280 >> Следующая