Эвристическая функция. Функция компенсации информационного дефицита
Эвристический поиск на И-ИЛИ графах
Поиск в глубину на И-ИЛИ графе
Как по И-ИЛИ графу построить решающее дерево? Это дело системы (стратегии) управления. На И-ИЛИ графах возможны все виды поиска, которые мы изучили: поиск в глубину, поиск в ширину, эвристический поиск.
Поиск в глубину на И-ИЛИ графах является процедурным механизмом Prolog-системы. Вначале системе адресуется запрос, или главная цель.
Для ее решения нужно решить все подцели в теле правила, с которым запрос сопоставился. Это вершина типа «И».
Если к цели могут быть применены альтернативные правила, то это вершина типа «ИЛИ».
Цель, которая сопоставилась с фактом базы данных, - терминальная вершина.
Рассмотрим поиск в глубину на модельном И-ИЛИ графе (рис. 19):
Рисунок 19. Модельный «И-ИЛИ граф»
Поиск в глубину из вершины X:
Если Х-целевая вершина, то задача решена.
Если Х-вершина типа «ИЛИ», то нужно пробовать решать одну за другой задачи-преемники, пока не будет найдена задача, имеющая решение.
Если Х-вершина типа «И», то нужно решить все ее задачи-преемники.
Если применение этих правил не приводит к решению, то решения нет.
Задание . Написать программу, реализующую поиск в глубину на модельном И-ИЛИ графе (рис. 19). Какова ее вычислительная сложность?
Припишем дугам И-ИЛИ графа стоимости.
Положим стоимость решающего дерева равной стоимости входящих в него дуг.
Цель оптимизации - поиск дерева решения минимальной стоимости.
Определим стоимость вершины как стоимость минимального решающего дерева с корнем в этой вершине.
Определим эвристическую функцию на вершинах И-ИЛИ графа. Эвристическая оценка листов равна непосредственно значению эвристики h(u) на вершине u. Внутренние вершины имеют преемников. Они будут оцениваться с помощью возвращенной эвристической оценки - оценки стоимости минимального решающего дерева с корнем в u.
Оценка для ИЛИ-вершины (рис. 20).
Рисунок 20. Возвращенная эвристика «ИЛИ»-вершины
Оценка для И-вершины (рис. 21).
Рисунок 21. Возвращенная эвристика «И»-вершины
3) - оценка для листа
В нашем дереве поиска у каждой вершины только один отец. Пусть u 0 - отец, u - сын (рис.22).
Рисунок 22. f-оценка сына u 1 с отцом u 0
f-оценка вершины u складывается как стоимость дуги, входящей в u от родительской вершины, плюс ее возвращенная эвристическая оценка . Начальная вершина не имеет родителя, поэтому будем считать, что в нее входит фиктивная дуга стоимости 0.
1.8.2. АО*-алгоритм эвристического поиска на И-ИЛИ графе
Каждый преемник ИЛИ-вершины соответствует альтернативному дереву - кандидату в решение. АО*-алгоритм на каждом шаге будет расширять дерево с минимальной f-оценкой, вычисленной следующим образом:
- для И-вершины;
Для ИЛИ-вершины.
Рассмотрим эвристический поиск на примере модельного И-ИЛИ графа (рис. 23) с эвристиками всех вершин тождественно равными 0 (h(u)≡0 для всех u).
Рисунок 23. Модельный граф с эвристиками всех вершин тождественно равными нулю
Начнем поиск из начальной вершины а.
f(a) = 0 + h(a) = 0 (рис. 24):
Рисунок 24. Трассировка алгоритма. Шаг 1
f(b) = 1 + h(b) =1;
f(c) = 3 + h(c) = 3;
f(a) = 0 + min{f(b),f(c)} = min{1,3} = 1.
Рисунок 25. Трассировка алгоритма. Шаг 2
Дерево с корнем в b является минимальным, поэтому оно расширяется (рис. 26), его оценка пересчитывается и пересчитывается оценка вершины а:
f(d) = 1 + h(d) =1;
f(e) = 1 + h(e) =1;
f(b) = 1 + f(d) + f(e) =3.
Рисунок 26. Трассировка алгоритма. Шаг 3
f(b) ≤ f(c), поэтому продолжаем расширять дерево с корнем в b. При попытке расширить d обнаруживаем что d - целевая вершина, для e находим преемника h (рис. 27):
f(h) = 6 + h(h) =6;
f(e) = 1 + h(h) =1 + 6 =7;
f(b) = 1 + f(d) + f(e) = 1 + 1 + 7 = 9
Рисунок 27. Трассировка алгоритма. Шаг 4
Поиск не успел понять, что h - целевая вершина; стоимость дерева с корнем в b равна 9, поэтому происходит переключение на дерево с корнем в с, причем рост дерева с корнем в с ограничивается величиной 9: f(c) ≤ 9 (рис. 28):
f(f) = 2 + h(f) =2;
f(g) = 1 + h(g) =1;
f(c) = 3 + f(f) +f(g) = 3 + 2 + 1 =6;
Рисунок 28. Трассировка алгоритма. Шаг 5
f(b) ≤ 9, поэтому продолжаем расширять дерево с корнем в с (рис. 29). Обнаруживаем, что g - целевая вершина и для f находим двух преемников:
f(h) = 2 + h(h) = 2;
f(i) = 3 + h(i) = 3;
f(f) = 2 +min {2,3} = 4;
f(c) = 3 + f(f) + f(g) = 8
f(a) = 0 + f(c) = 8.
Рисунок 29. Трассировка алгоритма. Шаг 6
Штриховой линией обведено активное дерево поиска. Заметим, что вершина h включена в разные деревья поиска и имеет разные f оценки: 6 и 2. f(c)≤8≤9, поэтому продолжаем расширять дерево с корнем в c. При попытке расширить h обнаруживаем целевую вершину и получаем дерево решения. Так как все h(u) ≡ 0, то оценка вершины а - f(a) есть стоимость дерева решения.
1.8.3. Некоторые свойства АО*-алгоритма
Обозначим стоимость минимального дерева решения, связывающего вершину u с терминальными вершинами.
Если для всех u, то эвристический поиск построит минимальное дерево решения. Это условие для эвристики h можно заменить другим - условием монотонности эвристики h.
Пусть у вершины u имеется несколько связок, одна связка состоит из k потомков u 1 ,…, u k . Если для каждой связки имеет место неравенство
где с(u,u i) - стоимость дуги от вершины u до потомка u i , h(u i) - эвристика вершины u i , и для каждой терминальной вершины t h(t)≡0. Это условие аналогично условию монотонности для обычного графа пространства состояний:
Т.е. эвристики вершин не меняются резко и согласованы со стоимостью дуг.
Информи́рованный по́иск (также эвристический поиск , англ. informed search, heuristic search ) - стратегия поиска решений в пространстве состояний , в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами .
Информация о конкретной задаче формулируется в виде эвристической функции . Эвристическая функция на каждом шаге перебора оценивает альтернативы на основании дополнительной информации с целью принятия решения о том, в каком направлении следует продолжать перебор .
Эвристические функции [ | код ]
В контексте поиска в пространстве состояний, эвристическая функция (англ. heuristic function ) h (n ) определена на узлах дерева перебора следующим образом:
h (n ) = оценка стоимости наименее дорогостоящего пути от узла n до целевого узла.Если n - целевой узел, то h (n ) = 0.
Узел для развёртывания выбирается на основе функции оценки (англ. evaluation function )
f (n ) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n , f (n ) = g (n ) + h (n ),где функция g (n ) определяет стоимость уже пройденного пути от начального узла до узла n .
Значения функций вдоль оптимального решения
f1(n) = g(n) + h1(n) - недопустимая эвристика
f2(n) = g(n) + h2(n) - допустимая, но не преемственная
f3(n) = g(n) + h3(n) - преемственная эвристика
Если эвристическая функция h (n ) никогда не переоценивает фактическую минимальную стоимость достижения цели (то есть является нижней оценкой фактической стоимости), то такая функция называется допустимой (англ. admissible ).
Если эвристическая функция h (n ) удовлетворяет условию
h (a ) ≤ cost (a , b ) + h (b ),где b - потомок a , то такая функция называется преемственной (англ. consistent ).
Если f (n ) = g (n ) + h (n ) - функция оценки, h (n ) - преемственная функция, то функция f (n ) является монотонно неубывающей вдоль любого исследуемого пути. Поэтому преемственные функции также называются монотонными (англ. monotonic ).
Любая преемственная функция является допустимой, но не любая допустимая функция является преемственной.
Если h 1 (n ), h 2 (n ) - допустимые эвристические функции, и для любого узла n верно неравенство h 1 (n ) ≥ h 2 (n ), то h 1 является более информированной эвристикой, или доминирует над h 2 .
Если для задачи существуют допустимые эвристики h 1 и h 2 , то эвристика h (n ) = max(h 1 , h 2) является допустимой и доминирует над каждой из исходных эвристик .
Сравнение эвристических функций [ | код ]
При сравнении допустимых эвристик имеют значение степень информированности и пространственная и временная сложность вычисления каждой из эвристик. Более информированные эвристики позволяют сократить количество развёртываемых узлов, хотя платой за это могут быть затраты времени на вычисление эвристики для каждого узла.
Эффективный коэффициент ветвления (англ. effective branching factor ) - среднее число преемников узла в дереве перебора после применения эвристических методов отсечения . По эффективному коэффициенту ветвления можно судить о качестве используемой эвристической функции.
Идеальная эвристическая функция (например, таблица поиска ) всегда возвращает точные значения длины кратчайшего решения, поэтому дерево перебора содержит только оптимальные решения. Эффективный коэффициент ветвления идеальной эвристической функции близок к 1 .
Примеры задач поиска [ | код ]
В качестве моделей для испытания алгоритмов поиска и эвристических функций часто используются перестановочные головоломки - Пятнашки 3×3 , 4×4 , 5×5 , 6×6 , кубик Рубика , Ханойская башня с четырьмя стержнями .
В головоломке «Пятнашки» может быть применена эвристика h m , основанная на манхэттенском расстоянии . Более конкретно, для каждой плитки подсчитывается манхэттенское расстояние между её текущим положением и её положением в начальном состоянии; полученные величины суммируются.
Можно показать, что эта эвристика является допустимой и преемственной: за один ход её значение не может измениться более чем на ±1.
Конструирование эвристических функций [ | код ]
Ослабленная задача [ | код ]
Эвристическая функция h m , использующаяся для решения головоломки «Пятнашки», представляет собой нижнюю оценку длины оптимального решения. Помимо этого, h m (n ) - это точное значение длины оптимального решения упрощённой версии головоломки, в которой плитки можно передвигать в занятые позиции. В исходной головоломке присутствует ограничение «в одной клетке не должны находиться две и более плитки», которого нет в упрощённой версии. Задача с меньшим количеством ограничений на возможные действия называется ослабленной задачей (англ. relaxed problem ); стоимость решения ослабленной задачи является допустимой эвристикой для первоначальной задачи , так как любое решение первоначальной задачи является также решением ослабленной задачи.
Подзадача [ | код ]
Допустимая эвристика может быть основана на стоимости решения подзадачи (англ. subproblem ) исходной задачи. Любое решение основной задачи одновременно является решением каждой из её подзадач .
Подзадачей задачи решения головоломки «Пятнашки» может быть задача перемещения на свои места плиток 1, 2, 3 и 4. Стоимость решения этой подзадачи является допустимой эвристикой для исходной задачи.
Базы данных с шаблонами [ | код ]
Пример шаблона для головоломки «Пятнашки» изображён на рисунке справа: в определение подзадачи входят позиции семи фишек, находящихся в первом столбце и в первой строке. Количество конфигураций этого шаблона равно 16 ! 8 ! = 518918400 {\displaystyle {\dfrac {16!}{8!}}=518918400} . Для каждой из конфигураций база данных содержит минимальное количество ходов, необходимое для перевода этой конфигурации в целевую конфигурацию подзадачи, показанную на рисунке. Построение базы данных осуществляется методом обратного поиска в ширину .
Алгоритмы поиска [ | код ]
[ | код ]
Поиск по первому наилучшему совпадению (англ. best-first search ) представляет собой подход, в котором узел для развёртывания выбирается на основе оценочной функции f (n ). Для развёртывания выбирается узел с наименьшей оценкой.
Поиск A* [ | код ]
Поиск A* - наиболее известная разновидность поиска по первому наилучшему совпадению. В нём применяется оценка f (n ) стоимости наименее дорогостоящего пути решения, проходящего через узел n :
f (n ) = g (n ) + h (n ), где g (n ) - стоимость пути от начального узла до узла n , h (n ) - оценка стоимости пути от узла n до цели.Если h (n ) никогда не переоценивает стоимость достижения цели (то есть является допустимой), то поиск A* является оптимальным.
IDA* [ | код ]
Алгоритм A* с итеративным углублением (iterative deepening A*, IDA* ) - применение идеи итеративного углубления в контексте эвристического поиска.
node текущий узел g стоимость начала решения root..node f оценка стоимости минимального пути через node h (node ) эвристическая оценка стоимости остатка пути node..goal cost (node , succ ) функция стоимости пути is_goal (node ) функция проверки цели successors (node ) функция развёртывания узла node procedure ida_star (root , cost (), is_goal (), h ()) bound := h (root ) loop t := search (root , 0, bound ) if t = FOUND then return FOUND if t = ∞ then return NOT_FOUND bound := t end loop end procedure function search (node , g , bound ) f := g + h (node ) if f > bound then return f if is_goal (node ) then return FOUND min := ∞ for succ in successors (node ) do t := search (succ , g + cost (node , succ ), bound ) if t = FOUND then return FOUND if t < min then min := t end for return min end functionMA* [ | код ]
SMA* [ | код ]
SMA* (англ.)
Ещё полностью не сформировалась.
Энциклопедичный YouTube
-
1 / 5
В Древней Греции под эвристикой понимали систему обучения, практиковавшуюся Сократом , когда учитель приводит ученика к самостоятельному решению какой-либо задачи, задавая ему наводящие вопросы. Понятие «эвристика» встречается в трактате греческого математика Паппа «Искусство решать задачи» (300 год н. э.).
Долгое время в основе творчества лежали методы проб и ошибок, перебора возможных вариантов, ожидание озарения и работа по аналогии. Так, Томас Эдисон провел около 50 тысяч опытов, пока разрабатывал устройство щелочного аккумулятора. А об изобретателе вулканизированной резины Чарльзе Гудиер (Goodyear) писали, что он смешивал сырую резину (каучук) с любым попадавшимся ему под руку веществом: солью, перцем, сахаром, песком, касторовым маслом, даже с супом. Он следовал логическому заключению, что рано или поздно перепробует всё, что есть на земле и, наконец, наткнется на удачное сочетание .
Однако со временем такие методы начали приходить в противоречие с темпами создания и масштабами современных объектов. Наиболее интенсивно поиском и разработкой эвристических методов занялись со второй половины XX века, причём не только посредством изучения приемов и последовательности действий инженеров и других творческих работников, но и на основе достижений психологии и физиологии мозга.
Эвристические методы
Эвристическими методами называются логические приемы и методические правила научного исследования и изобретательского творчества, которые способны приводить к цели в условиях неполноты исходной информации и отсутствия четкой программы управления процессом решения задачи .
В узком смысле слова под эвристикой понимают интуитивные (неосознанные) методы решения задач, в том числе:
- систему обучения, берущую свои истоки от сократовской майевтики (т. н. сократические беседы),
- эвристические методы проектирования,
- эвристический алгоритм , представляющий совокупность приёмов в поиске решения задачи, которые позволяют ограничить перебор.
В настоящее время разработано и эффективно используется несколько десятков эвристических методов. Универсальных среди них нет, и в каждой конкретной ситуации рекомендуют пробовать применять ряд методов, поскольку основное их предназначение заключается в активизации творческой деятельности. Это достигается следующими мерами:
- преодоление психологической инерции, обусловленной привычными образом мышления и типовыми методами решения задач определенного класса. Замечено, что около 80 % нововведений вначале специалистами отрицается как нереальные. Инерцию развивают и усиливают:
- рецептурное обучение и проектирование по аналогии;
- подсознательная вера в то, что каждая вещь и явление служат строго определенной цели;
- (техническая) терминология. Ф.Энгельс писал: «В науке каждая новая точка зрения влечет за собою революцию в технических терминах»;
- мобилизация подсознания.
- расширение перспектив видения, чему препятствует чрезмерная специализация образования и узкопрактический подход. Необходимо применение разнообразных методов, расширение области поиска новых идей и увеличение их количества.
Эвристические модели
Эвристика как наука занимается построением эвристических моделей процесса поиска оригинального решения задачи. Существуют следующие типы таких моделей:
- модель слепого поиска, которая опирается на метод проб и ошибок;
- лабиринтная модель, в которой решаемая задача рассматривается как лабиринт, а процесс поиска решения - как блуждание по лабиринту;
- структурно-семантическая модель, которая исходит из того, что в основе эвристической деятельности по решению задачи лежит принцип построения системы моделей, которая отражает семантические отношения между объектами, входящими в задачу.
Особенности эвристической деятельности
Эвристические методы и моделирование присущи только человеку и отличают его от искусственных интеллектуальных (мыслящих) систем. В настоящее время к сфере человеческой деятельности относят:
- постановку задачи;
- выбор методов её решений и построение (разработка) моделей и алгоритмов, выдвижение гипотез и предположений;
- осмысление результатов и принятие решений.
Стоит отметить, что важной особенностью именно человеческой деятельности является наличие в ней элемента случайности: необъяснимые поступки и сумасбродные решения часто лежат в основе оригинальных и неожиданных идей.
Однако с развитием вычислительной техники выполнение всё большего числа функций берут на себя автоматические системы, при этом выполняя работу быстрее и эффективнее человека. Задача человека как homo sapiens, прежде всего, совершенствоваться в эвристических процедурах , а не в выполнении алгоритмизированных операций, чтобы впоследствии не оказаться вытесненным «разумной» техникой.
Результаты эвристической деятельности
В науке и технике выделяют следующие результаты эвристической (творческой) деятельности:
- открытие , то есть установление ранее неизвестных объективных закономерностей, свойств и явлений материального мира с обязательным экспериментальным подтверждением. Открытие, в основном, является продуктом научной деятельности, но решающим и революционным образом определяет развитие техники. На открытие существует приоритет (право первенства), но нет права собственности на использование;
- изобретение , то есть новое и обладающее существенными отличиями техническое решение задачи, которое не является очевидным следствием известных решений. Изобретение относится к объектам интеллектуальной собственности и защищается патентным правом (главным образом - в виде предоставления патентообладателю исключительного права на использование изобретения). Содержание изобретения публикуется. Изобретателю выдается патент , свидетельствующий о его праве и приоритете на изобретение (в России ранее вместо патента выдавали авторское свидетельство). Исключительное право может быть уступлено (продано). Изобретение может быть использовано в коммерческих целях только с разрешения патентообладателя на основе лицензионного договора ;
- рационализаторское предложение , то есть предложение по улучшению конструкции реального изделия или процесса его изготовления, не содержащее существенно новых решений (с недостаточно существенными отличиями) и с незначительной эффективностью. Часто в качестве рацпредложения оформляют применение решения, неизвестного на данном предприятии, но известного в других местах (но следует быть осторожным с возможным нарушением авторских прав). Понятие рацпредложения существует всего в нескольких странах как способ поощрения изобретательства и вовлечения в него широкого круга работников предприятия;
Онтологическая функция - первая и отправная. Ее назначение - познание и объяснение политических явлений и процессов такими, какие они есть в действительности. Выполняя онтологическую функцию, политология отвечает на вопросы, что такое политика, политические институты и учреждения, как и почему они возникли, что они представляют собой в настоящее время, какова их судьба и т. д.
Эвристическая функция .Эвристика - это искусство нахождения истины и новых открытий. Политология не ограничивается познанием и истолкованием политических явлений и процессов, а постоянно углубляет знания о них, открывает новые закономерности в их развитии.
Методологическая функция . Методология - это, по сути дела, теория (учение), обращенная к научным исследованиям. Политология как сравнительно молодая наука призвана постоянно совершенствовать, обогащать арсенал методов, способов познания своего * сложного и динамичного предмета. Ее категории, выводы и основополагающие идеи используются другими гуманитарными науками, если они затрагивают проблемы политической жизни общества.
Управленческая функция . Термин "политика" в переводе с греческого - "искусство управления государством". Венцом политики выступает политическая (государственная) власть. Вот почему партии и политические движения ведут столь активную борьбу за политическую власть. Кому принадлежит она, тот, как правило, решает все дела. Реализуется политическая власть через государственное управление.
Мировоззренческо-регулятивная функци я. Один из основателей международного права Г. Гроций говорил, что война начинается в умах людей. Можно сказать шире - всякое поведение, любая человеческая деятельность начинается в умах, в сознании людей. Отсюда вытекает важная роль мировоззрения, политического сознания и политической культуры в регулировании общественных отношений. Они образуют интеллектуальную основу, определяющую качество работы всего регулятивного механизма. От уровня политического сознания и культуры напрямую зависит политическая активность личности и общества.
Прогностическая функция . На основе познания закономерностей развития политических явлений и процессов политология способна выдвигать гипотезы, теории, истинность которых затем будет проверяться практикой.
Научное прогнозирование имеет большое значение для предвидения в политической сфере, оно позволяет "заглянуть" в будущее политических явлений. Научные прогнозы будят мысль, придают уверенность в действиях и тогда, когда не полностью осуществляются.
Функции политологии тесно между собой взаимосвязаны, они дополняют друг друга. Лишь взятые в единстве, в системе, они дают полное представление о назначении и социальной роли политологии.