Эвристический метод поиска

Метод редукции

Данный метод описывается с помощью и/или-графа. Реализация задачи подразумевает ее разбиение на совокупность подзадач, каждая из которых представляется дугой графа. Каждая дуга графа имеет свое назначение. Различают дизъюнктивные ветви (дуги «или») и конъюнктивные дуги (дуги «и»).

При выполнении подзадач с помощью дуги «или» должна быть выполнена хотя бы одна из подзадач текущей задачи. При реализации дуги «и» должны быть выполнены все подзадачи. Конъюнктивные дуги на графе объединяются специальным значком в виде дужки (рис. 4.5). При поиске результата на «и/или»-графе обычно применяются стратегии поиска «вширь» и «вглубь».

Рис. 4.5. Метод редукции

Процедура поиска слепым методом подразумевает, что порядок просмотра вершин определен заранее и не зависит от расположения цели. При увеличении пространства поиска это обстоятельство приводит к существенному росту объема памяти и времени, необходимых для решения задачи. Стремление сократить время поиска привело к созданию эвристических методов поиска, т.е. методов, использующих лишь некоторую информацию о предметной области. При этом методе просматривается не все пространство поиска, а только пути, приводящие к цели с наибольшей вероятностью. Для сокращения пространства поиска используются различные критерии, например, такие как мера «перспективности» вершины, позволяющая сократить объем перебираемых вершин без потери полноты информации.

Дата добавления: 2014-12-29