用於算術運算的BFS

Question

用最少的操作將數字m轉換爲n。允許的操作是減1和乘以2.

例如：4和6.答案是2. 第一次操作：-1 - > 4-1 = 3 第二次操作：* - > 3 * 2 = 6。

我對特定輸入（src = 26，dst = 5）使用BFS方法需要很長時間。難道我做錯了什麼？

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。

感謝保羅： 下面是我在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改掉進行，其中n是所需的數量腳步）。請嘗試查找生成所需號碼的邏輯規則。

讓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不是這些值中的一個，那麼您首先從A中減去1，直到達到其中一個目標值。例如，如果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的溶液，DST = 5是減去1，直到到達如圖5所示，採用21 「廣度級別」= 21點的操作。在該級別，您的隊列和您的seen_list將包含〜2^20個值;並且對於隊列中的每個值，您都會進行線性搜索以查看它是否出現在列表中，因此該級別將包含2^20 * 2^20個比較= 2^40〜1千億個比較。這需要時間，而這只是最後一級。

你應該考慮一個更好的算法。對於初學者來說，如果你的當前值高於目標值，那麼沒有必要將其加倍，因爲它肯定只會增加額外的步驟。 僅僅考慮這個因素就可以將此案件的步驟數從數百萬減少到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; 
} 

說明::

試想一個臺階，並從（N）開始你就必須達到其頂部（即：數m），所以你決定做的所有列表最好的步驟，然後你參考你擁有的號碼，看看它是否存在於你爲最佳解決方案而制定的列表中，如果它在那裏，那麼你只需按照步驟進行操作，即使不是你，你必須將自己調整到最佳步驟（比如說減1），然後你就可以達到最佳的軌道和速度。 欲瞭解更多：請參考mr.paul解決方案中的解釋，以更好地解釋這一點。