Поиск в иерархии пространств

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

Важность иерархических методов при работе с большими пространствами понята давно. В 1963 г. М.Минский ввел понятие «островков планирования», уменьшающее время поиска по экспоненте – В графе с 10 ребрами, исходящими из каждой вершины, 20-шаговый поиск может потребовать 10хх20 попыток, что нереально организовать, в то время, как введение четырех лемм, или последовательных подцелей может уменьшить поиск до 4х10хх5 попыток, которые машина может выполнить. Поэтому имеет смысл приложить даже огромные усилия, чтобы выявить такие «островки» при решении сложных задач.

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

Пусть требуется переехать из центра города А в центр города Б. Если осуществлять поиск требуемого пути на детальной карте, содержащей все улицы во всех городах, встретившихся по дороге, то задача может стать практически неразрешимой. При определении пути из города А в город Б целесообразно спланировать маршрут по крупномасштабной карте (т.е. осуществить поиск в абстрактном пространстве), а затем по детальной карте спланировать выезд из города А и въезд в город Б.

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

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

Дата добавления: 2014-01-05