Изменения

''continue or find path'' //''недетерминировано выбираем переходить к следующей вершине или угадываем путь до данной''

Enum перебирает все вершины на логарифмической памяти и пытается угадать путь до этой вершины из ''s''.Для угадывания пути достаточно логарифмической памяти, так как необходимо помнить лишь текущую вершину пути и пытаться угадывать следующую. Enum является недетерминированой программой и если существует порядок исполнения, чтобы достичь ACCEPT, то он достигается. Теперь имея Enum, можно индуктивно находить ''r_i''. Очевидно, что <tex>r_0 = 1</tex>, так как <tex>R_0</tex> содержит единственную вершину ''s''. Пусть известно значение ''r_i''. Напишем программу, которая на логарифмической памяти будет находить ''r_{i + 1}''. <code>Next(s, i, r_i, G) r := 1 //''<tex>r_{i+1}</tex> хотя бы один, так как <tex>s \in R_{i + 1}</tex>'' '''for''' v = 1 .. n; <tex>v \neq s</tex> '''do''' //''перебираем все вершины графа, кроме s -- это кандидаты на попадание в <tex>R_{i + 1}</tex>'' '''for''' u : (u,v)∈E '''do''' //''перебираем все ребра, входящие в v'' Enum(s, i, r_i, G) //''перечисляем все вершины из <tex>R_i</tex>'' '''if''' u in output '''then''' //''если u одна из них, то <tex>v \in R_{i + 1}</tex>'' r++ //''увеличиваем количество найденных вершин и переходим к рассмотрению следующего кандидата'' break write r</code> Данный алгоритм изначально учитывает ''s'', а затем перебирает всех возможных кандидатов на попадание в <tex>R_{i + 1}</tex>. Для каждого из них перебираются все ребра, в него входящие. Затем перечисляются все вершины из <tex>R_i</tex> и, если начало нашего ребра было перечислено, то <tex>v \in R_{i + 1}</tex>. Алгоритм использует логарифмическую память, так необходимо хранить лишь ''v'', ''u'', ''r'' и еще поочередно значения полученные в результате вызова Enum. Теперь можно написать алгоритм, который будет недетерминировано решать задачу ''STNONCON'' на логарифмической памяти. Он будет состоять из двух частей: вычисление <tex>r_{n-1}</tex> и перечисление всех вершин