Обратное прослеживание
Cтраница 2
Если TMS переводит противоречивую вершину в состояние внутри, то для того, чтобы найти и удалить одно из текущих предположений и перевести противоречивую вершину в состояние вне, вызывается обратное прослеживание по зависимостям. Этот процесс состоит из следующих шагов. [16]
Поскольку TMS доверяет решателю задач указывать на несовместность, помечая вершину как противоречивую, решателю задач также доверяется и использование немонотонных предположений для любого допущения, к которому можно применить обратное прослеживание. Поскольку TMS не проверяет те утверждения, которые представляют вершины, она отказывается, например, от возможности удаления подтверждений типа посылок. [17]
Неудовлетворимые цикличности иногда указывают на действительную несовместность допу щений той программы, которая использует систему поддержания истинности, и такая несовместность может быть провозглашена, например, в том случае, когда далекое обратное прослеживание исключило все другие возможности. Текущая версия TMS не обрабатывает Неудовлетворимые цикличности ( система зацикливается), поскольку для увеличения эффективности программы в нормальных случаях я удалил проверку наличия таких цикличностей, которая иногда обходится довольно дорого. В более живучей реализации такая проверка могла бы быть восстановлена. Более подробно эта проблема обсуждается при описании шага 5 в разд. [18]
Если рассматривать вершины, на которые опирается D, как опровержения выбранного предположения, то этот шаг напоминает приведение к противоречию в методе доказательства от противного. Обратное прослеживание пытается силой сделать виновника вне, делая его опорное подтверждение недействительным с помощью введения нового подтверждения, которое действительно тогда, когда неприятная вершина и остальные предположения находятся внутри, а другие опровержения данного виновника находятся вне. Если обратный прослеживатель ошибается в выборе виновника или опровержения, то основание будущего противоречия, по-видимому, будет включать D / и остающиеся предположения. Однако, если вяе-список подтверждения ( 3) непуст, D / будет предположением более высокого уровня, чем остальные предположения, и будет соответственно опровергаться первым. [19]
Как и ранее, если программа решения задач подтверждает не выбранную ранее альтернативу, TMS переводит умалчиваемую вершину в состояние вне. Однако обратное прослеживание приведет к новому эффекту: если А / поддерживает противоречие, то обратный прослеживатель может подтвердить ПА / с тем, чтобы перевести А / в состояние вне. [20]
Эти две особенности MYC1N тесно увязаны. Нет необходимости использовать обратное прослеживание, поскольку мы неотступно следуем за множеством независимых свидетельств и на заключительной стадии ранжируем гипотезы. Процесс обратного прослеживания требует больших затрат вычислительных ресурсов системы, так как приходится сохранять информацию о предыдущих этапах вычислений, к которым, возможно, придется еще возвращаться. Большой объем пространства состояний, в котором ведется поиск, требует значительных ресурсов памяти. На практике при этом используется механизм постраничного обмена между оперативной и дисковой памятью, что отрицательно сказывается на производительности системы в целом. Однако значительные вычислительные ресурсы отвлекаются на активизацию каждого потенциально подходящего правила, от чего приходится отказываться в некоторых системах. [21]
В главе 19 мы рассмотрим системы обработки правдоподобия ( truth maintenance) - усовершенствованный механизм фиксации решений, который существенно облегчает выполнение обратного прослеживания. В тех случаях, когда обратного прослеживания избежать невозможно, желательно, по крайней мере, быстро определить, в какую именно точку вычислений нужно вернуться, а не отменять по очереди все предыдущие операции, анализируя каждый раз последствия такой отмены. [22]
Методы, основанные на знаниях, являются реальной альтернативой алгоритмическому подходу в тех случаях, когда имеется достаточный объем знаний в конкретной предметной области, которые позволяют реализовать стратегию предложения и пересмотра или предложения и исправления. Но для реализации таких методов требуется довольно специфический механизм управления и обратного прослеживания решений, принимаемых программой. [23]
Такие управляющие знания о предметной области ( domain-specific control knowledge) позволяют программе R1 принимать решение о том, с чего начинать и как расширять структуру комплекса, не используя при этом сложной процедуры поиска. Как мы увидим далее, программа R1, как правило, не нуждается в обратном прослеживании неудовлетворительных решений, которое можно было бы использовать для отмены сформированной частичной конфигурации и замены ее новой. [24]
Обоснованная отмена предположений помогает при определении одного класса процедур обратного прослеживания, которые пересматривают множество текущих предположений в тех случаях, когда выясняется их несовместность. Одну из процедур такого рода мы, следуя Столлмену и Сассмену [53], называем процедурой обратного прослеживания по зависимостям. [25]
Заметим, что такой путь выстраивания альтернатив в последовательность не позволяет программе решения задач напрямую пересматривать ранее отвергнутые альтернативы. Если, предположим, мы хотим использовать особые правила для корректировки неправильных выборов виновников системой обратного прослеживания, то для представления линейно упорядоченных альтернатив требуются более сложные структуры. Для каждой альтернативы А / мы создаем три новых вершины: РА, которая означает, что А / является возможной альтернативой, NSA /, которая означает, что At - не является выбранной сейчас альтернативой, и ROA, которая означает, что А - является исключенной альтернативой. Мы предлагаем включать элементы в множество альтернатив путем подтверждения каждой РА / причиной цля включения А / в множество альтернатив. [26]
В главе 18 будет рассмотрена система, предназначенная для идентификации трехмерных структур протеинов в растворах. Комбинаторика, связанная с просмотром всех возможных вариантов компоновки молекул, совершенно очевидно не позволяет использовать исчерпывающий поиск или обратное прослеживание на сколько-нибудь значительную глубину. Поэтому программа организована таким образом, что в ней имеется несколько баз знаний, поддерживающих разные эвристики управления поиском в пространстве решений. Такая архитектура, получившая название системы с доской объявлений ( blackboard system), обеспечивает мощный механизм реализации таких стратегий, как последовательное уточнение частичных решений и восстановление после принятия неудачных решений. [27]
Отметим, что даже в системе PLANNER явные эффекты действия представляются в форме утверждений. Кроме того, как нам кажется, если эффекты действий полностью утеряны в процедурном представлении, очень трудно использовать стратегию анализа целей и средств или стратегию обратного прослеживания. [28]
Траектории частиц, зарегистрированные соответствующим детектором, экстраполируются в эмульсионную мишень. Погрешность экстраполяции определяет область, в к-рой производится поиск события или следов вторичных частиц. Путем обратного прослеживания по этим идентифицированным следам осуществляется поиск первичного взаимодействия и распадов вторичных частиц. [30]
Страницы: 1 2 3 4