Программные продукты и системы

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

Говоря о стратегии поиска, прежде всего следует упомянуть о стратегиях, основанных на упорядочении (ordering-based strategies). Необходимо отметить, что среди них имеются стратегии, ориентированные как на расширение множества дизъюнктов для метода резолюции, так и на его сокращение путем поглощения. Упорядочение здесь понимается как наличие обоснованного порядка выражений, подлежащих процедуре поиска вывода. Стратегии, основанные на упорядочении, используют поиск только наилучшего (с применением эвристик) и, как правило, не очень восприимчивы к разрешению целей. Однако использование в них семантических (например, в семантической резолюции) или поддерживающих (например, в резолюции множества поддержки) требований настраивает поиск на разрешение целей. Стратегии, основанные на упорядочении, являются синтетическими, получаемыми образованием одних цепочек вывода из других.

Подробное описание дается в статье «Параллельный вывод в методе аналитических таблиц», авторы: Вагин В.Н., Зо Мью Хтет (Московский энергетический институт (технический университет)).