программа рекурсии для максимально независимого множества в графе

Question

У меня возникают трудности при написании программы для вышеуказанной проблемы .. У меня есть следующий график ....

A-----B------C       D
A is connected to B
B is connected to C
D is connected with no body!! 
The maximum Independent set in this is {A,C, D}... 

Матрица смежности для графика ниже: -

Я нарисовал следующий порядок дерева решений для решения проблемы: -

• Первым элементом каждого узла является индекс.

• Вторым элементом каждого узла является набор, в котором хранятся независимые элементы графа.

• Левая ветвь говорит, что я не буду рассматривать элемент, а правая ветвь говорит, что я буду рассматривать элемент с индексом, указанным первым элементом узла.

Итак, как вы можете ясно видеть, на каждом узле я не рассматривал элемент, указанный индексом первого элемента узла, и я рассмотрел элемент, может ли он быть вставлен в независимый набор.

Я хочу написать программу для этого на Python !! Я новичок, и все еще на ранних стадиях реализации программы посредством рекурсии.

любезно помогите !!

Я написал следующий код: - но он мне не нравится .. Он как-то работает ... Пожалуйста, опыт Люди могут добавить в ваши комментарии ... Я все еще учусь в рекурсии ..

def maxset(tab, i, set):
    global numcalls
    numcalls += 1
    if i == 0:
        flag = 0
        for s in set:
            if tab[i][s]:
                return 0
        if i not in set:
            set.append(i)
        return len(set)

    without_i = maxset(tab, i-1, set)

    flag = 0
    for s in set:
        if tab[i][s]:
            return without_i
    if i not in set:
        set.append(i)
    with_i = maxset(tab,i-1,set)
    return max(without_i, with_i)


tab = [[0,1,0,0],[1,0,1,0],[0,1,0,0],[0,0,0,0]]
#tab = [[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]
set = []
numVertIndex = 3 #### 0,1,2,3
numcalls = 0
print(maxset(tab, numVertIndex, set))
print(set)
print (numcalls)

Answer 1

Существует хорошо известный и простой алгоритм решения этой проблемы:

1. Изначально раскрасьте все вершины в зеленый цвет.
2. Найдите зеленую вершину. Цвет соседей красный.
3. Для каждой красной вершины раскрасьте ее зелеными соседями в красный. (Вот часть рекурсии)
4. Если красных вершин с зелеными соседями больше нет, множество красных вершин определяет максимально связанный компонент.
5. Повторяйте от 2 до тех пор, пока все вершины не станут красными и все компоненты не будут обнаружены.

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

Answer 2

Что касается вашего кода:

1. Имеется одна критическая ошибка: set никогда не копируется. Обычно это нормально, но это не так. Давайте посмотрим ваш код. После вычисления without_i исходное установленное значение может быть изменено. В этом случае для вычисления with_i используется неверное установленное значение. Простейший пример случая, который я могу себе представить, это tab = [[0,1,0],[1,0,0],[1,0,0]].

2. Незначительные ошибки: flag не используется? Также numcalls, кажется, создан для упрощения отладки. Поэтому я исключаю это из моего примера кода.

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

Пример моего кода:

def maxset( tab ):
    def maxset_detail(tab, i, set):
        if any( tab[i][s] for s in set ):
            return i and maxset_detail(tab, i-1, set) or 0
        if (i == 0):
            set.append(i)
            return len(set)
        set_copy = set[:] + [i]
        without_i = maxset_detail(tab, i-1, set)
        with_i = maxset_detail(tab, i-1, set_copy)
        if ( with_i > without_i ):
            set[:] = set_copy
            return with_i
        else:
            return without_i
    set = []
    maxset_detail(tab, len(tab)-1, set )
    return set