내 현재 코드는 5 개의 노드에 대한 정점 커버를 찾습니다. 여러 노드로 어떻게 일반화합니까? 재귀를 시도해야합니까?

저는 Vertex Cover Problem에 대한 최소 해결책을 찾으려고하는 프로젝트의 코드를 작성하고 있습니다. 그래프가 주어지면 그래프를 덮는 데 필요한 최소 정점 수를 찾으십시오.

전체 솔루션 공간에서 무차별 대입 검색을위한 프로그램을 작성하려고합니다. 지금 내 코드는 다음을 수행하여 작동합니다.

4 개의 노드를 사용한 예 :

• 모든 단일 노드 확인 : 솔루션 공간 : {1}, {2}, {3}, {4}
• 모든 노드 커플 확인 : 솔루션 공간 : {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}
• 모든 트리플 노드 확인 : 솔루션 공간 : {1,2,3}, {1,2,4}, {2,3,4}
• 모든 4 중 노드 확인 : 솔루션 공간 : {1,2,3,4}

현재 내 코드는 5 개 노드에서 작동합니다. 문제는 고정 된 수의 중첩 while 루프를 사용하여 이러한 순열을 검색한다는 것입니다. 6 개의 노드를 실행하려면 다른 While 루프를 추가해야합니다. 노드 수 자체가 변수가 될 수 있도록 코드를 일반화하려고합니다.

코드는 위의 솔루션 공간을 기반으로 이진수 행을 트리거하여 솔루션을 찾습니다. 예를 들어 시도중인 솔루션이 {1,2,4}이면 첫 번째, 두 번째 및 네 번째 이진 값은 1과 같게 설정됩니다. 세 번째는 0으로 설정됩니다. 이러한 입력을 사용하여 그래프를 포함하는지 여부를 결정하도록 행렬이 설정됩니다. 이것이 어떻게 작동하는지 더 보여주는 그림입니다.

이것을 노드 수에 일반화하는 방법에 대한 아이디어가 있습니까? 재귀에 대한 생각?

또한 코드에는 1 초 동안 대기하는 섹션이 있습니다. 이것은 단지 미학을위한 것이며 코드를보기에 재미있게 만드는 것 외에 어떤 목적도 제공하지 않습니다.

i = 0
j = 0
k = 0
m = 0

Range("Z22").Select

While i < 5 'Checks to see if a single vertice can cover the graph.


    Cells(5, 20 + i).Value = 1
    Application.Wait (Now + TimeValue("0:00:1"))
    If Cells(21, 13).Value = Cells(22, 26).Value Then

        GoTo Line1

    Else
        Cells(5, 20 + i) = 0
        i = i + 1
    End If

Wend

i = 0

While i < 4 'Checks to see if two vertices can cover the graph

Cells(5, 20 + i).Value = 1
j = i + 1


 While j < 5

      Cells(5, 20 + j).Value = 1
      Application.Wait (Now + TimeValue("0:00:1"))
    If Cells(21, 13).Value = Cells(22, 26).Value Then

        GoTo Line1

    Else
        Cells(5, 20 + j) = 0
        j = j + 1
    End If

 Wend

Cells(5, 20 + i) = 0
i = i + 1

Wend


k = 0


While k < 3 'Checks to see if three vertices can cover the graph

Cells(5, 20 + k) = 1
 i = k + 1
    While i < 4

    Cells(5, 20 + i).Value = 1
    j = i + 1


        While j < 5

             Cells(5, 20 + j).Value = 1
             Application.Wait (Now + TimeValue("0:00:1"))
           If Cells(21, 13).Value = Cells(22, 26).Value Then

               GoTo Line1

           Else
               Cells(5, 20 + j) = 0
               j = j + 1
           End If

        Wend

    Cells(5, 20 + i) = 0
    i = i + 1

      Wend

Cells(5, 20 + k).Value = 0
k = k + 1

Wend



While m < 2 'Checks to see if four vertices can cover the graph

Cells(5, 20 + m).Value = 1
 k = m + 1
    While k < 3

    Cells(5, 20 + k) = 1
     i = k + 1
        While i < 4

        Cells(5, 20 + i).Value = 1
        j = i + 1


            While j < 5

                 Cells(5, 20 + j).Value = 1
                 Application.Wait (Now + TimeValue("0:00:1"))
               If Cells(21, 13).Value = Cells(22, 26).Value Then

                   GoTo Line1

               Else
                   Cells(5, 20 + j) = 0
                   j = j + 1
               End If

            Wend

        Cells(5, 20 + i) = 0
        i = i + 1

          Wend

    Cells(5, 20 + k).Value = 0
    k = k + 1

    Wend

Cells(5, 20 + m).Value = 0
m = m + 1

Wend



If Cells(21, 13).Value <> Cells(22, 26).Value Then 'Final effort
    Range("T5:X5") = 1
    MsgBox ("It takes all five vertices.")

End If





Line1:
 Application.DisplayAlerts = True

End Sub