Поиск с предпочтением: эвристический поиск


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


- Начало -


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