Доказательство рекурсивного алгоритма

Question

Мне нужно доказать рекурсивный алгоритм. Обычно это делается с использованием некоторого целочисленного значения внутри кода в качестве базового случая для индукции, например, при вычислении факториала, но с обходным графиком. Я не знаю, с чего начать. Вот мой алгоритм. Подписчики не конвертировались.

Алгоритм

Гол: траверса график, создавая глубину первой связующего дерева, и вычислить последний потомок каждой вершины, которая является потомок VK, который имеет самое высокое значение к

Вход: A connected graph G with vertices ordered v1, v2, v3 … vn

Выход: A spanning tree T where each vertex in T has had its Last vertex computed

Инициализация Устанавливает каждую вершину на невидимую. Пусть ak обозначает список всех вершин, смежных с vk. Обозначим через lk Последний потомок vk. Обозначим через ck список всех дочерних элементов vk в остовном дереве. Пусть dk обозначает список всех вершин, являющихся потомками vk в охватывающем дереве, включая vk.

dfs(vk){ 

    add vK to T 
    set v to visited 
    lk = vk 
    add vk to dk 
    foreach(vertex m in ak with lowest value of k){ 
     add m to ck 
     add dfs(m) to dk 
    } 
    foreach(vertex vc in dk){ 
     if(c > k){ 
      lk = vc 
     } 
    } 
    if(k = 1) 
     return T 
    else 
     return dk 
} 

Это для группового проекта в школе, так что я не хочу все доказательства, но отправную точку и некоторое направление было бы весьма признателен.

Answer 1

Мне сложно понять ваш псевдокод. В лучшем случае кажется неясным, вероятно, алгоритм даже не работает. Некоторые вопросы:

• Свойство «visited» установлено, но не используется.
• T Предполагается, что это дерево. Но вы только добавляете вершины, нет ребер. Без краев это, конечно, не остовное дерево. Если вы рассмотрите все ребра из исходного графика между узлами в T-части T, тогда он будет содержать циклы и не будет также деревом.
• Почему вы вычисляете lk, если он никогда не используется?
• Является ли параметр вашей функции dfs как k вместо vk? В противном случае k никогда не устанавливается, но используется.
• Я не вижу, как заканчивается ваша рекурсия. Я не вижу никаких защит для базового случая (за исключением, может быть, условия «с наименьшим значением k» в вашем цикле, что я не понимаю, потому что я понимаю из остальной части кода, что k является входным параметром функция и, следовательно, m не зависит от нее).

Так что позвольте мне рассказать вам о проверке рекурсивных алгоритмов на графиках в целом. Помимо индукции по натуральным числам, о которых вы упомянули, есть также Structural Induction. Он имеет базовый корпус и индуктивный шаг, точно так же, как индукция, которую вы знаете. Но базовый случай обычно является тривиальной составляющей вашей структуры данных, и индуктивный шаг доказывает ваше предложение для более сложных композитов, предполагая, что ваше предложение выполняется для его менее сложных компонентов.

Например, вы можете доказать алгоритм над деревьями, доказав, что он работает для листьев (ваш базовый случай) и доказывает, что он работает для всего дерева, предполагая, что ваш алгоритм работает для левого и правого суб- деревья корня (шаг индукции).

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