Лекция: Поиск решений в иерархии пространств.

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

• поиск в факторизованном пространстве;
• поиск в фиксированном множестве пространств;
• поиск в изменяющемся множестве пространств.

Поиск в факторизованном пространстве.

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