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");
}

有時在 debug 中,我們會較感興趣,如何印出在過程中呼叫過的函式。

第一種較無腦的方式是,在每個 function 進入 / 退出時都輸出相關資訊,

( 這時該善用 __FUNCTION__ , __FUNC__ , __func__ ),

但會改到原本身 sub_function,較不佳。

在 gcc 裡已有提供一套 header 可用, exeinfo.h ,

網路上能找到其應用的不少,最簡易實作的大概 屬這篇

關鍵在於 backtrace 與 backtrace_symbols 之調用,於此不再贅述。

而 Microsoft 目前也有 API 專門處理這問題:StackWalker64

它放在 Dbghelp.h 裡,需連結 Dbghelp.lib。

看裡面第一個 Machine Type ,是和硬體相關 ,

目前只支援三種硬體 ( 像筆者的硬體永遠都是調用失敗 ),

這份函式要研究應會花不少時間,但幸運的是,

code project 裡有份 walking the callstack

將相關 API 封裝成了 class < 裡面用到一些 asm inline >,

但正如我所說,使用 StackWalker64 這份 API 相關於硬體,

故那份 class 下載下來還是相關於硬體 < 像筆者執行就看到一堆 GetLastError >。

好消息是,若為 .Net coder,M$ 已封裝了一份 class - StackTrace class

若不是 gcc / vc 使用者,要做 stack trace 呢?

oh , 恕筆者沒再用過其他 compiler, 不知有何相關之 trace 函式...

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()