BFS для арифметических операций

Question

Преобразование числа m в n с минимальными операциями. Разрешенные операции были вычитанием на 1 и умножением на 2.

Для примера: 4 и 6. Ответ равен 2. 1-я операция: -1 -> 4-1 = 3. Вторая операция: * -> 3 * 2 = 6.

Я использую подход BFS для конкретного ввода (src = 26, dst = 5), он занимает много времени. Я делаю что-то неправильно?

from queue_class import queue 


class node: 

    def __init__(self, value, level, parent): 
     self.level = level 
     self.value = value 
     self.parent = parent 

    def get_minimum_distance(src, target, q): 
     if src == target: 
      return 0 
     seen_list = [] 
     data = node(src, 0, -1) 
     q.enqueue(data) 
     while not q.isempty(): 
      data = q.dequeue() 
      if data == "sentinel": 
       break 
      if data.value == target: 
       # let's print what has got me here 
       while data.parent != -1: 
        print(data.value) 
        data = data.parent 
       return "finally reached" 
      if data.value in seen_list: 
       continue 
      seen_list.append(data.value) 
      # two operations are allowed i.e. -1 and multiplication by 2 
      # check if two numbers have opposite sign and if they have 
      # then check if the current number being subtracted from is a negative 
      # number. If it is, then there is no point subtracting 1 from that 
      if ((data.value^target) < 0 and data.value > 0) or (data.value^target >= 0): 
       q.enqueue(node(data.value - 1, data.level + 1, data)) 
       q.enqueue(node(data.value * 2, data.level + 1, data)) 
     return -1 

q = queue(1 << 20) 
print(get_minimum_distance(26, 5, q)) 

Выполнение очереди выполняется here.

Благодаря Paul: Ниже приведен код, который я привел с приведенным ниже кодом в python, и он отлично работает.

def get_minimum_operations(src, dst): 
    step = 0 
    operations = [] 
    if src == dst: 
     return 0 
    if dst < src: 
     return src-dst 
    while dst > src: 
     if dst & 0x01: 
      step += 1 
      operations.append("-1") 
     dst = (dst+1) >> 1 
     operations.append("*2") 
     step += 1 
    for i in range(0, src-dst): 
     operations.append("-1") 
    return (((src - dst) + step), operations) 

src = 38 
dst = 100 
output = "" 
(steps, operations) = get_minimum_operations(src, dst) 
print(steps) 
try: 
    while operations: 
     i = operations.pop() 
     if i == "*2": 
      if output == "": 
       output += "(" + str(src) + "*2" + ")" 
      else: 
       output = "(" + output + "*2" + ")" 
     if i == "-1": 
      if output == "": 
       output += "(" + str(src) + "-1" + ")" 
      else: 
       output = "(" + output + "-1" + ")" 
except IndexError: 
    pass 
print(output) 

Answer 1

BFS не совсем вариант здесь, из-за экспоненциального роста (2^(n - 1) to 2^n Trys выполняются, где п число требуется шаги). Вместо этого попробуйте найти логические правила для генерации необходимого числа.

Позвольте a быть номером ввода и b номер, который должен быть изготовлен.

Есть три случая:

• a == b, этот случай тривиально и просто перечислены для полноты
• a > b, решение a - b раз вычитая по -1
• a < b: Это более сложная часть

Наименьшее количество операций требует минимального значения n количество умножений и подстроек. Значения можно легко минимизировать из-за следующего факта: (a - 1) * 2 = a * 2 - 2. Таким образом, мы можем легко уменьшить число подстрок любым числом, которое является степенью 2, просто вычитая перед умножением.
Поскольку мы можем только вычитать и умножить, минимальное количество умножений - min n => a * 2^n >= b.
Используя этот факт, мы можем определить сумму, которую нужно вычесть: s = b - 2^n * a.

Реализация будет выглядеть в псевдокоде (не может предоставить код Python):

//using the same variable-names as above in the description 
minOp(int a , int b) 
    //find minimum number of multiplications 
    int n 
    for(n = 0 ; a << n < b ; n++) 
     noop 

    //find amount to substract 
    int s = (a << n) - b 

    for(int i = 0 ; i < n ; i++) 
     print("(") 

    print(a) 

    //calculate operations 
    while(n > 0) 
     //calculate number of times we need to substract here (minimization of substractions) 
     while(s >= 1 << n) 
      print(" - 1") 
      s -= 1 << n 

     print(")") 

     //divide by two 
     print(" * 2") 
     n -= 1 

    while(s >= 1 << n) 
     print(" - 1") 
     s -= 1 << n 

    print(" = ") 
    print(b) 

Это как хорошо реализация охватывает случаи a == b - с n = 0 и s = 0 - и a > b - с n = 0 и s = a - b.

тест-прогон в Java-реализации выше будет производить этот вывод:

(((4) * 2 - 1) * 2 - 1) * 2 = 26

упрощение выше расчета показывает идею этого алгоритма:

((4 * 2 - 1) * 2 - 1) * 2 = 26 
(4 * 2 * 2 - 2 - 1) * 2 = 26 
4 * 2 * 2 * 2 - 3 * 2 = 26 
32 - 6 = 26 

Благодаря @ user3386109 для этого объяснения:
Предположим, т а стартовое значение - A, а значение цели - B. Первым шагом является создание списка целевых значений, начинающихся с B, и продолжение деления на 2 (при необходимости округление). Например, если B равно 26, тогда список целевых значений будет 26, 13, 7, 4, 2, 1. Если начальное значение A является любым из этих целевых значений, то вы можете легко подняться до цели B (умножением на 2 и вычитанием 1, если необходимо). Если A не является одним из этих значений, вы начинаете с вычитания 1 из A, пока не достигнете одного из этих целевых значений. Например, если A равно 6, для достижения 4 требуется два вычитания, а затем вы поднимаетесь с 4 на 26. Если A равно 12, для достижения 7 требуется пять вычитаний и т. Д. Очевидно, что если A больше B, то все, что вы делаете, вычитается до тех пор, пока вы не достигнете B

Answer 2

Ваш алгоритм является экспоненциальным, на каждом дополнительном уровне «широта» добавить 2 новые значения для каждого значения в предыдущем уровне. Например:

26               (breadth = 0) 
25, 52              (breadth = 1) 
24, 50, 51, 104            (breadth = 2) 
23, 48, 49, 100, 50 (skipped because seen), 102, 103, 208  (breadth = 3) 
22, 46, 47, 96, 48 (skip), 98, 99, 200      (breadth = 4) 
21, 44, 45, 92, 46, 94, 95, 192, 97, 196, 199, 400   (breadth = 5) 

Раствор для случая SRC = 26, ДСТ = 5 вычесть 1, пока не достигнет 5, который принимает 21 "уровни" широта = 21 операций. На этом уровне ваша очередь и ваш seen_list будут содержать значения ~ 2^20; и для каждого значения в очереди вы выполняете линейный поиск, чтобы увидеть, присутствует ли он в списке, так что уровень будет состоять из сравнений 2^20 * 2^20 = 2^40 ~ 1 000 миллиардов. Это требует времени, и это только последний уровень.

Вы должны думать о лучшем алгоритме. Для начала, если ваше текущее значение выше целевого, нет смысла удваивать его, так как он обязательно добавит дополнительные шаги. Только это соображение уменьшит количество шагов для этого случая от миллионов до 21 (вы, буду просто вычесть 1, пока не достигнет целевого значения, и это будет происходить в общем, когда src > dest)

Answer 3

Этот код, надеюсь, реализует вышеупомянутый очень эффективный алгоритм.

private static int solve(int n, int m) { 

int steps = 0; 
int cur = n; 
ArrayList<Integer> arr = new ArrayList<>(); 

arr.add(m); 
for (int i = 0; !arr.contains(1); ++i) 
    arr.add((int) Math.round((double) arr.get(i)/2)); 

while (cur != m) { 
    if (arr.contains(cur)) 
     cur *= 2; 
    else 
     cur--; 

    steps++; 
    } 

return steps; 
} 

Объяснение ::

Представьте себе лестницу и, начиная с (п) вы должны достичь своей вершины (т.е. число м), так что вы решили сделать список всех что вы делаете, и вы видите, что он существует в том списке, который вы сделали для оптимального решения, если он есть, вы просто следуете этим шагам, и вы получите лучшее решение, если не вы, вам нужно привести себя в соответствие с оптимальными шагами (например, вычитая 1), а затем вы окажетесь на оптимальном пути и vooooom до вашего места назначения. Подробнее: пожалуйста, обратитесь к объяснению в решении mr.paul, там объясняет это лучше.