我当前的代码找到五个节点的顶点覆盖。我如何将它推广到任意数量的节点？我应该尝试递归吗？

Question

我正在为一个项目编写代码，该项目试图找到顶点覆盖问题的最小解：给定一个图，找到覆盖该图所需的最小顶点数。

我正在尝试编写一个程序，用于在整个解决方案中进行暴力搜索 space。现在，我的代码通过执行以下操作来工作：

使用 4 个节点的示例：

检查每个节点：解决方案Space：{1}、{2}、{3}、{4}
检查每一对节点：解决方案Space：{1,2}、{1,3}、{1,4}、{2,3}、{2,4}、{3 ,4}
检查节点的每个三元组：解决方案Space：{1,2,3}，{1,2,4}，{2,3,4}
检查每个四元组节点：解决方案Space：{1,2,3,4}

目前，我的代码适用于 5 个节点。问题是它使用固定数量的嵌套 while 循环搜索这些排列。如果我想要运行 6 个节点，我需要添加另一个 While 循环。我试图概括代码，以便节点数本身可以是一个变量。

代码根据上面的解决方案space通过触发一行二进制数来找到解决方案，例如，如果正在尝试的解决方案是{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

Answer 1

这对任意 n 进行组合；不使用递归。我必须考虑递归是否适用（让它更简单？）

Option Explicit

Const nnodes = 6
Dim a&(), icol&

Sub Main()
  ThisWorkbook.Sheets("sheet1").Activate
  Cells.Delete
  Dim i&, j&
  For i = 1 To nnodes ' from 1 to nnodes
    ReDim a(i)
    For j = 1 To i ' -- start with 1 up
      a(j) = j
    Next j
    Cells(i, 1) = i ' show
    icol = 2 ' for show
    Do ' -- show combination and get next combination
    Loop While doi(i)
  Next i
End Sub

Function doi(i) As Boolean ' show and get next
  Dim j&, s$
  For j = 1 To i ' build string for show
    If j > 1 Then s = s & ","
    s = s & Str$(a(j))
  Next j
  Cells(i, icol) = "{" & s & "}" ' show
  icol = icol + 1
  ' -- get next combination (if)
  For j = i To 1 Step -1 ' check if any more
    If a(j) < nnodes - i + j Then Exit For
  Next j
  If j < 1 Then doi = False: Exit Function ' no more
  a(j) = a(j) + 1 ' build next combination
  While j < i
    a(j + 1) = a(j) + 1
    j = j + 1
  Wend
  doi = True
End Function

编辑：将 "permutation" 更改为 "combination"。
EDIT2：我一直回到递归——它确实简化了代码：

Option Explicit

Dim icol& ' for showing combinations

Sub Main() ' get (non-empty) partitions of nnodes
  Const nnodes = 6
  Dim k&
  ThisWorkbook.Sheets("sheet2").Activate
  Cells.Delete
  For k = 1 To nnodes ' k = 1 to n
    Cells(k, 1) = k ' for showing
    icol = 2
    Call Comb("", 0, 1, nnodes, k) ' combinations(n,k)
  Next k
End Sub

Sub Comb(s$, lens&, i&, n&, k&) ' build combination
  Dim s2$, lens2&, j&
  For j = i To n + lens + 1 - k '
    If lens = 0 Then s2 = s Else s2 = s & ", "
    s2 = s2 & j
    lens2 = lens + 1
    If lens2 = k Then ' got it?
      Cells(k, icol) = "{" & s2 & "}" ' show combination
      icol = icol + 1
    Else
      Call Comb(s2, lens2, j + 1, n, k) ' recurse
    End If
  Next j
End Sub

我当前的代码找到五个节点的顶点覆盖。我如何将它推广到任意数量的节点？我应该尝试递归吗？

My current code finds the vertex cover for five nodes. How would I generalize it to any number of nodes? Should I try recursion?

recursion

vba

loops

while-loop

nested-loops

我当前的代码找到五个节点的顶​​点覆盖。我如何将它推广到任意数量的节点？我应该尝试递归吗？

My current code finds the vertex cover for five nodes. How would I generalize it to any number of nodes? Should I try recursion?

recursion

vba

loops

while-loop

nested-loops

我当前的代码找到五个节点的顶点覆盖。我如何将它推广到任意数量的节点？我应该尝试递归吗？