0

我有一个我认为是一个相当简单的约束满足问题，但找不到合适的包来实现算法。

我希望对一些点的数据集进行子集化。每个点都带有其他数据点的列表，如果要包含它，它必须从子集中排除。例如：

  points Must_Exclude
1      A            B,E
2      B            
3      C            F,G,H
4      D            
5      E            D
6      F            
7      G            H
8      H

我想在不违反任何规则的情况下最大化我可以放入子集中的点数。我的数据包含 1000 点。为此类问题设置的算法名称是什么？它们是我应该看的 R 中的任何包吗？我应该看看其他编程语言吗？

4

1 回答 1

3

求解作为具有八个二进制变量的整数线性规划 (ILP) 问题，每个变量代表从 A 到 H 的数据点之一，例如在包lpSolve的帮助下。

## Define inputs
obj <- rep(1, 8)                # 8 binary variables for A..H
A <- matrix(rbind(              # constraints:
    c(1,1,0,0,0,0,0,0),         # A <> B
    c(1,0,0,0,1,0,0,0),         # A <> E
    c(0,0,1,0,0,1,0,0),         # C <> F
    c(0,0,1,0,0,0,1,0),         # C <> G
    c(0,0,1,0,0,0,0,1),         # C <> H
    c(0,0,0,1,1,0,0,0),         # D <> E
    c(0,0,0,0,0,0,1,1)), 7, 8)  # G <> H
dir <- rep("<=", 7)             # all constraints '<='
rhs <- rep(1, 7)                # all right hand sides = 1
## maximise solution
sol <- lpSolve::lp("max", obj, A, dir, rhs,
                   all.bin = TRUE, num.bin.solns = 1)
sol$solution
## [1] 0 1 0 0 1 1 0 1

即，一种解决方案是（B，E，F，H）；当然，可能还有其他相同大小的组合，例如（A、D、F、G）。num.bin.solns 您可以通过将选项设置为某个值 > 1来获得更多解决方案。

于 2019-02-02T14:01:12.837 回答