ЛАБОРАТОРНАЯ РАБОТА 3 Методы типа дерева целей. Цель работы: Испытание метода дерева целей для решения сложных задач. - презентация

1 ЛАБОРАТОРНАЯ РАБОТА 3 Методы типа дерева целей

2 Цель работы: Испытание метода дерева целей для решения сложных задач.

3 Задача: Преобразовать произвольную начальную конфигурацию в конфигурацию имеющую вид (рис.1):

4 Расчет оценочной функции Более рациональный способ поиска решения связан с употреблением для упорядочения перебора оценочных функций. Оценочная функция должна обеспечивать возможность ранжирования вершин кандидатов на раскрытие – с тем, чтобы выделить ту вершину, которая с наибольшей вероятностью находится на лучшем пути к цели. f(n) = g(n) + W(n), Где f(n) – оценочная функция, используемая для упорядочения вершин перед их раскрытием. Где f(n) – оценочная функция, используемая для упорядочения вершин перед их раскрытием. g(n) – длина пути в дереве перебора от начальной вершины до вершины n. g(n) – длина пути в дереве перебора от начальной вершины до вершины n. W(n) – число фишек, которые лежат не на своем месте в описании состояния, связанного с вершиной n. W(n) – число фишек, которые лежат не на своем месте в описании состояния, связанного с вершиной n.

5 Рассчитаем оценочную функцию для каждой вершины: Начальная вершина 1 2 f = = 4 f = 6 f = 4 f = 6

6 f = 5 f = 7 f = 4

7 f = 5 f = 6 f = 7 Целеваявершина

8 Вывод: Использование оценочной функции приводит к существенно меньшему числу раскрытий вершин, чем путь который можно получить методом полного перебора.

9 Достаточно хорошей оценочной функцией является: 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 целевая вершина

10 F = 1+( )+ 3( )=58 f=57 f=57 f=57 f=59 f=59f=59 f=59 f=59 f=57 f=57

11 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

12 f=56 f=57 f=46 f=43 f=45 f=45 f=45 f=49

13 f=45 f=47 f=45f=45 f=47 f=56 f= 36 f=33 f=27f=27 целевая вершина f=18 f=29 f= 41