[HFC] Hidden Features of Stack/Backtracking in C－Edison.X. Blog

0. 前言

1. 中文我不確定是「回溯」還是「廻溯」，但英文是 backtrack 無誤。

2. 這篇文章不會提到關於任何 Judge 上 backtrack 技巧，因這些題目已有人提供更好的說明。

3. 這篇文章主要內容如下

(1) 常見被拿來探討 backtracking 之題目

(2) 求 inverse of matrix 之 backtrack

(3) functions of call stack

1. 常見用來探討之題目

在練習 Judge 或打史萊姆的階段，下面都是拿來練習 backtrack 技巧之題目

1.1 enumerate n-tuples

1.2 enumerate all permutation

1.3 enumerate all subsets

1.4 eight queen problem

1.5 kinght's tour problem

1.6 knapsack problem ( 0 / 1 )

有興趣之版友可試試，另這些題目大多還有各自的進階版本。

2. 倒帶人生 ?

筆者拿一個可能不是很引人興趣的問題作例 - inverse matrix，因筆者認為它在 backtracking 之動作真的就像是倒帶人生。

在學數值分析時，寫到一份 function 算 matrix 反矩陣，假設宣告長這樣

int mat_inverse(double** mat, size_t n);

由於不能確定 inverse matrix 必定存在，我們希望的情況是

ˇ 若 mat 存在 inverse matrix 時，直接改變 mat 內容即可，return 1。

ˇ 若 mat 不存在 inverse matrix，不要改變 mat 內容，return 0。

假設 mat_inverse 是用高斯消去法求得。一般在 mat_inverse 直覺的作法是，

ˇ 先配置一個 double unit[n][n] ，並設成單位矩陣。

ˇ 再配置一個 double mat_tmp[n][n]，將 mat 複製到 mat_tmp。

ˇ 對 mat_tmp / unit 進行反矩陣運算，若發現存在時，將 unit 複製到 mat；否則不動作。

ˇ 釋放記憶體。

一般教科書步驟大概如此，在教初學者的時候我也這麼教，去掉一些眉眉角角，就真的是這樣。

這麼做無疑，原本只要一個 mat 求 inverse，現在需要 mat、mat_tmp、unit 才能求 inverse，

換句話說，若為大維度之 matrix， n = 10000 時，

unit、mat、mat_tmp 所佔記憶體為 8 * 3 * 10000 * 10000 ≅ 2.4 GB，

這大小似乎不是大多 PC 都能配置出來的。

一種改善方式便是使用 Stack ，把 mat 在做列運算時的過程全都紀錄下來，

如假設 mat = { {1,2,3} , {4,5,6}, {7,8,9} }，它本身並不存在 inverse matrix，

消去法 ( 不考慮穩定度情況下 ) 最後會得到 mat = { {1,0,-1}, {0, 1, 2}, {0, 0, 0} }

所經過的列運算依序為 R12(-4), R13(-7), R2(-1/3), R21(-2), R23(6)，

把這些運算壓入 stack 裡，要回溯到原始狀態時，就再從最後的 { {1,0,-1}, {0, 1, 2}, {0, 0, 0} }

回溯回去，變成 R23(-6), R21(+2), R2(-3), R13(+7), R12(+4)

< 這例子裡面沒有列交換，若為 Rij，其反運算也是 Rij >

所以這種作法就可以將原本要用到的 unit、mat、mat_tmp，縮小成為只用 unit、mat 即可了嗎？

oh ，不只！實際上可以只用到原本的 mat，和額外記錄流程之 array 即可。

反矩陣不存在時，這個 array 就當 stack 看待；反矩陣存在時，這個 array 就當 queue 看待。

當然在這問題裡其實是有個假設前提的：我們可能會處理到維度很大的 matrix，

且這個 matrix 它不是稀疏矩陣。用三份 matrix 做和用一份 matrix 做，

若沒有記憶體上限考量時，我倒認為用原本之方式也不算很差，

雖在花了 2*n*n 之時間在複制 matrix，但回溯法之成本，未必比它還低。

<必須視情況才能比較>

其他實作的探討議題，不適合繼續於本文敘述，點到為止。

3. 這根本是 stack 吧？

換個角度想，是的，它是 stack。

即使是 recursive call ，它也是一種 Stack，實作方式確實可以用 Stack 來做無誤，

有名的老鼠走迷宮問題、漢諾塔問題等，常見是以 recursive function 實作，

但確實有人也以 stack 方式實作，實作起來程式碼可能不是那麼直覺便是。

另也有一門學術在研究，針對各種常見到的 recursive 問題，

將 recursive function 完全去掉，期望能增快其效能，大多之作法也是 stack 無誤。

< 當然還是有人用 goto 去完成就是了，此部份不再贅述 >

至於其他語言討論的問題，

像曾看過有人問，為什麼是 array 實作 stack，沒看過別人用 stack 實作 array 這問題，

就不適合在本文裡引戰。

4. And Then ? - functions of call stack

(*) 筆者並不打算深入 call stack 之架構，因牽扯到作業系統處理之機制稍嫌多一點點，且真正分析時大多會拆解編出來的 asm code，必須花一點時間閱讀其他文章或書籍了解，故於此略過，有興趣可看這篇入門文章。

(*) 我曾於 Debug 系列文裡，提到了使用 VC IDE 切換堆疊之技巧，VC 使用者可參考。

(*) 這議題目前沒有可攜性之作法。

現假設一段程式碼如下

#include <stdio.h>
void func1(), func2(), func3();
// -------------------------------
int main()
{
    func1();
    return 0;
}
// -------------------------------
void func1()
{
    puts("func1");
    func2();
}
void func2()
{
    puts("func2");
    func3();
}
void func3()
{
    puts("func3");
}