來源：http://www.y768.com/content/view/5755/109/
Steve Best（sbest@us.ibm.com）
JFS 核心小組成員，IBM
2002 年 8 月
您可以用各種方法來監控運行著的用戶空間程序：可以為其運行調試器并單步調試該程序，添加打印語句，或者添加工具來分析程序。本文描述了幾種可以用來調試在 Linux 上運行的程序的方法。我們將回顧四種調試問題的情況，這些問題包括段錯誤，內存溢出和泄漏，還有掛起。
本
文討論了四種調試 Linux 程序的情況。在第 1 種情況中，我們使用了兩個有內存分配問題的樣本程序，使用 MEMWATCH 和 Yet
Another Malloc Debugger（YAMD）工具來調試它們。在第 2 種情況中，我們使用了 Linux 中的 strace
實用程序，它能夠跟蹤系統調用和信號，從而找出程序發生錯誤的地方。在第 3 種情況中，我們使用 Linux 內核的 Oops
功能來解決程序的段錯誤，并向您展示如何設置內核源代碼級調試器（kernel source level debugger，kgdb），以使用
GNU 調試器（GNU debugger，gdb）來解決相同的問題；kgdb 程序是使用串行連接的 Linux 內核遠程 gdb。在第 4
種情況中，我們使用 Linux 上提供的魔術鍵控順序（magic key sequence）來顯示引發掛起問題的組件的信息。
常見調試方法
當您的程序中包含錯誤時，很可能在代碼中某處有一個條件，您認為它為真（true），但實際上是假（false）。找出錯誤的過程也就是在找出錯誤后推翻以前一直確信為真的某個條件過程。
以下幾個示例是您可能確信成立的條件的一些類型：
在源代碼中的某處，某變量有特定的值。
在給定的地方，某個結構已被正確設置。
對于給定的 if-then-else 語句，if 部分就是被執行的路徑。
當子例程被調用時，該例程正確地接收到了它的參數。
找
出錯誤也就是要確定上述所有情況是否存在。如果您確信在子例程被調用時某變量應該有特定的值，那么就檢查一下情況是否如此。如果您相信 if
結構會被執行，那么也檢查一下情況是否如此。通常，您的假設都會是正確的，但最終您會找到與假設不符的情況。結果，您就會找出發生錯誤的地方。
調試是您無法逃避的任務。進行調試有很多種方法，比如將消息打印到屏幕上、使用調試器，或只是考慮程序執行的情況并仔細地揣摩問題所在。
在
修正問題之前，您必須找出它的源頭。舉例來說，對于段錯誤，您需要了解段錯誤發生在代碼的哪一行。一旦您發現了代碼中出錯的行，請確定該方法中變量的值、
方法被調用的方式以及關于錯誤如何發生的詳細情況。使用調試器將使找出所有這些信息變得很簡單。如果沒有調試器可用，您還可以使用其它的工具。（請注意，
產品環境中可能并不提供調試器，而且 Linux 內核沒有內建的調試器。）
實用的內存和內核工具
您可以使用 Linux 上的調試工具，通過各種方式跟蹤用戶空間和內核問題。請使用下面的工具和技術來構建和調試您的源代碼：
用戶空間工具：
內存工具：MEMWATCH 和 YAMD
strace
GNU 調試器（gdb）
魔術鍵控順序
內核工具：
內核源代碼級調試器（kgdb）
內建內核調試器（kdb）
Oops
本文將討論一類通過人工檢查代碼不容易找到的問題，而且此類問題只在很少見的情況下存在。內存錯誤通常在多種情況同時存在時出現，而且您有時只能在部署程序之后才能發現內存錯誤。
第 1 種情況：內存調試工具
C 語言作為 Linux 系統上標準的編程語言給予了我們對動態內存分配很大的控制權。然而，這種自由可能會導致嚴重的內存管理問題，而這些問題可能導致程序崩潰或隨時間的推移導致性能降級。
內存泄漏（即 malloc() 內存在對應的 free() 調用執行后永不被釋放）和緩沖區溢出（例如對以前分配到某數組的內存進行寫操作）是一些常見的問題，它們可能很難檢測到。這一部分將討論幾個調試工具，它們極大地簡化了檢測和找出內存問題的過程。
MEMWATCH
MEMWATCH
由 Johan Lindh 編寫，是一個開放源代碼 C
語言內存錯誤檢測工具，您可以自己下載它（請參閱本文后面部分的參考資料）。只要在代碼中添加一個頭文件并在 gcc 語句中定義了 MEMWATCH
之后，您就可以跟蹤程序中的內存泄漏和錯誤了。MEMWATCH 支持 ANSI
C，它提供結果日志紀錄，能檢測雙重釋放（double-free）、錯誤釋放（erroneous free）、沒有釋放的內存（unfreed
memory）、溢出和下溢等等。
清單 1. 內存樣本（test1.c）
#include "STDLIB.H"
#include "STDIO.H"
#include "memwatch.h"
int main(void)
{
char *ptr1;
char *ptr2;
ptr1 = malloc(512);
ptr2 = malloc(512);
ptr2 = ptr1;
free(ptr2);
free(ptr1);
}
清單 1 中的代碼將分配兩個 512 字節的內存塊，然后指向第一個內存塊的指針被設定為指向第二個內存塊。結果，第二個內存塊的地址丟失，從而產生了內存泄漏。
現在我們編譯清單 1 的 memwatch.c。下面是一個 makefile 示例：
test1
gcc -DMEMWATCH -DMW_STDIO test1.c memwatch
c -o test1
當您運行 test1 程序后，它會生成一個關于泄漏的內存的報告。清單 2 展示了示例 memwatch.log 輸出文件。
清單 2. test1 memwatch.log 文件
MEMWATCH 2.67 Copyright (C) 1992-1999 Johan Lindh
...
double-free: <4> test1.c(15), 0x80517b4 was freed from test1.c(14)
...
unfreed: <2> test1.c(11), 512 bytes at 0x80519e4
{FE FE FE FE FE FE FE FE FE FE FE FE ..............}
Memory usage statistics (global):
N)umber of allocations made: 2
L)argest memory usage : 1024
T)otal of all alloc() calls: 1024
U)nfreed bytes totals : 512
MEMWATCH 為您顯示真正導致問題的行。如果您釋放一個已經釋放過的指針，它會告訴您。對于沒有釋放的內存也一樣。日志結尾部分顯示統計信息，包括泄漏了多少內存，使用了多少內存，以及總共分配了多少內存。
YAMD
YAMD
軟件包由 Nate Eldredge 編寫，可以查找 C 和 C++ 中動態的、與內存分配有關的問題。在撰寫本文時，YAMD 的最新版本為
0.32。請下載 yamd-0.32.tar.gz（請參閱參考資料）。執行 make 命令來構建程序；然后執行 make install
命令安裝程序并設置工具。
一旦您下載了 YAMD 之后，請在 test1.c 上使用它。請刪除 #include memwatch.h 并對 makefile 進行如下小小的修改：
使用 YAMD 的 test1
gcc -g test1.c -o test1
清單 3 展示了來自 test1 上的 YAMD 的輸出。
清單 3. 使用 YAMD 的 test1 輸出
YAMD version 0.32
Executable: /usr/src/test/yamd-0.32/test1
...
INFO: Normal allocation of this block
Address 0x40025e00, size 512
...
INFO: Normal allocation of this block
Address 0x40028e00, size 512
...
INFO: Normal deallocation of this block
Address 0x40025e00, size 512
...
ERROR: Multiple freeing At
free of pointer already freed
Address 0x40025e00, size 512
...
WARNING: Memory leak
Address 0x40028e00, size 512
WARNING: Total memory leaks:
1 unfreed allocations totaling 512 bytes
*** Finished at Tue ... 10:07:15 2002
Allocated a grand total of 1024 bytes 2 allocations
Average of 512 bytes per allocation
Max bytes allocated at one time: 1024
24 K alloced internally / 12 K mapped now / 8 K max
Virtual program size is 1416 K
End.
YAMD 顯示我們已經釋放了內存，而且存在內存泄漏。讓我們在清單 4 中另一個樣本程序上試試 YAMD。
清單 4. 內存代碼（test2.c）
#include "STDLIB.H"
#include "STDIO.H"
int main(void)
{
char *ptr1;
char *ptr2;
char *chptr;
int i = 1;
ptr1 = malloc(512);
ptr2 = malloc(512);
chptr = (char *)malloc(512);
for (i; i <= 512; i++) {
chptr = 'S';
}
ptr2 = ptr1;
free(ptr2);
free(ptr1);
free(chptr);
}
您可以使用下面的命令來啟動 YAMD：
./run-yamd /usr/src/test/test2/test2
清單 5 顯示了在樣本程序 test2 上使用 YAMD 得到的輸出。YAMD 告訴我們在 for 循環中有“越界（out-of-bounds）”的情況。
清單 5. 使用 YAMD 的 test2 輸出
Running /usr/src/test/test2/test2
Temp output to /tmp/yamd-out.1243
*********
./run-yamd: line 101: 1248 Segmentation fault (core dumped)
YAMD version 0.32
Starting run: /usr/src/test/test2/test2
Executable: /usr/src/test/test2/test2
Virtual program size is 1380 K
...
INFO: Normal allocation of this block
Address 0x40025e00, size 512
...
INFO: Normal allocation of this block
Address 0x40028e00, size 512
...
INFO: Normal allocation of this block
Address 0x4002be00, size 512
ERROR: Crash
...
Tried to write address 0x4002c000
Seems to be part of this block:
Address 0x4002be00, size 512
...
Address in question is at offset 512 (out of bounds)
Will dump core after checking heap.
Done.
MEMWATCH 和 YAMD 都是很有用的調試工具，它們的使用方法有所不同。對于 MEMWATCH，您需要添加包含文件 memwatch.h 并打開兩個編譯時間標記。對于鏈接（link）語句，YAMD 只需要 -g 選項。
Electric Fence
多
數 Linux 分發版包含一個 Electric Fence 包，不過您也可以選擇下載它。Electric Fence 是一個由 Bruce
Perens 編寫的 malloc() 調試庫。它就在您分配內存后分配受保護的內存。如果存在 fencepost
錯誤（超過數組末尾運行），程序就會產生保護錯誤，并立即結束。通過結合 Electric Fence 和
gdb，您可以精確地跟蹤到哪一行試圖訪問受保護內存。Electric Fence 的另一個功能就是能夠檢測內存泄漏。
第 2 種情況：使用 strace
strace
命令是一種強大的工具，它能夠顯示所有由用戶空間程序發出的系統調用。strace 顯示這些調用的參數并返回符號形式的值。strace
從內核接收信息，而且不需要以任何特殊的方式來構建內核。將跟蹤信息發送到應用程序及內核開發者都很有用。在清單 6
中，分區的一種格式有錯誤，清單顯示了 strace 的開頭部分，內容是關于調出創建文件系統操作（mkfs）的。strace
確定哪個調用導致問題出現。
清單 6. mkfs 上 strace 的開頭部分
execve("/sbin/mkfs.jfs", ["mkfs.jfs", "-f", "/dev/test1"], &
...
open("/dev/test1", O_RDWR|O_LARGEFILE) = 4
stat64("/dev/test1", {st_mode=&, st_rdev=makedev(63, 255), ...}) = 0
ioctl(4, 0x40041271, 0xbfffe128) = -1 EINVAL (Invalid argument)
write(2, "mkfs.jfs: warning - cannot setb" ..., 98mkfs.jfs: warning -
cannot set blocksize on block device /dev/test1: Invalid argument )
= 98
stat64("/dev/test1", {st_mode=&, st_rdev=makedev(63, 255), ...}) = 0
open("/dev/test1", O_RDONLY|O_LARGEFILE) = 5
ioctl(5, 0x80041272, 0xbfffe124) = -1 EINVAL (Invalid argument)
write(2, "mkfs.jfs: can\'t determine device"..., ..._exit(1)
= ?
清
單 6 顯示 ioctl 調用導致用來格式化分區的 mkfs 程序失敗。ioctl BLKGETSIZE64
失敗。（BLKGET-SIZE64 在調用 ioctl 的源代碼中定義。) BLKGETSIZE64 ioctl 將被添加到 Linux
中所有的設備，而在這里，邏輯卷管理器還不支持它。因此，如果 BLKGETSIZE64 ioctl 調用失敗，mkfs 代碼將改為調用較早的
ioctl 調用；這使得 mkfs 適用于邏輯卷管理器。
第 3 種情況：使用 gdb 和 Oops
您可以從命令行使用
gdb 程序（Free Software Foundation 的調試器）來找出錯誤，也可以從諸如 Data Display
Debugger（DDD）這樣的幾個圖形工具之一使用 gdb 程序來找出錯誤。您可以使用 gdb 來調試用戶空間程序或 Linux
內核。這一部分只討論從命令行運行 gdb 的情況。
使用 gdb program name 命令啟動 gdb。gdb 將載入可執行程序符號并顯示輸入提示符，讓您可以開始使用調試器。您可以通過三種方式用 gdb 查看進程：
使用 attach 命令開始查看一個已經運行的進程；attach 將停止進程。
使用 run 命令執行程序并從頭開始調試程序。
查看已有的核心文件來確定進程終止時的狀態。要查看核心文件，請用下面的命令啟動 gdb。
gdb programname corefilename
要用核心文件進行調試，您不僅需要程序的可執行文件和源文件，還需要核心文件本身。要用核心文件啟動 gdb，請使用 -c 選項：
gdb -c core programname
gdb 顯示哪行代碼導致程序發生核心轉儲。
在運行程序或連接到已經運行的程序之前，請列出您覺得有錯誤的源代碼，設置斷點，然后開始調試程序。您可以使用 help 命令查看全面的 gdb 在線幫助和詳細的教程。
kgdb
kgdb
程序（使用 gdb 的遠程主機 Linux 內核調試器）提供了一種使用 gdb 調試 Linux 內核的機制。kgdb
程序是內核的擴展，它讓您能夠在遠程主機上運行 gdb 時連接到運行用 kgdb
擴展的內核機器。您可以接著深入到內核中、設置斷點、檢查數據并進行其它操作（類似于您在應用程序上使用 gdb
的方式）。這個補丁的主要特點之一就是運行 gdb
的主機在引導過程中連接到目標機器（運行要被調試的內核）。這讓您能夠盡早開始調試。請注意，補丁為 Linux 內核添加了功能，所以 gdb
可以用來調試 Linux 內核。
使用 kgdb 需要兩臺機器：一臺是開發機器，另一臺是測試機器。一條串行線（空調制解調器電纜）將通過機器的串口連接它們。您希望調試的內核在測試機器上運行；gdb 在開發機器上運行。gdb 使用串行線與您要調試的內核通信。
請遵循下面的步驟來設置 kgdb 調試環境：
下載您的 Linux 內核版本適用的補丁。
將
組件構建到內核，因為這是使用 kgdb
最簡單的方法。（請注意，有兩種方法可以構建多數內核組件，比如作為模塊或直接構建到內核中。舉例來說，日志紀錄文件系統（Journaled
File System，JFS）可以作為模塊構建，或直接構建到內核中。通過使用 gdb 補丁，我們就可以將 JFS 直接構建到內核中。）
應用內核補丁并重新構建內核。
創建一個名為 .gdbinit 的文件，并將其保存在內核源文件子目錄中（換句話說就是 /usr/src/linux）。文件 .gdbinit 中有下面四行代碼：
set remotebaud 115200
symbol-file vmlinux
target remote /dev/ttyS0
set output-radix 16
將 append=gdb 這一行添加到 lilo，lilo 是用來在引導內核時選擇使用哪個內核的引導載入程序。
image=/boot/bzImage-2.4.17
label=gdb2417
read-only
root=/dev/sda8
append="gdb gdbttyS=1 gdb-baud=115200 nmi_watchdog=0"
清單 7 是一個腳本示例，它將您在開發機器上構建的內核和模塊引入測試機器。您需要修改下面幾項：
best@sfb：用戶標識和機器名。
/usr/src/linux-2.4.17：內核源代碼樹的目錄。
bzImage-2.4.17：測試機器上將引導的內核名。
rcp 和 rsync：必須允許它在構建內核的機器上運行。
清單 7. 引入測試機器的內核和模塊的腳本
set -x
rcp best@sfb: /usr/src/linux-2.4.17/arch/i386/boot/bzImage /boot/bzImage-2.4.17
rcp best@sfb:/usr/src/linux-2.4.17/System.map /boot/System.map-2.4.17
rm -rf /lib/modules/2.4.17
rsync -a best@sfb:/lib/modules/2.4.17 /lib/modules
chown -R root /lib/modules/2.4.17
lilo
現在我們可以通過改為使用內核源代碼樹開始的目錄來啟動開發機器上的 gdb 程序了。在本示例中，內核源代碼樹位于 /usr/src/linux-2.4.17。輸入 gdb 啟動程序。
如果一切正常，測試機器將在啟動過程中停止。輸入 gdb 命令 cont 以繼續啟動過程。一個常見的問題是，空調制解調器電纜可能會被連接到錯誤的串口。如果 gdb 不啟動，將端口改為第二個串口，這會使 gdb 啟動。
使用 kgdb 調試內核問題
清單 8 列出了 jfs_mount.c 文件的源代碼中被修改過的代碼，我們在代碼中創建了一個空指針異常，從而使代碼在第 109 行產生段錯誤。
清單 8. 修改過后的 jfs_mount.c 代碼
int jfs_mount(struct super_block *sb)
{
...
int ptr; /* line 1 added */
jFYI(1, ("\nMount JFS\n"));
/ *
* read/validate superblock
* (initialize mount inode from the superblock)
* /
if ((rc = chkSuper(sb))) {
goto errout20;
}
108 ptr=0; /* line 2 added */
109 printk("%d\n",*ptr); /* line 3 added */
清
單 9 在向文件系統發出 mount 命令之后顯示一個 gdb 異常。kgdb
提供了幾條命令，如顯示數據結構和變量值以及顯示系統中的所有任務處于什么狀態、它們駐留在何處、它們在哪些地方使用了 CPU 等等。清單 9
將顯示回溯跟蹤為該問題提供的信息；where 命令用來執行反跟蹤，它將告訴被執行的調用在代碼中的什么地方停止。
清單 9. gdb 異常和反跟蹤
mount -t jfs /dev/sdb /jfs
Program received signal SIGSEGV, Segmentation fault.
jfs_mount (sb=0xf78a3800) at jfs_mount.c:109
109 printk("%d\n",*ptr);
(gdb)where
#0 jfs_mount (sb=0xf78a3800) at jfs_mount.c:109
#1 0xc01a0dbb in jfs_read_super ... at super.c:280
#2 0xc0149ff5 in get_sb_bdev ... at super.c:620
#3 0xc014a89f in do_kern_mount ... at super.c:849
#4 0xc0160e66 in do_add_mount ... at namespace.c:569
#5 0xc01610f4 in do_mount ... at namespace.c:683
#6 0xc01611ea in sys_mount ... at namespace.c:716
#7 0xc01074a7 in system_call () at af_packet.c:1891
#8 0x0 in ?? ()
(gdb)
下一部分還將討論這個相同的 JFS 段錯誤問題，但不設置調試器，如果您在非 kgdb 內核環境中執行清單 8 中的代碼，那么它使用內核可能生成的 Oops 消息。
Oops 分析
Oops
（也稱 panic，慌張）消息包含系統錯誤的細節，如 CPU 寄存器的內容。在 Linux
中，調試系統崩潰的傳統方法是分析在發生崩潰時發送到系統控制臺的 Oops 消息。一旦您掌握了細節，就可以將消息發送到 ksymoops
實用程序，它將試圖將代碼轉換為指令并將堆棧值映射到內核符號。在很多情況下，這些信息就足夠您確定錯誤的可能原因是什么了。請注意，Oops
消息并不包括核心文件。
讓我們假設系統剛剛創建了一條 Oops 消息。作為編寫代碼的人，您希望解決問題并確定什么導致了 Oops
消息的產生，或者您希望向顯示了 Oops 消息的代碼的開發者提供有關您的問題的大部分信息，從而及時地解決問題。Oops
消息是等式的一部分，但如果不通過 ksymoops 程序運行它也于事無補。下面的圖顯示了格式化 Oops 消息的過程。
格式化 Oops 消息
ksymoops
需要幾項內容：Oops 消息輸出、來自正在運行的內核的 System.map 文件，還有 /proc/ksyms、vmlinux 和
/proc/modules。關于如何使用 ksymoops，內核源代碼
/usr/src/linux/Documentation/oops-tracing.txt 中或 ksymoops
手冊頁上有完整的說明可以參考。Ksymoops 反匯編代碼部分，指出發生錯誤的指令，并顯示一個跟蹤部分表明代碼如何被調用。
首先，將 Oops 消息保存在一個文件中以便通過 ksymoops 實用程序運行它。清單 10 顯示了由安裝 JFS 文件系統的 mount 命令創建的 Oops 消息，問題是由清單 8 中添加到 JFS 安裝代碼的那三行代碼產生的。
清單 10. ksymoops 處理后的 Oops 消息
ksymoops 2.4.0 on i686 2.4.17. Options used
... 15:59:37 sfb1 kernel: Unable to handle kernel NULL pointer dereference at
virtual address 0000000
... 15:59:37 sfb1 kernel: c01588fc
... 15:59:37 sfb1 kernel: *pde = 0000000
... 15:59:37 sfb1 kernel: Oops: 0000
... 15:59:37 sfb1 kernel: CPU: 0
... 15:59:37 sfb1 kernel: EIP: 0010:[jfs_mount+60/704]
... 15:59:37 sfb1 kernel: Call Trace: [jfs_read_super+287/688]
[get_sb_bdev+563/736] [do_kern_mount+189/336] [do_add_mount+35/208]
[do_page_fault+0/1264]
... 15:59:37 sfb1 kernel: Call Trace: []...
... 15:59:37 sfb1 kernel: [>EIP; c01588fc <=====
...
Trace; c0106cf3
Code; c01588fc
00000000 <_EIP>:
Code; c01588fc <=====
0: 8b 2d 00 00 00 00 mov 0x0,%ebp <=====
Code; c0158902
6: 55 push %ebp
接
下來，您要確定 jfs_mount 中的哪一行代碼引起了這個問題。Oops 消息告訴我們問題是由位于偏移地址 3c
的指令引起的。做這件事的辦法之一是對 jfs_mount.o 文件使用 objdump 實用程序，然后查看偏移地址 3c。Objdump
用來反匯編模塊函數，看看您的 C 源代碼會產生什么匯編指令。清單 11 顯示了使用 objdump 后您將看到的內容，接著，我們查看
jfs_mount 的 C 代碼，可以看到空值是第 109 行引起的。偏移地址 3c 之所以很重要，是因為 Oops
消息將該處標識為引起問題的位置。
清單 11. jfs_mount 的匯編程序清單
109 printk("%d\n",*ptr);
objdump jfs_mount.o
jfs_mount.o: file format elf32-i386
Disassembly of section .text:
00000000 :
0:55 push %ebp
...
2c: e8 cf 03 00 00 call 400
31: 89 c3 mov %eax,%ebx
33: 58 pop %eax
34: 85 db test %ebx,%ebx
36: 0f 85 55 02 00 00 jne 291
3c: 8b 2d 00 00 00 00 mov 0x0,%ebp << problem line above
42: 55 push %ebp
kdb
Linux
內核調試器（Linux kernel debugger，kdb）是 Linux
內核的補丁，它提供了一種在系統能運行時對內核內存和數據結構進行檢查的辦法。請注意，kdb 不需要兩臺機器，不過它也不允許您像 kgdb
那樣進行源代碼級別上的調試。您可以添加額外的命令，給出該數據結構的標識或地址，這些命令便可以格式化和顯示基本的系統數據結構。目前的命令集允許您控
制包括以下操作在內的內核操作：
處理器單步執行
執行到某條特定指令時停止
當存取（或修改）某個特定的虛擬內存位置時停止
當存取輸入／輸出地址空間中的寄存器時停止
對當前活動的任務和所有其它任務進行堆棧回溯跟蹤（通過進程 ID）
對指令進行反匯編
追擊內存溢出
您肯定不想陷入類似在幾千次調用之后發生分配溢出這樣的情形。
我
們的小組花了許許多多時間來跟蹤稀奇古怪的內存錯誤問題。應用程序在我們的開發工作站上能運行，但在新的產品工作站上，這個應用程序在調用
malloc() 兩百萬次之后就不能運行了。真正的問題是在大約一百萬次調用之后發生了溢出。新系統之所有存在這個問題，是因為被保留的
malloc() 區域的布局有所不同，從而這些零散內存被放置在了不同的地方，在發生溢出時破壞了一些不同的內容。
我們用多種不同技術
來解決這個問題，其中一種是使用調試器，另一種是在源代碼中添加跟蹤功能。在我職業生涯的大概也是這個時候，我便開始關注內存調試工具，希望能更快更有效
地解決這些類型的問題。在開始一個新項目時，我最先做的事情之一就是運行 MEMWATCH 和 YAMD，看看它們是不是會指出內存管理方面的問題。
內存泄漏是應用程序中常見的問題，不過您可以使用本文所講述的工具來解決這些問題。
第 4 種情況：使用魔術鍵控順序進行回溯跟蹤
如果在 Linux 掛起時您的鍵盤仍然能用，那請您使用以下方法來幫助解決掛起問題的根源。遵循這些步驟，您便可以顯示當前運行的進程和所有使用魔術鍵控順序的進程的回溯跟蹤。
您正在運行的內核必須是在啟用 CONFIG_MAGIC_SYS-REQ 的情況下構建的。您還必須處在文本模式。CLTR+ALT+F1 會使您進入文本模式，CLTR+ALT+F7 會使您回到 X Windows。
當在文本模式時，請按 ，然后按 。上述魔術的擊鍵會分別給出當前運行的進程和所有進程的堆棧跟蹤。
請查找 /var/log/messages。如果一切設置正確，則系統應該已經為您轉換了內核的符號地址。回溯跟蹤將被寫到 /var/log/messages 文件中。
結束語
幫助調試 Linux 上的程序有許多不同的工具可供使用。本文講述的工具可以幫助您解決許多編碼問題。能顯示內存泄漏、溢出等等的位置的工具可以解決內存管理問題，我發現 MEMWATCH 和 YAMD 很有幫助。
使
用 Linux 內核補丁會使 gdb 能在 Linux 內核上工作，這對解決我工作中使用的 Linux
的文件系統方面的問題很有幫助。此外，跟蹤實用程序能幫助確定在系統調用期間文件系統實用程序什么地方出了故障。下次當您要擺平 Linux
中的錯誤時，請試試這些工具中的某一個。
轉自：http://www.vbgood.com/viewthread.php?tid=34811
要使計算機能完成人們預定的工作，首先必須為如何完成預定的工作設計一個算法，然后再根據算法編寫程序。計算機程序要對問題的每個對象和處理規則給出正確
詳盡的描述，其中程序的數據結構和變量用來描述問題的對象，程序結構、函數和語句用來描述問題的算法。算法數據結構是程序的兩個重要方面。
算法是問題求解過程的精確描述，一個算法由有限條可完全機械地執行的、有確定結果的指令組成。指令正確地描述了要完成的任務和它們被執行的順序。計算機按
算法指令所描述的順序執行算法的指令能在有限的步驟內終止，或終止于給出問題的解，或終止于指出問題對此輸入數據無解。
通常求解一個問題可能會有多種算法可供選擇，選擇的主要標準是算法的正確性和可靠性，簡單性和易理解性。其次是算法所需要的存儲空間少和執行更快等。
算法設計是一件非常困難的工作，經常采用的算法設計技術主要有迭代法、窮舉搜索法、遞推法、貪婪法、回溯法、分治法、動態規劃法等等。另外，為了更簡潔的形式設計和藐視算法，在算法設計時又常常采用遞歸技術，用遞歸描述算法。
一、迭代法
迭代法是用于求方程或方程組近似根的一種常用的算法設計方法。設方程為f(x)=0，用某種數學方法導出等價的形式x=g(x)，然后按以下步驟執行：
（1） 選一個方程的近似根，賦給變量x0；
（2） 將x0的值保存于變量x1，然后計算g(x1)，并將結果存于變量x0；
（3） 當x0與x1的差的絕對值還小于指定的精度要求時，重復步驟（2）的計算。
若方程有根，并且用上述方法計算出來的近似根序列收斂，則按上述方法求得的x0就認為是方程的根。上述算法用C程序的形式表示為：
【算法】迭代法求方程的根
{ x0=初始近似根；
do {
x1=x0；
x0=g(x1)； /*按特定的方程計算新的近似根*/
} while ( fabs(x0-x1)>Epsilon)；
printf(“方程的近似根是%f\n”，x0)；
}
迭代算法也常用于求方程組的根，令
X=（x0，x1，…，xn-1）
設方程組為：
xi=gi(X) (I=0，1，…，n-1)
則求方程組根的迭代算法可描述如下：
【算法】迭代法求方程組的根
{ for (i=0;i
x=初始近似根;
do {
for (i=0;i
y=x;
for (i=0;i
x=gi(X);
for (delta=0.0,i=0;i
if (fabs(y-x)>delta) delta=fabs(y-x)；
} while (delta>Epsilon)；
for (i=0;i
printf(“變量x[%d]的近似根是 %f”，I，x)；
printf(“\n”)；
}
具體使用迭代法求根時應注意以下兩種可能發生的情況：
（1） 如果方程無解，算法求出的近似根序列就不會收斂，迭代過程會變成死循環，因此在使用迭代算法前應先考察方程是否有解，并在程序中對迭代的次數給予限制；
（2） 方程雖然有解，但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。
二、窮舉搜索法
窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從眾找出那些符合要求的候選解作為問題的解。
【問題】 將A、B、C、D、E、F這六個變量排成如圖所示的三角形，這六個變量分別取[1，6]上的整數，且均不相同。求使三角形三條邊上的變量之和相等的全部解。如圖就是一個解。
程
序引入變量a、b、c、d、e、f，并讓它們分別順序取1至6的證書，在它們互不相同的條件下，測試由它們排成的如圖所示的三角形三條邊上的變量之和是否
相等，如相等即為一種滿足要求的排列，把它們輸出。當這些變量取盡所有的組合后，程序就可得到全部可能的解。細節見下面的程序。
【程序1】
# include
void main()
{ int a,b,c,d,e,f;
for (a=1;a<=6;a++)
for (b=1;b<=6;b++) {
if (b==a) continue;
for (c=1;c<=6;c++) {
if (c==a)||(c==b) continue;
for (d=1;d<=6;d++) {
if (d==a)||(d==b)||(d==c) continue;
for (e=1;e<=6;e++) {
if (e==a)||(e==b)||(e==c)||(e==d) continue;
f=21-(a+b+c+d+e);
if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {
printf(“%6d,a);
printf(“%4d%4d”,b,f);
printf(“%2d%4d%4d”,c,d,e);
scanf(“%*c”);
}
}
}
}
}
}
按窮舉法編寫的程序通常不能適應變化的情況。如問題改成有9個變量排成三角形，每條邊有4個變量的情況，程序的循環重數就要相應改變。
對
一組數窮盡所有排列，還有更直接的方法。將一個排列看作一個長整數，則所有排列對應著一組整數。將這組整數按從小到大的順序排列排成一個整數，從對應最小
的整數開始。按數列的遞增順序逐一列舉每個排列對應的每個整數，這能更有效地完成排列的窮舉。從一個排列找出對應數列的下一個排列可在當前排列的基礎上作
部分調整來實現。倘若當前排列為1，2，4，6，5，3，并令其對應的長整數為124653。要尋找比長整數124653更大的排列，可從該排列的最后一
個數字順序向前逐位考察，當發現排列中的某個數字比它前一個數字大時，如本例中的6比它的前一位數字4大，這說明還有對應更大整數的排列。但為了順序從小
到大列舉出所有的排列，不能立即調整得太大，如本例中將數字6與數字4交換得到的排列126453就不是排列124653的下一個排列。為了得到排列
124653的下一個排列，應從已經考察過的那部分數字中選出比數字大，但又是它們中最小的那一個數字，比如數字5，與數字4交換。該數字也是從后向前考
察過程中第一個比4大的數字。5與4交換后，得到排列125643。在前面數字1，2，5固定的情況下，還應選擇對應最小整數的那個排列，為此還需將后面
那部分數字的排列順序顛倒，如將數字6，4，3的排列順序顛倒，得到排列1，2，5，3，4，6，這才是排列1，2，4，6，5，3的下一個排列。按以上
想法編寫的程序如下。
【程序2】
# include
# define SIDE_N 3
# define LENGTH 3
# define VARIABLES 6
int A,B,C,D,E,F;
int *pt[]={&A,&B,&C,&D,&E,&F};
int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};
int side_total[SIDE_N];
main{}
{ int i,j,t,equal;
for (j=0;j
*pt[j]=j+1;
while(1)
{ for (i=0;i
{ for (t=j=0;j
t+=*side[j];
side_total=t;
}
for (equal=1,i=0;equal&&i
if (side_total!=side_total[i+1] equal=0;
if (equal)
{ for (i=1;i
printf(“%4d”,*pt);
printf(“\n”);
scanf(“%*c”);
}
for (j=VARIABLES-1;j>0;j--)
if (*pt[j]>*pt[j-1]) break;
if (j==0) break;
for (i=VARIABLES-1;i>=j;i--)
if (*pt>*pt[i-1]) break;
t=*pt[j-1];* pt[j-1] =* pt; *pt=t;
for (i=VARIABLES-1;i>j;i--,j++)
{ t=*pt[j]; *pt[j] =* pt; *pt=t; }
}
}
從上述問題解決的方法中，最重要的因素就是確定某種方法來確定所有的候選解。下面再用一個示例來加以說明。
【問題】 背包問題
問題描述：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。
設n
個物品的重量和價值分別存儲于數組w[ ]和v[ ]中，限制重量為tw。考慮一個n元組（x0，x1，…，xn-1），其中xi=0
表示第i個物品沒有選取，而xi=1則表示第i個物品被選取。顯然這個n元組等價于一個選擇方案。用枚舉法解決背包問題，需要枚舉所有的選取方案，而根據
上述方法，我們只要枚舉所有的n元組，就可以得到問題的解。
顯然，每個分量取值為0或1的n元組的個數共為2n個。而每個n元組其實對應了一個長度為n的二進制數，且這些二進制數的取值范圍為0～2n-1。因此，如果把0～2n-1分別轉化為相應的二進制數，則可以得到我們所需要的2n個n元組。
【算法】
maxv=0;
for (i=0;i<2n;i++)
{ B[0..n-1]=0;
把i轉化為二進制數，存儲于數組B中;
temp_w=0;
temp_v=0;
for (j=0;j
{ if (B[j]==1)
{ temp_w=temp_w+w[j];
temp_v=temp_v+v[j];
}
if ((temp_w<=tw)&&(temp_v>maxv))
{ maxv=temp_v;
保存該B數組；
}
}
}
三、遞推法
遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。設要求
問題規模為N的解，當N=1時，解或為已知，或能非常方便地得到解。能采用遞推法構造算法的問題有重要的遞推性質，即當得到問題規模為i-1的解后，由問
題的遞推性質，能從已求得的規模為1，2，…，i-1的一系列解，構造出問題規模為
I的解。這樣，程序可從i=0或i=1出發，重復地，由已知至i-1規模的解，通過遞推，獲得規模為i的解，直至得到規模為N的解。
【問題】 階乘計算
問題描述：編寫程序，對給定的n（n≦100），計算并輸出k的階乘k！（k=1，2，…，n）的全部有效數字。
由于要求的整數可能大大超出一般整數的位數，程序用一維數組存儲長整數，存儲長整數數組的每個元素只存儲長整數的一位數字。如有m位成整數N用數組a[ ]存儲：
N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100
并用a[0]存儲長整數N的位數m，即a[0]=m。按上述約定，數組的每個元素存儲k的階乘k！的一位數字，并從低位到高位依次存于數組的第二個元素、第三個元素……。例如，5！=120，在數組中的存儲形式為：
3 0 2 1 ……
首元素3表示長整數是一個3位數，接著是低位到高位依次是0、2、1，表示成整數120。
計算階乘k！可采用對已求得的階乘(k-1)！連續累加k-1次后求得。例如，已知4！=24，計算5！，可對原來的24累加4次24后得到120。細節見以下程序。
# include
# include
# define MAXN 1000
void pnext(int a[ ],int k)
{ int *b,m=a[0],i,j,r,carry;
b=(int * ) malloc(sizeof(int)* (m+1));
for ( i=1;i<=m;i++) b=a;
for ( j=1;j<=k;j++)
{ for ( carry=0,i=1;i<=m;i++)
{ r=(i
a=r%10;
carry=r/10;
}
if (carry) a[++m]=carry;
}
free(b);
a[0]=m;
}
void write(int *a,int k)
{ int i;
printf(“%4d！=”,k);
for (i=a[0];i>0;i--)
printf(“%d”,a);
printf(“\n\n”);
}
void main()
{ int a[MAXN],n,k;
printf(“Enter the number n: “);
scanf(“%d”,&n);
a[0]=1;
a[1]=1;
write(a,1);
for (k=2;k<=n;k++)
{ pnext(a,k);
write(a,k);
getchar();
}
}
四、遞歸
遞歸是設計和描述算法的一種有力的工具，由于它在復雜算法的描述中被經常采用，為此在進一步介紹其他算法設計方法之前先討論它。
能
采用遞歸描述的算法通常有這樣的特征：為求解規模為N的問題，設法將它分解成規模較小的問題，然后從這些小問題的解方便地構造出大問題的解，并且這些規模
較小的問題也能采用同樣的分解和綜合方法，分解成規模更小的問題，并從這些更小問題的解構造出規模較大問題的解。特別地，當規模N=1時，能直接得解。
【問題】 編寫計算斐波那契（Fibonacci）數列的第n項函數fib（n）。
斐波那契數列為：0、1、1、2、3、……，即：
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2) （當n>1時）。
寫成遞歸函數有：
int fib(int n)
{ if (n==0) return 0;
if (n==1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
遞
歸算法的執行過程分遞推和回歸兩個階段。在遞推階段，把較復雜的問題（規模為n）的求解推到比原問題簡單一些的問題（規模小于n）的求解。例如上例中，求
解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說，為計算fib(n)，必須先計算fib(n-1)和fib(n-
2)，而計算fib(n-1)和fib(n-2)，又必須先計算fib(n-3)和fib(n-4)。依次類推，直至計算fib(1)和fib(0)，分
別能立即得到結果1和0。在遞推階段，必須要有終止遞歸的情況。例如在函數fib中，當n為1和0的情況。
在回歸階段，當獲得最簡單情況的解后，逐級返回，依次得到稍復雜問題的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的結果，……，在得到了fib(n-1)和fib(n-2)的結果后，返回得到fib(n)的結果。
在編寫遞歸函數時要注意，函數中的局部變量和參數知識局限于當前調用層，當遞推進入“簡單問題”層時，原來層次上的參數和局部變量便被隱蔽起來。在一系列“簡單問題”層，它們各有自己的參數和局部變量。
由
于遞歸引起一系列的函數調用，并且可能會有一系列的重復計算，遞歸算法的執行效率相對較低。當某個遞歸算法能較方便地轉換成遞推算法時，通常按遞推算法編
寫程序。例如上例計算斐波那契數列的第n項的函數fib(n)應采用遞推算法，即從斐波那契數列的前兩項出發，逐次由前兩項計算出下一項，直至計算出要求
的第n項。
【問題】 組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。例如n=5，r=3的所有組合為： （1）5、4、3 （2）5、4、2 （3）5、4、1
（4）5、3、2 （5）5、3、1 （6）5、2、1
（7）4、3、2 （8）4、3、1 （9）4、2、1
（10）3、2、1
分
析所列的10個組合，可以采用這樣的遞歸思想來考慮求組合函數的算法。設函數為void comb(int m,int
k)為找出從自然數1、2、……、m中任取k個數的所有組合。當組合的第一個數字選定時，其后的數字是從余下的m-1個數中取k-1數的組合。這就將求m
個數中取k個數的組合問題轉化成求m-1個數中取k-1個數的組合問題。設函數引入工作數組a[
]存放求出的組合的數字，約定函數將確定的k個數字組合的第一個數字放在a[k]中，當一個組合求出后，才將a[
]中的一個組合輸出。第一個數可以是m、m-1、……、k，函數將確定組合的第一個數字放入數組后，有兩種可能的選擇，因還未去頂組合的其余元素，繼續遞
歸去確定；或因已確定了組合的全部元素，輸出這個組合。細節見以下程序中的函數comb。
【程序】
# include
# define MAXN 100
int a[MAXN];
void comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1)
comb(i-1,k-1);
else
{ for (j=a[0];j>0;j--)
printf(“%4d”,a[j]);
printf(“\n”);
}
}
}
void main()
{ a[0]=3;
comb(5,3);
}
【問題】 背包問題
問題描述：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。
設n
件物品的重量分別為w0、w1、…、wn-1，物品的價值分別為v0、v1、…、vn-1。采用遞歸尋找物品的選擇方案。設前面已有了多種選擇的方案，并
保留了其中總價值最大的方案于數組option[ ]，該方案的總價值存于變量maxv。當前正在考察新方案，其物品選擇情況保存于數組cop[
]。假定當前方案已考慮了前i-1件物品，現在要考慮第i件物品；當前方案已包含的物品的重量之和為tw；至此，若其余物品都選擇是可能的話，本方案能達
到的總價值的期望值為tv。算法引入tv是當一旦當前方案的總價值的期望值也小于前面方案的總價值maxv時，繼續考察當前方案變成無意義的工作，應終止
當前方案，立即去考察下一個方案。因為當方案的總價值不比maxv大時，該方案不會被再考察，這同時保證函數后找到的方案一定會比前面的方案更好。
對于第i件物品的選擇考慮有兩種可能：
（1） 考慮物品i被選擇，這種可能性僅當包含它不會超過方案總重量限制時才是可行的。選中后，繼續遞歸去考慮其余物品的選擇。
（2） 考慮物品i不被選擇，這種可能性僅當不包含物品i也有可能會找到價值更大的方案的情況。
按以上思想寫出遞歸算法如下：
try(物品i，當前選擇已達到的重量和，本方案可能達到的總價值tv)
{ /*考慮物品i包含在當前方案中的可能性*/
if(包含物品i是可以接受的)
{ 將物品i包含在當前方案中；
if (i
try(i+1,tw+物品i的重量,tv);
else
/*又一個完整方案，因為它比前面的方案好，以它作為最佳方案*/
以當前方案作為臨時最佳方案保存;
恢復物品i不包含狀態；
}
/*考慮物品i不包含在當前方案中的可能性*/
if (不包含物品i僅是可男考慮的)
if (i
try(i+1,tw,tv-物品i的價值)；
else
/*又一個完整方案，因它比前面的方案好，以它作為最佳方案*/
以當前方案作為臨時最佳方案保存;
}
為了理解上述算法，特舉以下實例。設有4件物品，它們的重量和價值見表：
物品 0 1 2 3
重量 5 3 2 1
價值 4 4 3 1
并設限制重量為7。則按以上算法，下圖表示找解過程。由圖知，一旦找到一個解，算法就進一步找更好的佳。如能判定某個查找分支不會找到更好的解，算法不會在該分支繼續查找，而是立即終止該分支，并去考察下一個分支。
按上述算法編寫函數和程序如下：
【程序】
# include
# define N 100
double limitW,totV,maxV;
int option[N],cop[N];
struct { double weight;
double value;
}a[N];
int n;
void find(int i,double tw,double tv)
{ int k;
/*考慮物品i包含在當前方案中的可能性*/
if (tw+a.weight<=limitW)
{ cop=1;
if (i
else
{ for (k=0;k
option[k]=cop[k];
maxv=tv;
}
cop=0;
}
/*考慮物品i不包含在當前方案中的可能性*/
if (tv-a.value>maxV)
if (i
else
{ for (k=0;k
option[k]=cop[k];
maxv=tv-a.value;
}
}
void main()
{ int k;
double w,v;
printf(“輸入物品種數\n”);
scanf((“%d”,&n);
printf(“輸入各物品的重量和價值\n”);
for (totv=0.0,k=0;k
{ scanf(“%1f%1f”,&w,&v);
a[k].weight=w;
a[k].value=v;
totV+=V;
}
printf(“輸入限制重量\n”);
scanf(“%1f”,&limitV);
maxv=0.0;
for (k=0;k find(0,0.0,totV);
for (k=0;k
if (option[k]) printf(“%4d”,k+1);
printf(“\n總價值為%.2f\n”,maxv);
}
作
為對比，下面以同樣的解題思想，考慮非遞歸的程序解。為了提高找解速度，程序不是簡單地逐一生成所有候選解，而是從每個物品對候選解的影響來形成值得進一
步考慮的候選解，一個候選解是通過依次考察每個物品形成的。對物品i的考察有這樣幾種情況：當該物品被包含在候選解中依舊滿足解的總重量的限制，該物品被
包含在候選解中是應該繼續考慮的；反之，該物品不應該包括在當前正在形成的候選解中。同樣地，僅當物品不被包括在候選解中，還是有可能找到比目前臨時最佳
解更好的候選解時，才去考慮該物品不被包括在候選解中；反之，該物品不包括在當前候選解中的方案也不應繼續考慮。對于任一值得繼續考慮的方案，程序就去進
一步考慮下一個物品。
【程序】
# include
# define N 100
double limitW;
int cop[N];
struct ele { double weight;
double value;
} a[N];
int k,n;
struct { int ;
double tw;
double tv;
}twv[N];
void next(int i,double tw,double tv)
{ twv.=1;
twv.tw=tw;
twv.tv=tv;
}
double find(struct ele *a,int n)
{ int i,k,f;
double maxv,tw,tv,totv;
maxv=0;
for (totv=0.0,k=0;k
totv+=a[k].value;
next(0,0.0,totv);
i=0;
While (i>=0)
{ f=twv.;
tw=twv.tw;
tv=twv.tv;
switch(f)
{ case 1: twv.++;
if (tw+a.weight<=limitW)
if (i
{ next(i+1,tw+a.weight,tv);
i++;
}
else
{ maxv=tv;
for (k=0;k
cop[k]=twv[k].!=0;
}
break;
case 0: i--;
break;
default: twv.=0;
if (tv-a.value>maxv)
if (i
{ next(i+1,tw,tv-a.value);
i++;
}
else
{ maxv=tv-a.value;
for (k=0;k
cop[k]=twv[k].!=0;
}
break;
}
}
return maxv;
}
void main()
{ double maxv;
printf(“輸入物品種數\n”);
scanf((“%d”,&n);
printf(“輸入限制重量\n”);
scanf(“%1f”,&limitW);
printf(“輸入各物品的重量和價值\n”);
for (k=0;k
scanf(“%1f%1f”,&a[k].weight,&a[k].value);
maxv=find(a,n);
printf(“\n選中的物品為\n”);
for (k=0;k
if (option[k]) printf(“%4d”,k+1);
printf(“\n總價值為%.2f\n”,maxv);
}
五、回溯法
回溯法也稱為試探法，該方法首先暫時放棄關于問題規模大小的限制，并將
問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規模要求外，滿足所有其他要
求時，繼續擴大當前候選解的規模，并繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選
解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模，以繼續試探的過程稱為向前試探。
1、回溯法的一般描述
可用回溯法求解的問題
P，通常要能表達為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態空間 E={（x1，x2，…，xn）∣xi∈Si
，i=1，2，…，n}，給定關于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且
|Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。
我
們發現，對于許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j
（jj。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以
肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它
們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的算法。
回溯法首先將問題P的n元組的狀態空間E表示成一棵高為n的帶權有序樹T，把在E中求問題P的所有解轉化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構造：
設Si
中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si|
=mi，i=1，2，…，n。從根開始，讓T的第I層的每一個結點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權xi+1
(1) ，xi+1(2) ，…，xi+1(mi)
，i=0，1，2，…，n-1。照這種構造方式，E中的一個n元組（x1，x2，…，xn）對應于T中的一個葉子結點，T的根到這個葉子結點的路徑上依次
的n條邊的權分別為x1，x2，…，xn，反之亦然。另外，對于任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個前綴I元組（x1，
x2，…，xi）對應于T中的一個非葉子結點，T的根到這個非葉子結點的路徑上依次的I條邊的權分別為x1，x2，…，xi，反之亦然。特別，E中的任意
一個n元組的空前綴（），對應于T的根。
因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結點，要求從T的根到該葉子結點的路徑上依次的
n條邊相應帶的n個權x1，x2，…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結點，很自然的一種方式是從根出發，按深度優先的策略逐步深
入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。
在回溯法中，上述引入的樹被稱為問題P的狀態空間樹；樹T上任意一個結點被稱為問題P的狀態結點；樹T上的任意一個葉子結點被稱為問題P的一個解狀態結點；樹T上滿足約束集D的全部約束的任意一個葉子結點被稱為問題P的一個回答狀態結點，它對應于問題P的一個解。
【問題】 組合問題
問題描述：找出從自然數1、2、……、n中任取r個數的所有組合。
例如n=5，r=3的所有組合為：
（1）1、2、3 （2）1、2、4 （3）1、2、5
（4）1、3、4 （5）1、3、5 （6）1、4、5
（7）2、3、4 （8）2、3、5 （9）2、4、5
（10）3、4、5
則該問題的狀態空間為：
E={（x1，x2，x3）∣xi∈S ，i=1，2，3 } 其中：S={1，2，3，4，5}
約束集為： x1
顯然該約束集具有完備性。
2、回溯法的方法
對于具有完備約束集D的一般問題P及其相應的狀態空間樹T，利用T的層次結構和D的完備性，在T中搜索問題P的所有解的回溯法可以形象地描述為：
從T
的根出發，按深度優先的策略，系統地搜索以其為根的子樹中可能包含著回答結點的所有狀態結點，而跳過對肯定不含回答結點的所有子樹的搜索，以提高搜索效
率。具體地說，當搜索按深度優先策略到達一個滿足D中所有有關約束的狀態結點時，即“激活”該狀態結點，以便繼續往深層搜索；否則跳過對以該狀態結點為根
的子樹的搜索，而一邊逐層地向該狀態結點的祖先結點回溯，一邊“殺死”其兒子結點已被搜索遍的祖先結點，直到遇到其兒子結點未被搜索遍的祖先結點，即轉向
其未被搜索的一個兒子結點繼續搜索。
在搜索過程中，只要所激活的狀態結點又滿足終結條件，那么它就是回答結點，應該把它輸出或保存。由于在回溯法求解問題時，一般要求出問題的所有解，因此在得到回答結點后，同時也要進行回溯，以便得到問題的其他解，直至回溯到T的根且根的所有兒子結點均已被搜索過為止。
例
如在組合問題中，從T的根出發深度優先遍歷該樹。當遍歷到結點（1，2）時，雖然它滿足約束條件，但還不是回答結點，則應繼續深度遍歷；當遍歷到葉子結點
（1，2，5）時，由于它已是一個回答結點，則保存（或輸出）該結點，并回溯到其雙親結點，繼續深度遍歷；當遍歷到結點（1，5）時，由于它已是葉子結
點，但不滿足約束條件，故也需回溯。
3、回溯法的一般流程和技術
在用回溯法求解有關問題的過程中，一般是一邊建樹，一邊遍歷該樹。在回溯法中我們一般采用非遞歸方法。下面，我們給出回溯法的非遞歸算法的一般流程：
在用回溯法求解問題，也即在遍歷狀態空間樹的過程中，如果采用非遞歸方法，則我們一般要用到棧的數據結構。這時，不僅可以用棧來表示正在遍歷的樹的結點，而且可以很方便地表示建立孩子結點和回溯過程。
例
如在組合問題中，我們用一個一維數組Stack[
]表示棧。開始棧空，則表示了樹的根結點。如果元素1進棧，則表示建立并遍歷（1）結點；這時如果元素2進棧，則表示建立并遍歷（1，2）結點；元素3再
進棧，則表示建立并遍歷（1，2，3）結點。這時可以判斷它滿足所有約束條件，是問題的一個解，輸出（或保存）。這時只要棧頂元素（3）出棧，即表示從結
點（1，2，3）回溯到結點（1，2）。
【問題】 組合問題
問題描述：找出從自然數1，2，…，n中任取r個數的所有組合。
采用回溯法找問題的解，將找到的組合以從小到大順序存于a[0]，a[1]，…，a[r-1]中，組合的元素滿足以下性質：
（1） a[i+1]>a，后一個數字比前一個大；
（2） a-i<=n-r+1。
按回溯法的思想，找解過程可以敘述如下：
首
先放棄組合數個數為r的條件，候選組合從只有一個數字1開始。因該候選解滿足除問題規模之外的全部條件，擴大其規模，并使其滿足上述條件（1），候選組合
改為1，2。繼續這一過程，得到候選組合1，2，3。該候選解滿足包括問題規模在內的全部條件，因而是一個解。在該解的基礎上，選下一個候選解，因a
[2]上的3調整為4，以及以后調整為5都滿足問題的全部要求，得到解1，2，4和1，2，5。由于對5不能再作調整，就要從a[2]回溯到a[1]，這
時，a[1]=2，可以調整為3，并向前試探，得到解1，3，4。重復上述向前試探和向后回溯，直至要從a[0]再回溯時，說明已經找完問題的全部解。按
上述思想寫成程序如下：
【程序】
# define MAXN 100
int a[MAXN];
void comb(int m,int r)
{ int i,j;
i=0;
a=1;
do {
if (a-i<=m-r+1
{ if (i==r-1)
{ for (j=0;j
printf(“%4d”,a[j]);
printf(“\n”);
}
a++;
continue;
}
else
{ if (i==0)
return;
a[--i]++;
}
} while (1)
}
main()
{ comb(5,3);
}
【問題】 填字游戲
問題描述：在3×3個方格的方陣中要填入數字1到N（N≥10）內的某9個數字，每個方格填一個整數，似的所有相鄰兩個方格內的兩個整數之和為質數。試求出所有滿足這個要求的各種數字填法。
可
用試探發找到問題的解，即從第一個方格開始，為當前方格尋找一個合理的整數填入，并在當前位置正確填入后，為下一方格尋找可填入的合理整數。如不能為當前
方格找到一個合理的可填證書，就要回退到前一方格，調整前一方格的填入數。當第九個方格也填入合理的整數后，就找到了一個解，將該解輸出，并調整第九個的
填入的整數，尋找下一個解。
為找到一個滿足要求的9個數的填法，從還未填一個數開始，按某種順序（如從小到大的順序）每次在當前位置填入一個整
數，然后檢查當前填入的整數是否能滿足要求。在滿足要求的情況下，繼續用同樣的方法為下一方格填入整數。如果最近填入的整數不能滿足要求，就改變填入的整
數。如對當前方格試盡所有可能的整數，都不能滿足要求，就得回退到前一方格，并調整前一方格填入的整數。如此重復執行擴展、檢查或調整、檢查，直到找到一
個滿足問題要求的解，將解輸出。
回溯法找一個解的算法：
{ int m=0,ok=1;
int n=8;
do{
if (ok) 擴展;
else 調整;
ok=檢查前m個整數填放的合理性;
} while ((!ok||m!=n)&&(m!=0))
if (m!=0) 輸出解;
else 輸出無解報告；
}
如果程序要找全部解，則在將找到的解輸出后，應繼續調整最后位置上填放的整數，試圖去找下一個解。相應的算法如下：
回溯法找全部解的算法：
{ int m=0,ok=1;
int n=8;
do{
if (ok)
{ if (m==n)
{ 輸出解；
調整；
}
else 擴展;
}
else 調整;
ok=檢查前m個整數填放的合理性;
} while (m!=0);
}
為
了確保程序能夠終止，調整時必須保證曾被放棄過的填數序列不會再次實驗，即要求按某種有許模型生成填數序列。給解的候選者設定一個被檢驗的順序，按這個順
序逐一形成候選者并檢驗。從小到大或從大到小，都是可以采用的方法。如擴展時，先在新位置填入整數1，調整時，找當前候選解中下一個還未被使用過的整數。
將上述擴展、調整、檢驗都編寫成程序，細節見以下找全部解的程序。
【程序】
# include
# define N 12
void write(int a[ ])
{ int i,j;
for (i=0;i<3;i++)
{ for (j=0;j<3;j++)
printf(“%3d”,a[3*i+j]);
printf(“\n”);
}
scanf(“%*c”);
}
int b[N+1];
int a[10];
int isprime(int m)
{ int i;
int primes[ ]={2,3,5,7,11,17,19,23,29,-1};
if (m==1||m%2=0) return 0;
for (i=0;primes>0;i++)
if (m==primes) return 1;
for (i=3;i*i<=m;)
{ if (m%i==0) return 0;
i+=2;
}
return 1;
}
int checkmatrix[ ][3]={ {-1},{0,-1},{1,-1},{0,-1},{1,3,-1},
{2,4,-1},{3,-1},{4,6,-1},{5,7,-1}};
int selectnum(int start)
{ int j;
for (j=start;j<=N;j++)
if (b[j]) return j
return 0;
}
int check(int pos)
{ int i,j;
if (pos<0) return 0;
for (i=0;(j=checkmatrix[pos])>=0;i++)
if (!isprime(a[pos]+a[j])
return 0;
return 1;
}
int extend(int pos)
{ a[++pos]=selectnum(1);
b[a][pos]]=0;
return pos;
}
int change(int pos)
{ int j;
while (pos>=0&&(j=selectnum(a[pos]+1))==0)
b[a[pos--]]=1;
if (pos<0) return –1
b[a[pos]]=1;
a[pos]=j;
b[j]=0;
return pos;
}
void find()
{ int ok=0,pos=0;
a[pos]=1;
b[a[pos]]=0;
do {
if (ok)
if (pos==8)
{ write(a);
pos=change(pos);
}
else pos=extend(pos);
else pos=change(pos);
ok=check(pos);
} while (pos>=0)
}
void main()
{ int i;
for (i=1;i<=N;i++)
b=1;
find();
}
【問題】 n皇后問題
問題描述：求出在一個n×n的棋盤上，放置n個不能互相捕捉的國際象棋“皇后”的所有布局。
這是來源于國際象棋的一個問題。皇后可以沿著縱橫和兩條斜線4個方向相互捕捉。如圖所示，一個皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個皇后相互捕捉。
1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × Q × × × × ×
× × ×
× × ×
× ×
× ×
從圖中可以得到以下啟示：一個合適的解應是在每列、每行上只有一個皇后，且一條斜線上也只有一個皇后。
求
解過程從空配置開始。在第1列至第m列為合理配置的基礎上，再配置第m+1列，直至第n列配置也是合理時，就找到了一個解。接著改變第n列配置，希望獲得
下一個解。另外，在任一列上，可能有n種配置。開始時配置在第1行，以后改變時，順次選擇第2行、第3行、…、直到第n行。當第n行配置也找不到一個合理
的配置時，就要回溯，去改變前一列的配置。得到求解皇后問題的算法如下：
{ 輸入棋盤大小值n；
m=0;
good=1;
do {
if (good)
if (m==n)
{ 輸出解；
改變之，形成下一個候選解;
}
else 擴展當前候選接至下一列；
else 改變之，形成下一個候選解；
good=檢查當前候選解的合理性；
} while (m!=0);
}
在
編寫程序之前，先確定邊式棋盤的數據結構。比較直觀的方法是采用一個二維數組，但仔細觀察就會發現，這種表示方法給調整候選解及檢查其合理性帶來困難。更
好的方法乃是盡可能直接表示那些常用的信息。對于本題來說，“常用信息”并不是皇后的具體位置，而是“一個皇后是否已經在某行和某條斜線合理地安置好
了”。因在某一列上恰好放一個皇后，引入一個一維數組（col[
]），值col表示在棋盤第i列、col行有一個皇后。例如：col[3]=4，就表示在棋盤的第3列、第4行上有一個皇后。另外，為了使程序在找完了全
部解后回溯到最初位置，設定col[0]的初值為0當回溯到第0列時，說明程序已求得全部解，結束程序運行。
為使程序在檢查皇后配置的合理性方面簡易方便，引入以下三個工作數組：
（1） 數組a[ ]，a[k]表示第k行上還沒有皇后；
（2） 數組b[ ]，b[k]表示第k列右高左低斜線上沒有皇后；
（3） 數組 c[ ]，c[k]表示第k列左高右低斜線上沒有皇后；
棋盤中同一右高左低斜線上的方格，他們的行號與列號之和相同；同一左高右低斜線上的方格，他們的行號與列號之差均相同。
初
始時，所有行和斜線上均沒有皇后，從第1列的第1行配置第一個皇后開始，在第m列col[m]行放置了一個合理的皇后后，準備考察第m+1列時，在數組
a[ ]、b[ ]和c[
]中為第m列，col[m]行的位置設定有皇后標志；當從第m列回溯到第m-1列，并準備調整第m-1列的皇后配置時，清除在數組a[ ]、b[
]和c[ ]中設置的關于第m-1列，col[m-1]行有皇后的標志。一個皇后在m列，col[m]行方格內配置是合理的，由數組a[ ]、b[
]和c[ ]對應位置的值都為1來確定。細節見以下程序：
【程序】
# include
# include
# define MAXN 20
int n,m,good;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
void main()
{ int j;
char awn;
printf(“Enter n: “); scanf(“%d”,&n);
for (j=0;j<=n;j++) a[j]=1;
for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
m=1; col[1]=1; good=1; col[0]=0;
do {
if (good)
if (m==n)
{ printf(“列\t行”);
for (j=1;j<=n;j++)
printf(“%3d\t%d\n”,j,col[j]);
printf(“Enter a character (Q/q for exit)!\n”);
scanf(“%c”,&awn);
if (awn==’Q’||awn==’q’) exit(0);
while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
else
{ a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
}
else
{ while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
} while (m!=0);
}
試探法找解算法也常常被編寫成遞歸函數，下面兩程序中的函數queen_all()和函數queen_one()能分別用來解皇后問題的全部解和一個解。
【程序】
# include
# include
# define MAXN 20
int n;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
void main()
{ int j;
printf(“Enter n: “); scanf(“%d”,&n);
for (j=0;j<=n;j++) a[j]=1;
for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
queen_all(1,n);
}
void queen_all(int k,int n)
{ int i,j;
char awn;
for (i=1;i<=n;i++)
if (a&&b[k+i]&&c[n+k-i])
{ col[k]=i;
a=b[k+i]=c[n+k-i]=0;
if (k==n)
{ printf(“列\t行”);
for (j=1;j<=n;j++)
printf(“%3d\t%d\n”,j,col[j]);
printf(“Enter a character (Q/q for exit)!\n”);
scanf(“%c”,&awn);
if (awn==’Q’||awn==’q’) exit(0);
}
queen_all(k+1,n);
a=b[k+i]=c[n+k-i];
}
}
采
用遞歸方法找一個解與找全部解稍有不同，在找一個解的算法中，遞歸算法要對當前候選解最終是否能成為解要有回答。當它成為最終解時，遞歸函數就不再遞歸試
探，立即返回；若不能成為解，就得繼續試探。設函數queen_one()返回1表示找到解，返回0表示當前候選解不能成為解。細節見以下函數。
【程序】
# define MAXN 20
int n;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
int queen_one(int k,int n)
{ int i,found;
i=found=0;
While (!found&&i
{ i++;
if (a&&b[k+i]&&c[n+k-i])
{ col[k]=i;
a=b[k+i]=c[n+k-i]=0;
if (k==n) return 1;
else
found=queen_one(k+1,n);
a=b[k+i]=c[n+k-i]=1;
}
}
return found;
}
六、貪婪法
貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。
例
如平時購物找錢時，為使找回的零錢的硬幣數最少，不考慮找零錢的所有各種發表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的
幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪法。這種方法在這里總是最優，是因為銀行對其發行的硬幣種類和硬幣面值的
巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，
共找回5個硬幣。但最優的解應是3個5單位面值的硬幣。
【問題】 裝箱問題
問題描述：裝箱問題可簡述如下：設有編號為0、
1、…、n-1的n種物品，體積分別為v0、v1、…、vn-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過V，即對于
0≤i＜n，有0＜vi≤V。不同的裝箱方案所需要的箱子數目可能不同。裝箱問題要求使裝盡這n種物品的箱子數要少。
若考察將n種物品的集合分劃
成n個或小于n個物品的所有子集，最優解就可以找到。但所有可能劃分的總數太大。對適當大的n，找出所有可能的劃分要花費的時間是無法承受的。為此，對裝
箱問題采用非常簡單的近似算法，即貪婪法。該算法依次將物品放到它第一個能放進去的箱子中，該算法雖不能保證找到最優解，但還是能找到非常好的解。不失一
般性，設n件物品的體積是按從大到小排好序的，即有v0≥v1≥…≥vn-1。如不滿足上述要求，只要先對這n件物品按它們的體積從大到小排序，然后按排
序結果對物品重新編號即可。裝箱算法簡單描述如下：
{ 輸入箱子的容積；
輸入物品種數n；
按體積從大到小順序，輸入各物品的體積；
預置已用箱子鏈為空；
預置已用箱子計數器box_count為0；
for (i=0;i
{ 從已用的第一只箱子開始順序尋找能放入物品i 的箱子j；
if （已用箱子都不能再放物品i）
{ 另用一個箱子，并將物品i放入該箱子；
box_count++；
}
else
將物品i放入箱子j；
}
}
上
述算法能求出需要的箱子數box_count，并能求出各箱子所裝物品。下面的例子說明該算法不一定能找到最優解，設有6種物品，它們的體積分別為：
60、45、35、20、20和20單位體積，箱子的容積為100個單位體積。按上述算法計算，需三只箱子，各箱子所裝物品分別為：第一只箱子裝物品1、
3；第二只箱子裝物品2、4、5；第三只箱子裝物品6。而最優解為兩只箱子，分別裝物品1、4、5和2、3、6。
若每只箱子所裝物品用鏈表來表示，鏈表首結點指針存于一個結構中，結構記錄尚剩余的空間量和該箱子所裝物品鏈表的首指針。另將全部箱子的信息也構成鏈表。以下是按以上算法編寫的程序。
【程序】
# include
# include
typedef struct ele
{ int vno;
struct ele *link;
} ELE;
typedef struct hnode
{ int remainder;
ELE *head;
Struct hnode *next;
} HNODE;
void main()
{ int n, i, box_count, box_volume, *a;
HNODE *box_h, *box_t, *j;
ELE *p, *q;
Printf(“輸入箱子容積\n”);
Scanf(“%d”,&box_volume);
Printf(“輸入物品種數\n”);
Scanf(“%d”,&n);
A=(int *)malloc(sizeof(int)*n);
Printf(“請按體積從大到小順序輸入各物品的體積：”);
For (i=0;i
Box_h=box_t=NULL;
Box_count=0;
For (i=0;i
{ p=(ELE *)malloc(sizeof(ELE));
p->vno=i;
for (j=box_h;j!=NULL;j=j->next)
if (j->remainder>=a) break;
if (j==NULL)
{ j=(HNODE *)malloc(sizeof(HNODE));
j->remainder=box_volume-a;
j->head=NULL;
if (box_h==NULL) box_h=box_t=j;
else box_t=boix_t->next=j;
j->next=NULL;
box_count++;
}
else j->remainder-=a;
for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);
if (q==NULL)
{ p->link=j->head;
j->head=p;
}
else
{ p->link=NULL;
q->link=p;
}
}
printf(“共使用了%d只箱子”，box_count);
printf(“各箱子裝物品情況如下：”);
for (j=box_h,i=1;j!=NULL;j=j->next,i++)
{ printf(“第%2d只箱子，還剩余容積%4d，所裝物品有；\n”,I,j->remainder);
for (p=j->head;p!=NULL;p=p->link)
printf(“%4d”,p->vno+1);
printf(“\n”);
}
}
【問題】 馬的遍歷
問題描述：在8×8方格的棋盤上，從任意指定的方格出發，為馬尋找一條走遍棋盤每一格并且只經過一次的一條路徑。
馬
在某個方格，可以在一步內到達的不同位置最多有8個，如圖所示。如用二維數組board[ ][
]表示棋盤，其元素記錄馬經過該位置時的步驟號。另對馬的8種可能走法（稱為著法）設定一個順序，如當前位置在棋盤的（i，j）方格，下一個可能的位置依
次為（i+2，j+1）、（i+1，j+2）、（i-1，j+2）、（i-2，j+1）、（i-2，j-1）、（i-1，j-2）、（i+1，j-2）、
（i+2，j-1），實際可以走的位置盡限于還未走過的和不越出邊界的那些位置。為便于程序的同意處理，可以引入兩個數組，分別存儲各種可能走法對當前位
置的縱橫增量。
4 3
5 2
馬
6 1
7 0
對于本題，一般可以采用回溯法，這里采用
Warnsdoff策略求解，這也是一種貪婪法，其選擇下一出口的貪婪標準是在那些允許走的位置中，選擇出口最少的那個位置。如馬的當前位置（i，j）只
有三個出口，他們是位置（i+2，j+1）、（i-2，j+1）和（i-1，j-2），如分別走到這些位置，這三個位置又分別會有不同的出口，假定這三個
位置的出口個數分別為4、2、3，則程序就選擇讓馬走向（i-2，j+1）位置。
由于程序采用的是一種貪婪法，整個找解過程是一直向前，沒有回
溯，所以能非常快地找到解。但是，對于某些開始位置，實際上有解，而該算法不能找到解。對于找不到解的情況，程序只要改變8種可能出口的選擇順序，就能找
到解。改變出口選擇順序，就是改變有相同出口時的選擇標準。以下程序考慮到這種情況，引入變量start，用于控制8種可能著法的選擇順序。開始時為0，
當不能找到解時，就讓start增1，重新找解。細節以下程序。
【程序】
# include
int delta_i[ ]={2,1,-1,-2,-2,-1,1,2};
int delta_j[ ]={1,2,2,1,-1,-2,-2,-1};
int board[8][8];
int exitn(int i,int j,int s,int a[ ])
{ int i1,j1,k,count;
for (count=k=0;k<8;k++)
{ i1=i+delta_i[(s+k)%8];
j1=i+delta_j[(s+k)%8];
if (i1>=0&&i1<8&&j1>=0&&j1<8&&board[I1][j1]==0)
a[count++]=(s+k)%8;
}
return count;
}
int next(int i,int j,int s)
{ int m,k,mm,min,a[8],b[8],temp;
m=exitn(i,j,s,a);
if (m==0) return –1;
for (min=9,k=0;k
{ temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);
if (temp
{ min=temp;
kk=a[k];
}
}
return kk;
}
void main()
{ int sx,sy,i,j,step,no,start;
for (sx=0;sx<8;sx++)
for (sy=0;sy<8;sy++)
{ start=0;
do {
for (i=0;i<8;i++)
for (j=0;j<8;j++)
board[j]=0;
board[sx][sy]=1;
I=sx; j=sy;
For (step=2;step<64;step++)
{ if ((no=next(i,j,start))==-1) break;
I+=delta_i[no];
j+=delta_j[no];
board[j]=step;
}
if (step>64) break;
start++;
} while(step<=64)
for (i=0;i<8;i++)
{ for (j=0;j<8;j++)
printf(“%4d”,board[j]);
printf(“\n\n”);
}
scanf(“%*c”);
}
}
七、分治法【問題】 大整數乘法
問題描述：
通常，在分析一個算法的計算復雜性時，都將加法和乘法運算當作是基本運算來處理，即將執行一次加法或乘法運
算所需的計算時間當作一個僅取決于計算機硬件處理速度的常數。
這個假定僅在計算機硬件能對參加運算的整數直接表示和處理時才是合理的。然而，在某些情況下，我們要處理很
大的整數，它無法在計算機硬件能直接表示的范圍內進行處理。若用浮點數來表示它，則只能近似地表示它的大小
，計算結果中的有效數字也受到限制。若要精確地表示大整數并在計算結果中要求精確地得到所有位數上的數字，
就必須用軟件的方法來實現大整數的算術運算。
請設計一個有效的算法，可以進行兩個n位大整數的乘法運算。
設X和Y都是n位的二進制整數，現在要計算它們的乘積XY。我們可以用小學所學的方法來設計一個計算乘積XY的算
法，但是這樣做計算步驟太多，顯得效率較低。如果將每2個1位數的乘法或加法看作一步運算，那么這種方法要作
O(n2)步運算才能求出乘積XY。下面我們用分治法來設計一個更有效的大整數乘積算法。
圖6-3 大整數X和Y的分段
我們將n位的二進制整數X和Y各分為2段，每段的長為n/2位（為簡單起見，假設n是2的冪），如圖6-3所示。
由此，X=A2n/2+B，Y=C2n/2+D。這樣，X和Y的乘積為：
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD （1）
如果按式（1）計算XY，則我們必須進行4次n/2位整數的乘法(AC，AD，BC和BD)，以及3次不超過n位的整數加法（
分別對應于式（1）中的加號），此外還要做2次移位（分別對應于式（1）中乘2n和乘2n/2）。所有這些加法和移
位共用O（n）步運算。設T（n）是2個n位整數相乘所需的運算總數，則由式（1），我們有：
（2）
由此可得T（n）=O（n2）。因此，用（1）式來計算X和Y的乘積并不比小學生的方法更有效。要想改進算法的計算
復雜性，必須減少乘法次數。為此我們把XY寫成另一種形式：
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD （3）
雖然，式（3）看起來比式（1）復雜些，但它僅需做3次n/2位整數的乘法（AC，BD和（A-B）（D-C）），6次加、
減法和2次移位。由此可得：
（4）
用解遞歸方程的套用公式法馬上可得其解為T(n)=O(nlog3)=O(n1.59)。利用式（3），并考慮到X和Y的符號對結果
的影響，我們給出大整數相乘的完整算法MULT如下：
function MULT(X，Y，n); {X和Y為2個小于2n的整數，返回結果為X和Y的乘積XY}
begin
S=SIGN(X)*SIGN(Y); {S為X和Y的符號乘積}
X=ABS(X);
Y=ABS(Y); {X和Y分別取絕對值}
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A=X的左邊n/2位;
B=X的右邊n/2位;
C=Y的左邊n/2位;
D=Y的右邊n/2位;
ml=MULT(A,C,n/2);
m2=MULT(A-B,D-C,n/2);
m3=MULT(B,D,n/2);
S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
上述二進制大整數乘法同樣可應用于十進制大整數的乘法以提高乘法的效率減少乘法次數。
【問題】 最接近點對問題
問題描述：
在應用中，常用諸如點、圓等簡單的幾何對象代表現實世界中的實體。在涉及這些幾何對象的問題中，常需要了解
其鄰域中其他幾何對象的信息。例如，在空中交通控制問題中，若將飛機作為空間中移動的一個點來看待，則具有
最大碰撞危險的2架飛機，就是這個空間中最接近的一對點。這類問題是計算幾何學中研究的基本問題之一。下面
我們著重考慮平面上的最接近點對問題。
最接近點對問題的提法是：給定平面上n個點，找其中的一對點，使得在n個點的所有點對中，該點對的距離最小。
嚴格地說，最接近點對可能多于1對。為了簡單起見，這里只限于找其中的一對。
這個問題很容易理解，似乎也不難解決。我們只要將每一點與其他n-1個點的距離算出，找出達到最小距離的兩個
點即可。然而，這樣做效率太低，需要O(n2)的計算時間。我們能否找到問題的一個O (nlogn)算法。
這個問題顯然滿足分治法的第一個和第二個適用條件，我們考慮將所給的平面上n個點的集合S分成2個子集S1和S2
，每個子集中約有n/2個點，然后在每個子集中遞歸地求其最接近的點對。在這里，一個關鍵的問題是如何實現分
治法中的合并步驟，即由S1和S2的最接近點對，如何求得原集合S中的最接近點對，因為 S1和S2的最接近點對未必
就是S的最接近點對。如果組成S的最接近點對的2個點都在S1中或都在S2中，則問題很容易解決。但是，如果這2個
點分別在 S1和S2中，則對于S1中任一點p，S2中最多只有n/2個點與它構成最接近點對的候選者，仍需做n2/4次計
算和比較才能確定S的最接近點對。因此，依此思路，合并步驟耗時為O(n2)。整個算法所需計算時間T(n)應滿足：
T(n)=2T(n/2)+O(n2)
它的解為T(n)=O(n2)，即與合并步驟的耗時同階，顯示不出比用窮舉的方法好。從解遞歸方程的套用公式法，我們
看到問題出在合并步驟耗時太多。這啟發我們把注意力放在合并步驟上。
為了使問題易于理解和分析，我們先來考慮一維的情形。此時S中的n個點退化為x軸上的n個實數x1、x2、…、xn。
最接近點對即為這n個實數中相差最小的 2個實數。我們顯然可以先將x1、x2、…、xn排好序，然后，用一次線性
掃描就可以找出最接近點對。這種方法主要計算時間花在排序上，因此如在排序算法中所證明的，耗時為O(nlogn)
。然而這種方法無法直接推廣到二維的情形。因此，對這種一維的簡單情形，我們還是嘗試用分治法來求解，并希
望能推廣到二維的情形。
假設我們用x軸上某個點m將S劃分為2個子集S1和S2，使得S1={x∈S | x≤m}；S2={x∈S | x>m}。這樣一來，對于
所有p∈S1和q∈S2有p
遞歸地在S1和S2上找出其最接近點對{p1，p2}和{q1，q2}，并設δ=min{|p1-p2|，|q1-q2|}，S中的最接近點對或
者是{p1，p2}，或者是{q1，q2}，或者是某個{p3，q3}，其中p3∈S1且q3∈S2。如圖1所示。
圖1 一維情形的分治法
我們注意到，如果S的最接近點對是{p3，q3}，即 | p3-q3 | < δ，則p3和q3兩者與m的距離不超過δ，即 | p3-m
| < δ，| q3-m | < δ，也就是說，p3∈(m-δ，m)，q3∈(m，m+δ)。由于在S1中，每個長度為δ的半閉區間至
多包含一個點（否則必有兩點距離小于δ），并且m是 S1和S2的分割點，因此(m-δ，m)中至多包含S中的一個點。
同理，(m，m+δ)中也至多包含S中的一個點。由圖1可以看出，如果(m-δ，m)中有S中的點，則此點就是S1中最大
點。同理，如果(m，m+δ)中有S中的點，則此點就是S2中最小點。因此，我們用線性時間就能找到區間(m-δ，m)
和(m，m+δ)中所有點，即p3和q3。從而我們用線性時間就可以將S1的解和S2的解合并成為S的解。也就是說，按這
種分治策略，合并步可在O(n) 時間內完成。這樣是否就可以得到一個有效的算法了呢？
還有一個問題需要認真考慮，即分割點m的選取，及S1和S2的劃分。選取分割點m的一個基本要求是由此導出集合S
的一個線性分割，即S=S1∪S2 ，S1∩S2=Φ，且S1 {x | x≤m}；S2 {x | x>m}。容易看出，如果選取m=[max（S）
+min（S）]/2，可以滿足線性分割的要求。選取分割點后，再用O(n)時間即可將S劃分成 S1={x∈S |
x≤m}和S2={x∈S | x>m}。然而，這樣選取分割點m，有可能造成劃分出的子集S1和S2的不平衡。例如在最壞情況
下，|S1|=1，|S2|=n-1，由此產生的分治法在最壞情況下所需的計算時間T（n）應滿足遞歸方程：
T（n）=T（n-1）+O（n）
它的解是T（n）=O（n2）。這種效率降低的現象可以通過分治法中“平衡子問題”的方法加以解決。也就是說，我
們可以通過適當選擇分割點m，使S1和 S2中有大致相等個數的點。自然地，我們會想到用S的n個點的坐標的中位數
來作分割點。在選擇算法中介紹的選取中位數的線性時間算法使我們可以在O（n）時間內確定一個平衡的分割點m
。
至此，我們可以設計出一個求一維點集S中最接近點對的距離的算法pair如下。
Float pair（S）;
{ if | S | =2 δ= | x[2]－x[1] | /*x[1..n]存放的是S中n個點的坐標*/
else
{ if ( | S | =1) δ=∞
else
{ m=S中各點的坐標值的中位數;
構造S1和S2，使S1={x∈S | x≤m}，S2={x∈S | x＞m};
δ1=pair(S1);
δ2=pair(S2);
p=max(S1);
q=min(S2);
δ=min(δ1，δ2，q-p);
}
return(δ);
}
由以上的分析可知，該算法的分割步驟和合并步驟總共耗時O(n)。因此，算法耗費的計算時間T(n)滿足遞歸方程：
解此遞歸方程可得T(n)=O(nlogn)。
【問題】循環賽日程表
問題描述：設有n=2k個運動員要進行網球循環賽。現要設計一個滿足以下要求的比賽日程表：
（1）每個選手必須與其他n-1個選手各賽一次；
（2）每個選手一天只能參賽一次；
（3）循環賽在n-1天內結束。
請按此要求將比賽日程表設計成有n行和n-1列的一個表。在表中的第i行，第j列處填入第i個選手在第j天所遇到的
選手。其中1≤i≤n，1≤j≤n-1。
按分治策略，我們可以將所有的選手分為兩半，則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。
遞歸地用這種一分為二的策略對選手進行劃分，直到只剩下兩個選手時，比賽日程表的制定就變得很簡單。這時只
要讓這兩個選手進行比賽就可以了。
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 1 4 3 6 7 8 5
3 4 1 2 7 8 5 6
1 2 3 4 3 2 1 8 5 6 7
1 2 3 4 5 6 7 8 1 4 3 2
1 2 1 4 3 6 5 8 7 2 1 4 3
1 2 3 4 1 2 7 8 5 6 3 2 1 4
2 1 4 3 2 1 8 7 6 5 4 3 2 1
（1） （2） （3）
圖1 2個、4個和8個選手的比賽日程表
圖1 所列出的正方形表（3）是8個選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5
至選手8前3天的比賽日程。據此，將左上角小塊中的所有數字按其相對位置抄到右下角，又將左下角小塊中的所有
數字按其相對位置抄到右上角，這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4 天的比賽日程。依此
思想容易將這個比賽日程表推廣到具有任意多個選手的情形。
八、動態規劃法
經常會遇到復雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地采用把大問題分解成子問
題，并綜合子問題的解導出大問題的解的方法，問題求解耗時會按問題規模呈冪級數增加。
為了節約重復求相同子問題的時間，引入一個數組，不管它們是否對最終解有用，把所有子問題的解存于該數組中
，這就是動態規劃法所采用的基本方法。以下先用實例說明動態規劃方法的使用。
【問題】 求兩字符序列的最長公共字符子序列
問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續）去掉若干個字符（可能一個也不去掉）
后所形成的字符序列。令給定的字符序列X= “x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，
存在X的一個嚴格遞增下標序列，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”
是X的一個子序列。
給定兩個序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長公共
子序列。
如采用列舉A的所有子序列，并一一檢查其是否又是B的子序列，并隨時記錄所發現的子序列，最終求出最長公共子
序列。這種方法因耗時太多而不可取。
考慮最長公共子序列問題如何分解成子問題，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，
z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質：
（1）
如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”
的一個最長公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，
bn-1”的一個最長公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，
bn-2”的一個最長公共子序列。
這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找“a0，a1，…，am-2”和“b0，b
1，…，bm-2”的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出“a0，a1，…，am-2”和“b
0，b1，…，bn-1”的一個最長公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共
子序列，再取兩者中較長者作為A和B的最長公共子序列。
定義c[j]為序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最長公共子序列的長度，計算c[j]可遞歸
地表述如下：
（1）c[j]=0 如果i=0或j=0；
（2）c[j]= c[i-1][j-1]+1 如果I，j>0，且a[i-1]=b[j-1]；
（3）c[j]=max（c[j-1]，c[i-1][j]） 如果I，j>0，且a[i-1]!=b[j-1]。
按此算式可寫出計算兩個序列的最長公共子序列的長度函數。由于c[j]的產生僅依賴于c[i-1][j-1]、c[i-1][j
]和c[j-1]，故可以從c[m][n]開始，跟蹤c[j]的產生過程，逆向構造出最長公共子序列。細節見程序。
# include
# include
# define N 100
char a[N],b[N],str[N];
int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i<=m;i++) c[0]=0;
for (i=0;i<=n;i++) c[0]=0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if (a[i-1]==b[j-1])
c[j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[j-1])
c[j]=c[i-1][j];
else
c[j]=c[j-1];
return c[m][n];
}
char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=’\0’;
while (k>0)
if (c[j]==c[i-1][j]) i--;
else if (c[j]==c[j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}
void main()
{ printf (“Enter two string（<%d）!\n”,N);
scanf(“%s%s”,a,b);
printf(“LCS=%s\n”,build_lcs(str,a,b));
}
1、動態規劃的適用條件
任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態規劃也并不是萬能的。適用動態
規劃的問題必須滿足最優化原理和無后效性。
（1）最優化原理（最優子結構性質）
最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態
而言，余下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原
理又稱其具有最優子結構性質。
圖2
例如圖2中，若路線I和J是A到C的最優路徑，則根據最優化原理，路線J必是從B到C的最優路線。這可用反證法證明
：假設有另一路徑J’是B到C的最優路徑，則A到C的路線取I和J’比I和J更優，矛盾。從而證明J’必是B到C的最優
路徑。
最優化原理是動態規劃的基礎，任何問題，如果失去了最優化原理的支持，就不可能用動態規劃方法計算。根據最
優化原理導出的動態規劃基本方程是解決一切動態規劃問題的基本方法。
（2）無后向性
將各階段按照一定的次序排列好之后，對于某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策
，而只能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無后向性，又稱為無后
效性。
（3）子問題的重疊性
動態規劃算法的關鍵在于解決冗余，這是動態規劃算法的根本目的。動態規劃實質上是一種以空間換時間的技術，
它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間復雜度要大于其它的算法。選擇動態規劃算
法是因為動態規劃算法在空間上可以承受，而搜索算法在時間上卻無法承受，所以我們舍空間而取時間。
所以，能夠用動態規劃解決的問題還有一個顯著特征：子問題的重疊性。這個性質并不是動態規劃適用的必要條件
，但是如果該性質無法滿足，動態規劃算法同其他算法相比就不具備優勢。
2、動態規劃的基本思想
前文主要介紹了動態規劃的一些理論依據，我們將前文所說的具有明顯的階段劃分和狀態轉移方程的動態規劃稱為
標準動態規劃，這種標準動態規劃是在研究多階段決策問題時推導出來的，具有嚴格的數學形式，適合用于理論上
的分析。在實際應用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該
問題可以劃分成規模更小的子問題，并且原問題的最優解中包含了子問題的最優解（即滿足最優子化原理），則可
以考慮用動態規劃解決。
動態規劃的實質是分治思想和解決冗余，因此，動態規劃是一種將問題實例分解為更小的、相似的子問題，并存儲
子問題的解而避免計算重復的子問題，以解決最優化問題的算法策略。
由此可知，動態規劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，并通過求解子
問題產生一個全局最優解。其中貪心法的當前選擇可能要依賴已經作出的所有選擇，但不依賴于有待于做出的選擇
和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的（即不包含公共的
子子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。但不足的是，
如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最優解；如果各子問題是不獨立的，
則分治法要做許多不必要的工作，重復地解公共的子問題。
解決上述問題的辦法是利用動態規劃。該方法主要應用于最優化問題，這類問題會有多種可能的解，每個解都有一
個值，而動態規劃找出其中最優（最大或最小）值的解。若存在若干個取最優值的解的話，它只取其中的一個。在
求解過程中，該方法也是通過求解局部子問題的解達到全局最優解，但與分治法和貪心法不同的是，動態規劃允許
這些子問題不獨立，（亦即各子問題可包含公共的子子問題）也允許其通過自身子問題的解作出選擇，該方法對每
一個子問題只解一次，并將結果保存起來，避免每次碰到時都要重復計算。
因此，動態規劃法所針對的問題有一個顯著的特征，即它所對應的子問題樹中的子問題呈現大量的重復。動態規劃
法的關鍵就在于，對于重復出現的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接
引用，不必重新求解。
3、動態規劃算法的基本步驟
設計一個標準的動態規劃算法，通常可按以下幾個步驟進行：
（1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是
可排序的（即無后向性），否則問題就無法用動態規劃求解。
（2）選擇狀態：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿
足無后效性。
（3）確定決策并寫出狀態轉移方程：之所以把這兩步放在一起，是因為決策和狀態轉移有著天然的聯系，狀態轉
移就是根據上一階段的狀態和決策來導出本階段的狀態。所以，如果我們確定了決策，狀態轉移方程也就寫出來了
。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態之間的關系來確定決策。
（4）寫出規劃方程（包括邊界條件）：動態規劃的基本方程是規劃方程的通用形式化表達式。
一般說來，只要階段、狀態、決策和狀態轉移確定了，這一步還是比較簡單的。動態規劃的主要難點在于理論上的
設計，一旦設計完成，實現部分就會非常簡單。根據動態規劃的基本方程可以直接遞歸計算最優值，但是一般將其
改為遞推計算，實現的大體上的框架如下：
標準動態規劃的基本框架
1. 對fn+1(xn+1)初始化; {邊界條件}
for k:=n downto 1 do
for 每一個xk∈Xk do
for 每一個uk∈Uk(xk) do
begin
5. fk(xk):=一個極值; {∞或－∞}
6. xk+1:=Tk(xk,uk); {狀態轉移方程}
7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}
if t比fk(xk)更優 then fk(xk):=t; {計算fk(xk)的最優值}
end;
9. t:=一個極值; {∞或－∞}
for 每一個x1∈X1 do
11. if f1(x1)比t更優 then t:=f1(x1); {按照10式求出最優指標}
12. 輸出t;
但是，實際應用當中經常不顯式地按照上面步驟設計動態規劃，而是按以下幾個步驟進行：
（1）分析最優解的性質，并刻劃其結構特征。
（2）遞歸地定義最優值。
（3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優值。
（4）根據計算最優值時得到的信息，構造一個最優解。
步驟（1）～（3）是動態規劃算法的基本步驟。在只需要求出最優值的情形，步驟（4）可以省略，若需要求出問
題的一個最優解，則必須執行步驟（4）。此時，在步驟（3）中計算最優值時，通常需記錄更多的信息，以便在步
驟（4）中，根據所記錄的信息，快速地構造出一個最優解。
1、分治法的基本思想
任
何一個可以用計算機求解的問題所需的計算時間都與其規模N有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問
題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接
解決一個規模較大的問題，有時是相當困難的。
分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
如果原問題可分割成k個子問題（1
2、分治法的適用條件
分治法所能解決的問題一般具有以下幾個特征：
（1）該問題的規模縮小到一定的程度就可以容易地解決；
（2）該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；
（3）利用該問題分解出的子問題的解可以合并為該問題的解；
（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
上
述的第一條特征是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；第二條特征是應用分治法的前提，它也是大多數問題可以
滿足的，此特征反映了遞歸思想的應用；第三條特征是關鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三
條特征，則可以考慮貪心法或動態規劃法。第四條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，
此時雖然可用分治法，但一般用動態規劃法較好。
3、分治法的基本步驟
分治法在每一層遞歸上都有三個步驟：
（1）分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
（2）解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
（3）合并：將各個子問題的解合并為原問題的解。
它的一般的算法設計模式如下：
Divide_and_Conquer（P）
if |P|≤n0
then return（ADHOC（P））
將P分解為較小的子問題P1、P2、…、Pk
for i←1 to k
do
yi ← Divide-and-Conquer（Pi） △ 遞歸解決Pi
T ← MERGE（y1，y2，…，yk） △ 合并子問題
Return（T）
其中 |P| 表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC（P）是該分治法中的基本子算法，用于直接解小規模的問題P。因此，當P的規模不超過n0時，直接用算法ADHOC（P）求解。
算法MERGE（y1，y2，…，yk）是該分治法中的合并子算法，用于將P的子問題P1、P2、…、Pk的相應的解y1、y2、…、yk合并為P的解。
根
據分治法的分割原則，原問題應該分為多少個子問題才較適宜？各個子問題的規模應該怎樣才為適當？這些問題很難予以肯定的回答。但人們從大量實踐中發現，在
用分治法設計算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取k=2。這種使
子問題規模大致相等的做法是出自一種平衡子問題的思想，它幾乎總是比子問題規模不等的做法要好。
分治法的合并步驟是算法的關鍵所在。有些問題的合并方法比較明顯，有些問題合并方法比較復雜，或者是有多種合并方案；或者是合并方案不明顯。究竟應該怎樣合并，沒有統一的模式，需要具體問題具體分析。
【問題】 凸多邊形的最優三角剖分問題
問題描述：多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成
多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點稱為多邊形的頂點。若多邊形的邊之間除了連接
頂點外沒有別的公共點，則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分：被包圍在多邊形內的
所有點構成了多邊形的內部；多邊形本身構成多邊形的邊界；而平面上其余的點構成了多邊形的外部。當一個簡單
多邊形及其內部構成一個閉凸集時，稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內部的任意兩點所連
成的直線段上所有的點均在該凸多邊形的內部或邊界上。
通常，用多邊形頂點的逆時針序列來表示一個凸多邊形，即P=表示具有n條邊v0v1，v1v2，…，vn-1vn的一個凸多
邊形，其中，約定v0=vn 。
若vi與vj是多邊形上不相鄰的兩個頂點，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成凸的兩個子多邊形和
。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。圖1是一個凸多邊形的兩個不同的三角
剖分。
(a) (b)
圖1 一個凸多邊形的2個不同的三角剖分
在凸多邊形P的一個三角剖分T中，各弦互不相交且弦數已達到最大，即P的任一不在T中的弦必與T中某一弦相交。
在一個有n個頂點的凸多邊形的三角刮分中，恰好有n-3條弦和n-2個三角形。
凸多邊形最優三角剖分的問題是：給定一個凸多邊形P=以及定義在由多邊形的邊和弦組成的三角形上的權函數ω。
要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應的權即剖分中諸三角形上的權之和為最小。
可以定義三角形上各種各樣的權函數ω。例如：定義ω(△vivjvk)=| vivj |+| vivk |+| vkvj |，其中，| vivj
|是點vi到vj的歐氏距離。相應于此權函數的最優三角剖分即為最小弦長三角剖分。
（1）最優子結構性質
凸多邊形的最優三角剖分問題有最優子結構性質。事實上，若凸（n+1）邊形P=的一個最優三角剖分T包含三角形v0
vkvn，1≤k≤n-1，則T的權為3個部分權的和，即三角形v0vkvn的權，子多邊形 的權和的權之和。可以斷言由T所
確定的這兩個子多邊形的三角剖分也是最優的，因為若有或的更小權的三角剖分，將會導致T不是最優三角剖分的
矛盾。
（2）最優三角剖分對應的權的遞歸結構
首先，定義t[i，j]（1≤i的最優三角剖分所對應的權值，即最優值。為方便起見，設退化的多邊形具有權值0。據
此定義，要計算的凸（n+1）邊多邊形P對應的權的最優值為t[1，n]。
t[i，j]的值可以利用最優子結構性質遞歸地計算。由于退化的2頂點多邊形的權值為0，所以t[i，i]=0，i=1，2，
…，n 。當j一i≥1時，子多邊形至少有3個頂點。由最優于結構性質，t[i，j]的值應為t[i，k]的值加上t [k+1，
j]的值，再加上△vi-1vkvj的權值，并在i≤k≤j-1的范圍內取最小。由此，t[i，j]可遞歸地定義為：
（3）計算最優值
下面描述的計算凸（n+1）邊形P=的三角剖分最優權值的動態規劃算法MINIMUM_WEIGHT，輸入是凸多邊形P=的權函
數ω，輸出是最優值t[i，j]和使得t[i，k]+t[k+1，j]+ω（△vi-1vkvj）達到最優的位置（k=）s[i，j]，1≤i≤
j≤n 。
Procedure MINIMUM_WEIGHT(P，w)；
Begin
n=length[p]-1;
for i=1 to n do t[i,i]:=0;
for ll=2 to n do
for i=1 to n-ll+1 do
begin
j=i+ll-1;
t[i,j]=∞;
for k=i to j-1 do
begin
q=t[i,k]+t[k+1,j]+ω(△vi-1vkvj);
if q
begin
t[i,j]=q;
s[i,j]=k;
end;
end;
end;
return(t,s);
end;
算法MINIMUM_WEIGHT_占用θ(n2)空間，耗時θ(n3)。
（4）構造最優三角剖分
如我們所看到的，對于任意的1≤i≤j≤n ，算法MINIMUM_WEIGHT在計算每一個子多邊形的最優三角剖分所對應的
權值t[i，j]的同時，還在 s[i，j]中記錄了此最優三角剖分中與邊（或弦）vi-1vj構成的三角形的第三個頂點的
位置。因此，利用最優子結構性質并借助于s[i，j]， 1≤i≤j≤n ，凸（n+l）邊形P=的最優三角剖分可容易地在
Ο(n)時間內構造出來。
習題：
1、汽車加油問題：
設有路程長度為L公里的公路上，分布著m個加油站，它們的位置分別為p（i=1，2，……，m），而汽車油箱加
滿油后（油箱最多可以加油k升），可以行駛n公里。設計一個方案，使汽車經過此公路的加油次數盡量少（汽車出
發時是加滿油的）。
2、最短路徑：
設有一個網絡，要求從某個頂點出發到其他頂點的最短路徑
3、跳馬問題：
在8*8方格的棋盤上，從任意指定的方格出發，為馬尋找一條走遍棋盤每一格并且只經過一次的一條路徑。
4、二叉樹的遍歷
5、背包問題
6、用分治法實現兩個大整數相乘
7、設x1，x2，…，xn是直線上的n個點，若要用單位長度的閉區間去覆蓋這n個點，至少需要多少個這樣的單位閉區間？
8、用關系“＜”和“＝”將3個數A、B和C依次排列時，有13種不同的序關系：
A＝B＝C，A＝B＜C，A＜B＝C，A＜B＜C，A＜C＜B，A＝C＜B，B＜A＝C，
B＜A＜C，B＜C＜A，B＝C＜A，C＜A＝B，C＜A＜B，C＜A＜B。
若要將n個數依序進行排列，試設計一個動態規劃算法，計算出有多少鐘不同的序關系。
9、有一種單人玩的游戲：設有n(2<=n<=200)堆薄片，各堆順序用0至 n-1編號，極端情況，有的堆可能沒有薄片。
在游戲過程中，一次移動只能取某堆上的若干張薄片，移到該堆的相鄰堆上。如指定
I堆k張 k 移到I-1(I>0)堆，和將k 張薄片移至I+1(I
游戲的目標是對給定的堆數，和各堆上的薄片數，按上述規則移動薄片，最終使 各堆的薄片數相同。為了使移動
次數較少些，移動哪一堆薄片，和移多少薄片先作以下估算：
設
ci:I堆的薄片數(0<=I<=ci<=200);
v：每堆 的平均薄片數；
ai:I堆的相鄰堆可以從I堆得到的薄片數。
估算方法如下：
v=c0+a1-a0 a1=v+a0-c0
v=c1+a0+a2-2a1 a2=v+2a1-a0-c1
…….. ……….
V=ci+ai-1+ai+1-2aI ai+1=v+2ai-ai-1-ci
這里并不希望準確地求出A0 至an-1，而是作以下處理：若令 a0 為0，能按上述算式計算出 A1至 an-1。程序找出
a 中的最小值，并讓全部a值減去這最小值，使每堆移去的薄片數大于等于0。
實際操作采用以下貪心策略：
（1）每次從第一堆出發順序搜索每一堆，若發現可從 I堆移走薄片，就完成一次移動。即， I堆的相鄰堆從 I堆
取走 ai片薄片。可從I 堆移薄片到相鄰堆取于 I堆薄片數：若I 堆是處于兩端位置( I=0 I=n-1), 要求 ci>=ai
；若 I堆是中間堆，則要求ci>=2ai。
（2）因在ai>0的所有堆中，薄片數最多的堆 在平分過程中被它的相鄰堆取走的薄片數也最多。在用策略（1）搜
索移動時，當發生沒有滿足條件（1）的可移走薄片的堆時，采用本策略，讓在ai>0的所有堆中，薄片數最多的堆
被它的相鄰堆取走它的全部薄片。