ЛАБОРАТОРНАЯ РАБОТА 3 Методы типа дерева целей
Цель работы: Испытание метода дерева целей для решения сложных задач.
Задача: Преобразовать произвольную начальную конфигурацию в конфигурацию имеющую вид (рис.1):
Расчет оценочной функции Более рациональный способ поиска решения связан с употреблением для упорядочения перебора оценочных функций. Оценочная функция должна обеспечивать возможность ранжирования вершин кандидатов на раскрытие – с тем, чтобы выделить ту вершину, которая с наибольшей вероятностью находится на лучшем пути к цели. f(n) = g(n) + W(n), Где f(n) – оценочная функция, используемая для упорядочения вершин перед их раскрытием. Где f(n) – оценочная функция, используемая для упорядочения вершин перед их раскрытием. g(n) – длина пути в дереве перебора от начальной вершины до вершины n. g(n) – длина пути в дереве перебора от начальной вершины до вершины n. W(n) – число фишек, которые лежат не на своем месте в описании состояния, связанного с вершиной n. W(n) – число фишек, которые лежат не на своем месте в описании состояния, связанного с вершиной n.
Рассчитаем оценочную функцию для каждой вершины: Начальная вершина 1 2 f = = 4 f = 6 f = 4 f = 6
f = 5 f = 7 f = 4
f = 5 f = 6 f = 7 Целеваявершина
Вывод: Использование оценочной функции приводит к существенно меньшему числу раскрытий вершин, чем путь который можно получить методом полного перебора.
Достаточно хорошей оценочной функцией является: f(n) = p(n) + 3S(n) + g(n) где S(n) – число очков, учитывающее порядок расположения фишек. Для его вычисления необходимо просмотреть все нецентральные фишки в данной конфигурации и за каждую фишку, за которой не идет та фишка, которая должна бы идти, начисляется два очка, в противном случае берется ноль очков. За фишку, находящуюся в центре, начисляется одно очко. P(n) – сумма расстояний каждой фишки от своего места (без учета фишек, расположенных на ее пути). f=45 f=47 f=56 f= 36 f= 41 f=29 f=33 f=27 f=18 целевая вершина
F = 1+( )+ 3( )=58 f=57 f=57 f=57 f=59 f=59f=59 f=59 f=59 f=57 f=57
f=59 f=59 f=59 f=58 f=57 f=57f=57 f=57 f=57 f=56 f=55 f=55 f=55 f=62
f=56 f=57 f=46 f=43 f=45 f=45 f=45 f=49
f=45 f=47 f=45f=45 f=47 f=56 f= 36 f=33 f=27f=27 целевая вершина f=18 f=29 f= 41