-1

我正在尝试编写一个 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 6 1 2 1 3 1 4 2 5 2 6 3 7 4 8 4 9

预期输出为 2

我的程序输出 0。

在看到下面的答案后，我想出了以下代码：

#include <iostream>
#include <tuple>
#include <bits/stdc++.h>

using namespace std;

using MyKey = tuple<int, int, int, int>;

map<MyKey, int> glob;

int numEdges[100000];

tuple<int,int> compareAndGetBest(tuple<int,int> a, tuple<int,int> b){
 if (get<0>(a) == get<0>(b)){
    if (get<1>(a) >= get<1>(b)) return a;
    else return b;
 }
 else {
    if (get<0>(a) < get<0>(b)) return a;
    else return b;
 }
}

tuple<int,int> f(vector<vector<int>> map, int u, int i,int k,int childEdge){
  //printf("u: %d , i: %d k: %d childEdge: %d\n",u,i,k,childEdge);
  if (!glob[{u,k,i,childEdge}]==0) return make_tuple(glob[{u,k,i,childEdge}],k);


  tuple <int,int> result;

  if (k <= 0){
    result=make_tuple(0,0);
    glob[{u,k,i,childEdge}]=get<0>(result);
    return result;
  }


  if (i < 0){
    result=make_tuple(1000000,0);
    glob[{u,k,i,childEdge}]=get<0>(result);
    return result;
  }


  tuple <int,int> best = f(map, u, i-1, k, childEdge);



  int v = map[u][i];

  if (map[v].size()==0){  
    glob[{u,k,i,childEdge}]=get<0>(best);   
    return best;
  }


  int max = min(k, numEdges[v]);

  int l = map[v].size();


  for (int j=1; j<=max; j++){
    int max_j = (j - l);
    tuple <int,int> a   = f(map, v, l-1, max_j, 0);
    tuple <int,int> fa  = f(map, u, i-1, k-max_j-l-childEdge, childEdge);

    tuple <int,int> b  = f(map, v, l-1, j, 1);
    tuple <int,int> fb = f(map, u, i-1, k-j, childEdge);


    get<0>(a)  = get<0>(a) + 1;
    get<1>(a)  = get<1>(a) + l + childEdge;


    tuple <int,int> na = make_tuple(get<0>(a) + get<0>(fa), get<1>(a) + get<1>(fa));

    tuple <int,int> nb = make_tuple(get<0>(b) + get<0>(fb), get<1>(b) + get<1>(fb));

    best = compareAndGetBest(best, compareAndGetBest(na, nb));

  }

  glob[{u,k,i,childEdge}]=get<0>(best);
  return best;
}

int getNumEdges(vector<vector<int>> map,int u){
    int count=0;

    if (map[u].size()==0){
        return 0;
    }

    else {
        for (auto v: map[u]){
            if (map[v].size()>0){
                numEdges[v]=getNumEdges(map,v);
                count += 1 + numEdges[v];
            }
            else count +=1;
        }
    }

    numEdges[u]=count;

    return numEdges[u];

}

int main(int argc,char **argv){
    int N,K;
    FILE *fp;
    vector<vector<int> > myvec;
    fp=fopen(argv[1],"r");
    fscanf(fp,"%d %d",&N,&K);
    myvec.resize(N+1);
    for(int i=1 ; i<N ; i++){
        //printf("i: %d \n",i);
        int u, v;
        fscanf(fp,"%d %d",&u,&v);
        myvec[u].push_back(v);
    }

    int whatever=getNumEdges(myvec,1);
    //for (int k=1;k<=N-1;k++) printf("numEdges[%d]= %d \n",k,numEdges[k]);

    int l = myvec[1].size();

    tuple<int,int> a = f(myvec, 1, l-1, K, 1);
    tuple<int,int> b = f(myvec, 1, l-1, K-l, 0);

    tuple<int,int> ans=compareAndGetBest(a, make_tuple(get<0>(b)+1,get<1>(b)+l));
    printf("%d\n",get<0>(ans));
}
4

1 回答 1

0

（这个答案适用于树木，这似乎是这个问题的意义所在，在这里给出了一个非常相似的树，而这里给出了一个封闭的树。）

这是 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")
  
  let a = f(childrenMap, 1, l-1, k, 1)
  let [bc, bm] = f(childrenMap, 1, l-1, k-l, 0)

  return compareAndGetBest(a, [bc + 1, bm + l])
}

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()

于 2020-01-07T11:54:27.440 回答