Алгоритм Цепочка

Привет, сегодня поговорим про алгоритм цепочка, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое алгоритм цепочка , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Задание

Задан набор неповторяющихся пар (A_i,A_j), A_i, A_j принадлежат множеству А={A₁, A₂, ..., A_n}. Необходимо составить цепочку максимальной длины по правилу

(A_i,A_j)+(A_j,Ak)=(A_i,A_j,A_k).

При образовании этой цепочки любая пара может быть использована не более одного раза.

Ввод

Входящими данными является матрица смежности, составленая по такому правилу: C[i,j]=1, если в наборе есть пара (Ai,Aj) и C[i,j]=0 иначе.

Вывод

Вывести последовательность звеньев самой длинной цепочки в формате Ai Ak ... Об этом говорит сайт https://intellect.icu . An.

Решение     [вверх]

Будем строить все возможные цепочки (по правилу, данному в условии) и искать среди них ту, которая имеет максимальную длину. Для этого воспользуемся поиском в глубину. После построения цепочки, к которой уже нельзя присоединить ни одного звена, сравниваем длину текущей цепочки с длиной максимальной. Если текущая цепочка длиннее, то запоминаем ее и считаем текущую цепочку максимальной. Формальный алгоритм приведен ниже.

Формальное описание

Chain()
1. Создать матрицу смежности для цепочки.
2. Для каждой вершины графа повторить пп.2.1-2.4:
   2.1. Поиском в глубину найти неувеличивающийся маршрут из текущей 
        вершины.
   2.2. Если найденный маршрут длиннее максимального, то сохранить 
        данный маршрут и считать его максимальным.
   2.3. Найти следующий маршрут для текущий вершины. 
   2.4. Если маршрут не найден, то перейти к следующей вершине.
3. Вывести самый длинный маршрут.

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