Программирование на языке Пролог для искусственного интеллекта




Глава 12. Поиск с предпочтением: эвристический поиск


    Глава 12. Поиск с предпочтением: эвристический поиск
    Глава 12 ПОИСК С ПРЕДПОЧТЕНИЕМ: ЭВРИСТИЧЕСКИЙ ПОИСК Поиск в графах при решении задач, как правило, невозможен без решения проблемы комбинаторной сложности, возникающей из-за быстрого роста числа а...
    Поиск с предпочтением
    Поиск с предпочтением Программу поиска с предпочтением можно получить как результат усовершенствования программы поиска в ширину (рис. 11.13). Подобно поиску в ширину, поиск с предпочтением начина...
    Построение эвристической оценки f(n) стоимости самого дешевого пути из s в t, проходящего через n: f(n) = g(n) + h(n).
    Построение эвристической оценки f(n) стоимости самого дешевого пути из s в t, проходящего через n: f(n) = g(n) + h(n) . Мы будем в дальнейшем предполагать, что для дуг пространства состояний опред...
    Поиск кратчайшего маршрута из s в t. (а) карта со
    Поиск кратчайшего маршрута из s в t. (а) Карта со связями между городами; связи помечены своими длинами; в квадратиках указаны расстояния по прямой до цели t. (b) Порядок, в котором при поиске с п...
    Программа поиска с предпочтением.
    Программа поиска с предпочтением. Аргументы процедуры расширить имеют следующий смысл: Путь Путь между стартовой вершиной и корнем дерева Дер . Дер Текущее (под)дерево поиска. Предел Предельное зн...
    Отношение расширить: расширение дерева дер до тех
    Отношение расширить : расширение дерева Дер до тех пор, пока f-оценка не превзойдет Предел , приводит к дереву Дер1 . которое, возможно, меньшее значение Предел1 , зависящее от f-оценок других кон...
    Связь между g-оценкой вершины в и f- и g-оценками
    Связь между g-оценкой вершины В и f- и g-оценками ее детей в пространстве состояний. line(); Алгоритм поиска пути называют допустимым, если он всегда отыскивает оптимальное решение (т.е. путь мини...
    Упражнение
    Упражнение Определите отношения после , цель и h для задачи поиска маршрута рис. 12.2. Посмотрите, как наш алгоритм поиска с предпочтением будет вести себя при решении этой задачи....
    Поиск c предпочтением применительно к головоломке "игра в восемь"
    Поиск c предпочтением применительно к головоломке игра в восемь Если мы хотим применить программу поиска с предпочтением, показанную на рис. 12.3, к какой-нибудь задаче, мы должны добавить к нашей...
    Процедуры для головоломки "игра в восемь",
    Процедуры для головоломки игра в восемь, предназначенные для использования программой поиска с предпочтением рис. 12.3. Существуют три отношения, отражающих специфику конкретной задачи: после( Вер...
    Три стартовых позиции для "игры в восемь": (а) решение
    Три стартовых позиции для игры в восемь: (а) решение требует 4 шага; (b) решение требует 5 шагов; (с) решение требует 18 шагов. Наша задача - минимизировать длину решения, поэтому мы положим стоим...
    Упражнение
    Упражнение Введите в программу поиска с предпочтением, приведенную на рис. 12.3, подсчет числа вершин, порожденных в процессе поиска. Один из простых способов это сделать - хранить текущее число в...
    Применение поиска с предпочтением к планированию выполнения задач
    Применение поиска с предпочтением к планированию выполнения задач Рассмотрим следующую задачу планирования. Дана совокупность задач t1, t2, ..., имеющих времена выполнения соответственно T1, Т2, ....
    Планирование прохождения задач...
    Планирование прохождения задач в многопроцессорной системе для 7 задач и 3 процессоров. Вверху показано предшествование задач и величины продолжительности их решения. Например, задача t5 требует 2...
    Проект
    Проект Вообще говоря, задачи планирования характеризуются значительной комбинаторной сложностью. Наша простая эвристическая функция не обеспечивает высокой эффективности управления поиском. Предло...
    Отношения для задачи планирования. Даны также
    Отношения для задачи планирования. Даны также определения отношений для конкретной задачи планирования с рис. 12.8: граф предшествования и исходный (пустой) план в качестве стартовой вершины....
    Резюме
    Резюме Для оценки степени удаленности некоторой вершины пространства состояний от ближайшей целевой вершины можно использовать эвристическую информацию. В этой главе были рассмотрены численные эвр...
    Литература
    Литература Программа поиска с предпочтением, представленная в настоящей главе, - это один из многих вариантов похожих друг на друга программ, из которых А*-алгоритм наиболее популярен. Общее описа...








Начало    



Книжный магазин