1

例如，这是一个矩阵：

[1, 0, 0, 0],
[1, 1, 0, 0],
[1, 0, 1, 0],
[1, 1, 1, 0],
[1, 1, 1, 1],

我想找到一些总和等于 [4, 3, 2, 1] 的行。预期的答案是行：{0,1,3,4}。因为：

[1, 0, 0, 0] + [1, 1, 0, 0] + [1, 1, 1, 0] + [1, 1, 1, 1] = [4, 3, 2, 1]

是否有一些著名的或相关的算法来解决这个问题？

感谢@sascha 和@N。沃达的评论。为了澄清这一点，我在这里提供了更多细节。

在我的问题中，矩阵将有大约 50 行和 25 列。但回声行将只有少于 4 个元素（其他为零）。每个解决方案都有 8 行。

如果我尝试所有组合，c(8, 50) 大约是 5.5 亿次尝试。太复杂了。所以我想找到一个更有效的算法。

4

2 回答 2

2

如果您想跳到使用求解器，我会推荐它。这是一个非常简单的整数程序。以下解决方案使用python，python 的pyomo数学编程包来制定问题，以及 COIN OR 的cbc整数程序和混合整数程序的求解器，需要单独安装（免费软件）可用： https ://www.coin-or.org/downloading/

这是一个包含您的数据的示例，后面是一个包含 100,000 行的示例。上面的示例立即解决，100,000 行示例在我的机器上大约需要 2 秒。

# row selection Integer Program
import pyomo.environ as pyo

data1 = [   [1, 0, 0, 0],
            [1, 1, 0, 0],
            [1, 0, 1, 0],
            [1, 1, 1, 0],
            [1, 1, 1, 1],]


data_dict = {(i, j): data1[i][j] for i in range(len(data1)) for j in range(len(data1[0]))}

model = pyo.ConcreteModel()

# sets
model.I = pyo.Set(initialize=range(len(data1)))     # a simple row index
model.J = pyo.Set(initialize=range(len(data1[0])))  # a simple column index

# parameters
model.matrix = pyo.Param(model.I , model.J, initialize=data_dict)   # hold the sparse matrix of values
magic_sum = [4, 3, 2, 1 ]

# variables
model.row_select = pyo.Var(model.I, domain=pyo.Boolean) # row selection variable

# constraints
# ensure the columnar sum is at least the magic sum for all j
def min_sum(model, j):
    return sum(model.row_select[i] * model.matrix[(i, j)] for i in model.I) >= magic_sum[j] 
model.c1 = pyo.Constraint(model.J, rule=min_sum)

# objective function
# minimze the overage
def objective(model):
    delta = 0
    for j in model.J:
        delta += sum(model.row_select[i] * model.matrix[i, j] for i in model.I) - magic_sum[j] 

    return delta

model.OBJ = pyo.Objective(rule=objective)


model.pprint()  # verify everything

solver = pyo.SolverFactory('cbc')  # need to have cbc solver installed

result = solver.solve(model)

result.write()  # solver details

model.row_select.display() # output

输出：

# ----------------------------------------------------------
#   Solver Information
# ----------------------------------------------------------
Solver: 
- Status: ok
  User time: -1.0
  System time: 0.0
  Wallclock time: 0.0
  Termination condition: optimal
  Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
  Statistics: 
    Branch and bound: 
      Number of bounded subproblems: 0
      Number of created subproblems: 0
    Black box: 
      Number of iterations: 0
  Error rc: 0
  Time: 0.01792597770690918
# ----------------------------------------------------------
#   Solution Information
# ----------------------------------------------------------
Solution: 
- number of solutions: 0
  number of solutions displayed: 0
row_select : Size=5, Index=I
    Key : Lower : Value : Upper : Fixed : Stale : Domain
      0 :     0 :   1.0 :     1 : False : False : Boolean
      1 :     0 :   1.0 :     1 : False : False : Boolean
      2 :     0 :   0.0 :     1 : False : False : Boolean
      3 :     0 :   1.0 :     1 : False : False : Boolean
      4 :     0 :   1.0 :     1 : False : False : Boolean

100,000 行的压力更大的演绎：

# row selection Integer Program stress test
import pyomo.environ as pyo
import numpy as np

# make a large matrix 100,000 x 8
data1 = np.random.randint(0, 1000, size=(100_000, 8))
# inject "the right answer into 3 rows"
data1[42602]    = [8, 0, 0, 0, 0, 0, 0, 0 ]
data1[3]        = [0, 0, 0, 0, 4, 3, 2, 1 ]
data1[10986]    = [0, 7, 6, 5, 0, 0, 0, 0 ]

data_dict = {(i, j): data1[i][j] for i in range(len(data1)) for j in range(len(data1[0]))}

model = pyo.ConcreteModel()

# sets
model.I = pyo.Set(initialize=range(len(data1)))     # a simple row index
model.J = pyo.Set(initialize=range(len(data1[0])))  # a simple column index

# parameters
model.matrix = pyo.Param(model.I , model.J, initialize=data_dict)   # hold the sparse matrix of values
magic_sum = [8, 7, 6, 5, 4, 3, 2, 1 ]

# variables
model.row_select = pyo.Var(model.I, domain=pyo.Boolean) # row selection variable

# constraints
# ensure the columnar sum is at least the magic sum for all j
def min_sum(model, j):
    return sum(model.row_select[i] * model.matrix[(i, j)] for i in model.I) >= magic_sum[j] 
model.c1 = pyo.Constraint(model.J, rule=min_sum)

# objective function
# minimze the overage
def objective(model):
    delta = 0
    for j in model.J:
        delta += sum(model.row_select[i] * model.matrix[i, j] for i in model.I) - magic_sum[j] 

    return delta

model.OBJ = pyo.Objective(rule=objective)

solver = pyo.SolverFactory('cbc')

result = solver.solve(model)
result.write()


print('\n\n======== row selections =======')
for i in model.I:
    if model.row_select[i].value > 0:
        print (f'row {i} selected')

输出：

# ----------------------------------------------------------
#   Solver Information
# ----------------------------------------------------------
Solver: 
- Status: ok
  User time: -1.0
  System time: 2.18
  Wallclock time: 2.61
  Termination condition: optimal
  Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
  Statistics: 
    Branch and bound: 
      Number of bounded subproblems: 0
      Number of created subproblems: 0
    Black box: 
      Number of iterations: 0
  Error rc: 0
  Time: 2.800779104232788
# ----------------------------------------------------------
#   Solution Information
# ----------------------------------------------------------
Solution: 
- number of solutions: 0
  number of solutions displayed: 0


======== row selections =======
row 3 selected
row 10986 selected
row 42602 selected
于 2020-06-28T23:38:15.767 回答
0

这个选择而不是选择一个元素（递归地）。一旦树无法求解（没有剩余元素或任何目标值为负），它将返回 false。如果目标的总和为 0，则会找到解决方案并以拾取元素的形式返回。

随意在评论中添加时间和内存复杂性。最坏的情况应该是 2^(n+1)

请让我知道它在您的 8/50 数据上的表现。

const elements = [
  [1, 0, 0, 0],
  [1, 1, 0, 0],
  [1, 0, 1, 0],
  [1, 1, 1, 0],
  [1, 1, 1, 1]
];

const target = [4, 3, 2, 1];

let iterations = 0;

console.log(iter(elements, target, [], 0));
console.log(`Iterations: ${iterations}`);

function iter(elements, target, picked, index) {
  iterations++;
  const sum = target.reduce(function(element, sum) {
    return sum + element;
  });

  if (sum === 0) return picked;
  if (elements.length === 0) return false;

  const result = iter(
    removeElement(elements, 0),
    target,
    picked,
    index + 1
  );

  if (result !== false) return result;

  const newTarget = matrixSubtract(target, elements[0]);
  const hasNegatives = newTarget.some(function(element) {
    return element < 0;
  });

  if (hasNegatives) return false;

  return iter(
    removeElement(elements, 0),
    newTarget,
    picked.concat(index),
    index + 1
  );
}

function removeElement(target, i) {
  return target.slice(0, i).concat(target.slice(i + 1));
}

function matrixSubtract(minuend, subtrahend) {
  let i = 0;
  return minuend.map(function(element) {
    return minuend[i] - subtrahend[i++]
  });
}

于 2020-06-28T17:41:54.727 回答