Cтраница 2
В противном случае первая новая альтернативная ветвь, встречающаяся в процессе возврата, продолжается вниз опять по принципу сначала в глубину. Таким способом конечное дерево поиска будет в конце концов полностью просмотрено и будут найдены все решения программы. Стрелки указывают направление поиска; те из них, которые направлены вверх, указывают на то, что выполняется процесс возврата. [16]
Обозначим через А множество кандидатов. Бинарное дерево на А есть такое конечное дерево, в котором каждой нефиналь-иой вершине ( включая начальную) соответствуют ровно две следующие, а каждой финальной вершине ( у которой нет следующих за ней) приписан кандидат ( элемент из А), причем каждый кандидат появляется по крайней мере в одной финальной вершине. [17]
Первоначальное предписание предусматривает лишь преобразование конечного числа конечных входных слов. При этом ставится задача определения такого ограниченно-детерминированного оператора, который реализует нужное преобразование указанных слов; что же касается других возможных входных слов или продолжений заданных слов, то на оператор специальных ограничений не накладывается. В этом случае само первоначальное задание предстает в виде конечного дерева, для которого нужно найти бесконечное продолжение с конечным весом. [18]
Отметим также, что отношение неразличимости пли &-неразличи-мости, оставаясь по-прежнему симметричным, пе является транзитивным, когда сравнению подлежат деревья с неодинаковыми высотами. Так, например, на рис. 5.7 каждое из деревьев V и V неразличимо от дерева F, но вместе с тем V и V различимы друг от друга. Поэтому, в отличие от бесконечных деревьев, вообще говоря, невозможно разбиение множества всех ветвей конечного дерева на попарно непересекающиеся классы таким образом, чтобы две ветви были неразличимы тогда п только тогда, когда они принадлежат одному и тому же классу. [19]
Совокупность кодовых слов часто представляют в виде ( однокорневого) дерева с Y направленными ребрами, выходящими из каждой вершины и обозначающими различные элементы из Y. С этой целью каждой вершине приписывают последовательность элементов, соответствующих ребрам на пути от корня до этой вершины. Такое конечное дерево называется кодовым деревом. [20]