30503-1 (Методы решения задач), страница 2

Все неудачи, возникшие при поиске в одном направлении, не запоминаются при переходе к поиску в другом направлении. Та же самая причина неудачи может заново обнаруживаться и на новом направлении.

Осуществлять возврат целесообразно не к состоянию, непосредственно предшествующему данному, а к тому состоянию, которое является причиной возникновения неудачи. В используемых нами терминах причиной неудач являются предположения, т.е. недоказуемые утверждения. Поэтому при обнаружении неудачи необходимо возвращаться в состояние, где это предположение было сделано, и испытывать другое предположение.

Этот метод поиска называют поиском, направляемым зависимостью.

3.4. ПОИСК С ИСПОЛЬЗОВАНИЕМ НЕСКОЛЬКИХ МОДЕЛЕЙ

Все методы поиска, рассмотренные до сих пор, использовали при представлении проблемной области какую-то одну модель, т.е. рассматривали область с какой-то одной точки зрения. При решении сложных задач в условиях ограниченных ресурсов использование нескольких моделей может значительно повысить мощность системы. Объединение в одной системе нескольких моделей дает возможность преодолеть следующие трудности.

• переход с одной модели на другую позволяет обходить тупики, возникающие при поиске в процессе распространения ограничений.

• использование нескольких моделей позволяет в ряде случаев уменьшить вероятность потери хорошего решения (следствие неполного поиска, вызванного ограниченностью ресурсов) за счет конструирования полного решения из ограниченного числа частичных кандидатов путем их расширения и комбинации.

• наличие нескольких моделей позволяет системе справляться с неточностью (ошибочностью) данных.

Следует отметить, что использование нескольких моделей требует дополнительных знаний о том, как создавать и объединять различные точки зрения.

3.5. ВЫБОР МЕТОДА РЕШЕНИЯ ЗАДАЧ

Выбор метода решения задачи зависит прежде всего от сложности задачи, которая определяется особенностями проблемной области и требованиями, предъявляемыми пользователем к решению задачи. Для преодоления трудностей, вызванных большим пространством поиска, используются методы, основанные на введении иерархии пространств (конкретных, абстрактных и метапространств). Простейший из этих методов основывается на факторизуемости пространства решений, что позволяет производить раннее отсечение. Метод обеспечивает получение всех решений. Если пространство поиска не удается факторизовать, но при этом не требуется получать все решения или выбирать лучшее, то могут быть применены методы, использующие иерархию однородных абстрактных пространств. Если пространство поиска таково, что любая задача может быть сведена к известной заранее последовательности подзадач, то используется фиксированное абстрактное пространство.

Эффективность этого метода определяется возможностью использовать безвозвратную стратегию. В случае, если подзадачи взаимозависимы, т.е. для решения некоторой подзадачи может требоваться информация, получаемая другой подзадачей, и подзадачи не могут быть упорядочены, целесообразно применять принцип наименьших свершений. Этот подход позволяет приостанавливать решение подзадачи, для которой недостает информации, переходить к решению другой подзадачи и возвращаться к исходной задаче, когда отсутствующая информация станет доступной. (поиск в иерархии пространстве)

Для преодоления трудностей, вызванных неполнотой и (или) неточностью данных (знаний), используют вероятностные, размытые и точные методы. Все эти методы основываются на идее увеличения надежности путем комбинирования фактов и использования метазнаний о возможностях комбинирования фактов.

Для преодоления неадекватности модели проблемной области используются методы, ориентированные на использование нескольких моделей. Эти методы позволяют объединить возможности различных моделей, описывающих проблемную область с различных точек зрения. Кроме того, использование нескольких моделей позволяет уменьшить вероятность потери хорошего решения, несмотря на неполноту поиска, вызванную ограниченностью вычислительных ресурсов.