用最少数量的顶点覆盖k个边

Question

[我正在尝试编写一种DP算法，该算法计算我们需要选择的最小顶点数才能覆盖图形上的k个边。

到目前为止我写的代码是：

#include<iostream>

#include<vector>

#include<list>

#include<set>
#include<algorithm> 
#include <tuple>

using namespace std;

int edges[10000][10000]={0}; //which edges I have covered
int adjacency[10000][10000]={0}; //the graph in an array
int K;
int sum=0;

int DP(int i,int j){
    if (j==K) return 1;
    int neys=0; //number of neighbors
    for (int m=0; m<10000; m++){ //scan the neighbor array
         if(adjacency[i][m]==1) {  //if I find a neighbor
            if(edges[i][m]==0) neys++; //if I have not taken this edge before into consideration
            edges[i][m]=1; //mark it as covered
         }
    }
    printf("i: %d\n",i);
    for (int m=0; m<10000; m++) //for all neighbors of i
        if(adjacency[i][m]==1) { //if m is a neighbor
            sum=min(1+DP(m,j+neys),DP(m,j)); //then take the minimum if I include it or not
            printf("sum: %d\n",sum);
        }
    return sum;
}

int main() {

    int N;
    int begin;
    scanf("%d %d",&N,&K);


    for (int i = 0; i < N - 1; i++) {

        int u,v;

        scanf("%d %d",&u,&v);
        if (i==0) begin=u;
        adjacency[u][v]=1;


    }

    int sol=DP(begin,0);
    printf("%d\n",sum);
}

此代码由于某种原因产生了错误的输出。但是，如果这是正确的，我怀疑它不会很快（指数复杂度）。您可以建议一种算法吗？

示例：用于输入：9 61 21 31 42 52 63 74 84 9

预期输出为2

我的程序输出0。

Answer 1

这是JavaScript中的幼稚递归（被大量注释），它使用每个父顶点到子节点的简单映射，并且还用子树中的边数装饰。 （该代码可能会受益于更多示例案例，以进行改进，或者可能会裁定概念不正确。）

想法是将每个子代与其父代一起对待，如果选择了父代，则调用者已经从k中减去了子代的边。递归调用既返回到较早的子代（具有相同的父代分配状态），又尝试从当前子树中尝试不同的k值，选择还是跳过子代本身，这是递归中的选择。 >

重复返回元组(c, m)，其中c是成本（顶点数），m是覆盖的边数（可以大于k）。

每个节点的搜索空间为O(|edges in subtree|)。似乎可能O(|V| * k)？

// Returns a tuple, `(c, m)`, where `c` 
// is the cost (number of vertices) and `m`
// is the number of edges covered (which 
// could be greater than `k`).
// 'u' is the root of the tree/subtree,
// 'i' is the index of a child of 'u',
// 'childEdge' is 1 if the root is
// not used, matching the edge count
// we can add to each child chosen.
// If 'childEdge' is 0, it implies
// k was already adjusted by the caller.
function f(map, u, i, k, childEdge){
  // Base case
  if (k <= 0)
    return [0, 0]

  // Recursion limit
  if (i < 0)
    return [Infinity, 0]
  
  // Without the ith child
  let best = f(map, u, i-1, k, childEdge)
    
  // Current child
  let v = map[u].children[i]
  
  // Child has no subtree,
  // it's never optimal to use a leaf
  if (!map[v])
    return best
  
  /* Try different edge quantities from the subtree */
  
  let max = Math.min(k, map[v].numEdges)
  let l = map[v].children.length
  
  for (let j=1; j<=max; j++){
    // If we choose the child, subtract
    // its children's count but apply a 0
    // childEdge, as well as any childEdge
    // for the child-as-parent. numEdges includes
    // edges from the child-as-parent, subtract them.
    let max_j = (j - l) 
    let [ac, am] = f(map, v, l-1, max_j, 0)
    let [fac, fam] = f(map, u, i-1, k-max_j-l-childEdge, childEdge)
    
    let [bc, bm] = f(map, v, l-1, j, 1)
    let [fbc, fbm] = f(map, u, i-1, k-j, childEdge)
    // Add 'v' and the edges to its
    // children to the branch
    // where 'v' was used.
    ac = ac + 1
    am = am + l + childEdge

    let a = [ac + fac, am + fam]
    let b = [bc + fbc, bm + fbm]

    // Choose between a and b
    best = compareAndGetBest(
      best,
      compareAndGetBest(a, b)
    )
  }
  return best
}

// [c, m] are [cost, num_edges_covered]
// Return larger m if possible
function compareAndGetBest(a, b){
  if (a[0] == b[0]){
    return a[1] >= b[1] ? a : b
  } else {
    return a[0] < b[0] ? a : b
  }
}

function getNumEdges(map, u){
  if (!map[u]){
    return 0
    
  } else {
    let count = 0
    for (let v of map[u].children){
      if (map[v]){
        map[v]["numEdges"] = getNumEdges(map, v)
        count += 1 + map[v]["numEdges"]
      } else {
        count += 1
      }
    }
    return map[u]["numEdges"] = count
  }
}

function getChildrenMap(edges){
  return edges.reduce(function(acc, [u, v]){
    if (acc[u])
      acc[u].children.push(v)
    else
      acc[u] = {children: [v]}
    return acc
  }, {})
}

function partialVertexCover(edges, k){
  var childrenMap = getChildrenMap(edges)
  getNumEdges(childrenMap, 1)
  var l = childrenMap[1].children.length

  console.log(JSON.stringify(childrenMap) + "\n")

  return compareAndGetBest(
    f(childrenMap, 1, l-1, k, 1),
    f(childrenMap, 1, l-1, k-l, 0)
  )
}

function main(){
  var edges = [
    [1, 2],
    [1, 3], //        1
    [1, 4], //     /  |  \
    [2, 5], //    2   3   4
    [2, 6], //   / \  |  / \
    [3, 7], //  5   6 7 8   9
    [4, 8],
    [4, 9]
  ]

  var k = 6

  console.log(partialVertexCover(edges, k) + "\n")

  edges = [
    [1, 2],
    [1, 3], //       1
    [1, 4], //    /  |  \
    [2, 5], //   2   3   4
    [3, 6], //   |   |   |
    [4, 7]  //   5   6   7
  ]

  console.log(partialVertexCover(edges, k) + "")
}

main()