找到最小的解决方案集，如果存在（两个乘数）

Question

注意：这是 this problem

的双乘数变体

给定一个集合 A，由介于 0.0 和 1.0 之间的浮点数组成，找到一个最小的集合 B 使得对于 A 中的每个 a，有a == B[x] 处的值，或 a == B[x] * B[y].

处的一对唯一值

例如给定

$ A = [0.125, 0.25, 0.5, 0.75, 0.9]

B 的一个可能的（但可能不是最小的）解决方案是

$ B = solve(A)
$ print(B)
[0.25, 0.5, 0.75, 0.9]

这就满足了最初的问题，因为A[0] == B[0] * B[1]、A[1] == B[1]等，这让我们可以重新创建原始集合A。 B的长度比A的长度小，但我猜也有更小的答案。

我假设 B 的解 space 很大，如果不是无穷大的话。如果存在解决方案，如何找到最小集合 B？

备注：

我们不必局限于 A 中的项目。B 可以包含任何一组值，无论它们是否存在于 A 中。
由于 A 中的项目都是 0-1 浮点数，我假设 B 也将是 0-1 浮点数。是这样吗？
这可能是一个约束满足问题，但我不确定它是如何定义的？
由于浮点数学通常存在问题，因此任何答案都应围绕有理数构建算法。

Answer 1

对数组进行排序。对于每对元素 Am, An ∈ A, m < n - 计算它们的比率。

检查比率是否等于 A 中的某个元素，它不等于 Am 也不等于 An。

示例：

A = { 0.125, 0.25, 0.5, 0.75, 0.9 }

(0.125, 0.25): 0.5    <--- bingo
(0.125, 0.5 ): 0.25   <--- bingo
(0.125, 0.75): 0.1(6)
(0.125, 0.9 ): 0.13(8)
(0.25 , 0.5 ): 0.5
(0.25 , 0.75): 0.(3)
(0.25 , 0.9 ): 0.2(7)
(0.5  , 0.75): 0.(6)
(0.5  , 0.9 ): 0.(5) 
(0.75 , 0.9 ): 0.8(3)

分子(0.125)多余(=0.25*0.5)或(=0.5*0.25)

我们可以通过引入新元素来做得更好：

另一个例子：

A = { 0.1, 0.11, 0.12, 0.2, 0.22, 0.24 }

(0.1 , 0.11): 0.(90)        ***
(0.1 , 0.12): 0.8(3)        +++
(0.1 , 0.2 ): 0.5     <--------
(0.1 , 0.22): 0.(45)
(0.1 , 0.24): 0.41(6)
(0.11, 0,12): 0.91(6)       ~~~
(0.11, 0.2 ): 0.55
(0.11, 0.22): 0.5     <--------
(0.11, 0.24): 0.458(3)
(0.12, 0.2 ): 0.6
(0.12, 0.22): 0.(54)
(0.12, 0.24): 0.5     <--------
(0.2 , 0.22): 0.(90)        ***
(0.2 , 0.24): 0.8(3)        +++
(0.22. 0.24): 0.91(6)       ~~~

任何 2 对或更多对 (a1,a2), (a3,a4), (... , ...) 具有公比 f 可以替换为 { a1, a3, ..., f }.

因此，将 0.5 添加到我们的集合中会使 { 0.1, 0.11, 0.12 } 变得多余。

B = (0.2, 0.22, 0.24, 0.5}

我们现在（在一般情况下）剩下一个优化问题，即选择要删除哪些元素以及添加哪些因素以最小化 B 的基数（我将其作为练习留给reader).

注意这里不需要引入大于1的数。B也可以表示为{0.1,0.11,0.12,2}但是这个集合有相同的基数。

Answer 2

Google's OR-Tools provide a nice CP solver 可以用来解决这个问题。您可以将您的问题编码为一组简单的布尔变量，说明哪些变量或变量组合是有效的。

我首先引入库的相关部分并设置一些变量：

from ortools.sat.python import cp_model

A = [0.125, 0.25, 0.5, 0.75, 0.9]
# A = [0.1, 0.11, 0.12, 0.2, 0.22, 0.24]

model = cp_model.CpModel()

然后我们可以定义一些辅助函数来从我们的数字创建变量：

vars = {}
def get_var(val):
    assert val >= 0 and val <= 1
    if val in vars:
        return vars[val]

    var = model.NewBoolVar(str(val))
    vars[val] = var
    return var

pairs = {}
def get_pair(pair):
    if pair in pairs:
        return pairs[pair]

    a, b = pair
    av = get_var(a)
    bv = get_var(b)

    var = model.NewBoolVar(f'[{a} * {b}]')
    model.AddBoolOr([av.Not(), bv.Not(), var])
    model.AddImplication(var, av)
    model.AddImplication(var, bv)
    pairs[pair] = var
    return var

即get_var(0.5) 将创建一个布尔变量（使用 Name='0.5'），而 get_pair(0.5, 0.8) 将创建一个变量并设置约束，以便它仅在 0.5 和 0.8 也为真时为真。有一篇关于编码的有用文档 boolean logic in ortools

然后我们可以通过 A 找出哪些组合是有效的并将它们作为约束添加到求解器中：

for i, a in enumerate(A):
    opts = {(a,)}
    for a2 in A[i+1:]:
        assert a < a2
        m = a / a2
        if m == a2:
            opts.add((m,))
        elif m < a2:
            opts.add((m, a2))
        else:
            opts.add((a2, m))

    alts = []
    for opt in opts:
        if len(opt) == 1:
            alts.append(get_var(*opt))
        else:
            alts.append(get_pair(opt))

    model.AddBoolOr(alts)

接下来我们需要一种方式来表明我们更喜欢变量为假而不是真。这个的最小版本是：

model.Minimize(sum(vars.values()))

但是如果我们稍微复杂一点并优先考虑 A:

中的值，我们会得到更好的结果

costsum = 0
for val, var in vars.items():
    cost = 1000 if val in A else 1001
    costsum += var * cost
model.Minimize(costsum)

最后，我们可以运行我们的求解器并打印出一个解决方案：

solver = cp_model.CpSolver()
status = solver.Solve(model)
print(solver.StatusName(status))

if status in {cp_model.FEASIBLE, cp_model.OPTIMAL}:
    B = [val for val, var in vars.items() if solver.Value(var)]
    print(sorted(B))

这给了我预期的一组： [0.125, 0.5, 0.75, 0.9] 和 [0.2, 0.22, 0.24, 0.5] 对于顶部的两个示例

你也可以编码这样一个事实，即你只在求解器中 |B| < |A| 才考虑有效的解决方案，但我很想在求解器之外这样做

找到最小的解决方案集，如果存在（两个乘数）

Finding the smallest solution set, if one exists (two multipliers)

python

algorithm

set-theory

constraints

set