Нахождение наименьшего множества решений, если оно существует (два множителя)

Question

Примечание: это вариант с двумя множителями для этой задачи

Для заданного набора 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 большое, если не бесконечное.Если решение существует, как найти наименьший набор B?

---

Примечания:

• Мы не обязательно ограничены элементами в A. B можетсостоят из любого набора значений, независимо от того, существуют ли они в A.
• Поскольку все элементы в A - все 0-1 с плавающей запятой, я предполагаю, что B также будет 0-1 с плавающей запятой.Так ли это?
• Это может быть проблемой удовлетворения ограничений, но я не уверен, как бы это было определено?
• Поскольку математика с плавающей запятой, как правило, проблематична, любой ответ должен обрамлятьалгоритм вокруг рациональных чисел.

Answer 1

Сортировка массива.Для каждой пары элементов Am, An ∈ A, m

Проверьте, равно ли отношение некоторому элементу в 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 (которые я оставляю читателю в качестве упражнения).

Обратите внимание, что нет необходимости вводить числа больше 1. B также можно представить как {0,1, 0,11, 0,12, 2}, но этот набор имеет ту же мощность.

Answer 2

Google OR-Tools предоставляют хороший CP решатель , который можно использовать для решения этой проблемы.Вы можете закодировать вашу проблему в виде простого набора логических переменных, говоря, какие переменные или комбинации переменных являются допустимыми.

Я начну с извлечения соответствующей части библиотеки и установки нескольких переменных:

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 также верно.есть полезный документ по кодированию логической логики в 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| в решателе, но я бы соблазнился сделать это за пределами