回溯法backtracking)係演算法嘅一種,指用遞歸噉一步一步建立一個答案,而喺發現個答案唔掂(唔符合由用家指定嘅條件)嗰陣,就放棄嗰個答案(「回溯」-返轉頭做過),郁手建立下一個答案,一路重複做,做到搵到個掂嘅答案為止。大致上可以噉樣想像[1]

  1. 檢查吓搵到答案未,如果搵到(true)嘅話,終止程式;
  2. 建立答案嘅一步(例:如果解嘅係數獨,是但填一個可能數字),
  3. 如果目前狀態冇可能達到目的,噉就重新做過;
  4. 重複。

例如下圖係用回溯法解數獨嘅動畫:

編輯

  1. Backtracking Algorithms. GeeksForGeeks.