Как реализовать алгоритм для данной задачи

Question

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

Использование алгоритма грубой силы неэффективно, поэтому я подумал, что могу использовать жадный алгоритм. Может ли кто-нибудь помочь мне разобраться в эвристике для проблемы, а также в лучших решениях. Пожалуйста, держите это к основам, поскольку я новичок в topi c.

Answer 1

Использование грубой силы неэффективно

Почему вы так думаете? Сложность грубой силы равна n!, где n - это количество блоков, в данном случае 9!

Для типичных персональных компьютеров в наши дни не требуется даже секунды для его вычисления.

Было бы неэффективно, если бы количество полей, которые нужно было заполнить, было бы очень большим, то есть с n! > 10^8, поскольку операции 10^8 basi c могут быть выполнены обычными компьютерами в секунду.

Вы можете сделать что-то подобное в C ++:

vector<int> perm = {1, 2, 3, 4,.., 9};
do {
  // use them to fill sequentially upto element perm[7]
  // and find value

  int compare = perm[7]*10 + perm[8];
  if(compare == value){
    // found solution
  }
} while(next_permutation(perm.begin(), perm.end());

Пожалуйста, перейдите по этой ссылке здесь для получения более подробной информации о next_permutation: Ссылка

Answer 2

Грубая сила с некоторыми ограничениями для этой задачи будет очень быстрой (70 миллисекунд). В следующем коде я использовал следующие границы:

• Вместо грубой силы 9! перестановки, мы можем сначала попробовать все перестановки для первых 3 цифр (в первых двух числах)
• Следующие 2 цифры (3-е число), таким образом, могут быть рассчитаны, так как они являются первым произведением. Мы можем исключить случаи, когда цифры в первом результате дублируют несколько цифр в первых 3 цифрах, или результат имеет более 2 цифр
• Затем мы пробуем все перестановки 2 среди оставшихся 4 цифр, чтобы сформировать 4-е число, получите второй результат (некоторые из 3-го и 4-го числа) и проверьте, не используются ли какие-либо цифры более одного раза.

Так что в худшем случае нам нужно только попробовать 9*8*7*4*3 = 6048 (9*8*7 из 3-перестановки на шаге 1 и 4*3 из 2-перестановки на шаге 3), не говоря уже о том, что многие случаи исключаются на 2-м шаге.

import itertools


def solve():
    digits = list(range(1,10))

    for a, b, c in itertools.permutations(digits, 3):
        res = (a*10+b)*c # third number

        if res > 100:  # third number uses more than 2 digits
            continue
        d, e = res//10, res%10 
        used = set([a,b,c,d,e])
        if len(used) < 5:  # duplicate digits
            continue
        left = set(digits).difference(used)
        for f, g in itertools.permutations(left, 2):
            res = d*10 + e + f*10 + g # final number
            h, k = res//10, res%10  
            if set([f,g,h,k]) == left:
                print("{}{}*{}={}{}".format(a,b,c,d,e))
                print("{}{}+{}{}={}{}".format(d,e,f,g,h,k))

import time
start = time.time()
solve()
print("Solve in {:.3}s".format(time.time()-start))

Решение

17*4=68
68+25=93
Solve in 0.073s