Задача 20.
N колец сцеплены между собой (задана матрица A(n*n), A(i,j)=1 в случае, если кольца i и j сцеплены друг с другом и A(i,j)=0 иначе). Удалить минимальное количество колец так, чтобы получилась цепочка.
|
Решение задачи 20.
Предполагаемый вариант решения использует полный перебор всех вариантов. В качестве первого звена цепочки берем последовательно каждое из N колец. Ищем сцепленные с этим кольцом, выбираем среди них одно (все остальные кольца будут считаться удаленными - т.е. строки и столбцы с номерами этих колец должны обнуляться). С этим изменением задача сводится к задаче 1 (Графы). Действительно, если мы найдем максимальный путь в графе (в данном случае - максимальную длину цепочки в начальной конструкции), то мы минимизируем количество выброшенных колец.
|
