C++程序設(shè)計例解(07)

07. 有2*n個盒子排成一行，其中有兩個相鄰的空盒，有n-1個盒子有符號'A'，有n-1個盒子有符號'B'。例如，n=5，并有初始配置如下：
    A B B A . . A B A B
    試編制程序，將輸入的盒子排列狀態(tài)按以下交換規(guī)則將全部‘A'放到全部‘B'的左邊，不管相鄰兩空盒的位置。交換規(guī)則是任意兩個非空相鄰盒子的內(nèi)容可移入兩個空盒中，但移動時不得變更兩符號的前后次序。編寫程序輸入初始配置后，找出達到目標要求的最少交換次數(shù)的方案。
    解：
    從一種盒子排列出發(fā)，將其中兩個非空相鄰盒子中的內(nèi)容移入空盒的每一種移動，會使盒子產(chǎn)生新的排列狀態(tài)，采用試探法窮舉所有可能的移動找問題的解。首先將盒子初始排列存入移動步聚表，然后是試探和回溯循環(huán)。循環(huán)工作內(nèi)容有：檢查當前排列，若當前排列是要求的最終狀態(tài)，則將達到該狀態(tài)的移動步聚保存，并回溯去找更少移動步數(shù)的解。在試探超 過限定的深度或當前狀態(tài)的所有可能移動都已試探窮盡情況下回溯；否則對當前狀態(tài)取其當前移動方法產(chǎn)生新的后繼狀態(tài)存入移動步聚表，并繼續(xù)向前試探。為能從某種排列出發(fā)，通過移動產(chǎn)生更接近目標要求的排列，對移動方法的選取作如下規(guī)定：
    。掠過無意義的來回移動；
    。不把兩個相鄰的同為符號‘A'的盒子向后移；
    。不把兩個相鄰的同為符號‘B'的盒子向前移；
    。不把兩個盒子移入到這樣的位置，移入后其首尾沒有一個與相鄰的盒子相同。
    試探回溯找解算法如下：
    算法---試探回溯找解
    {
    輸入初始排列；
    初始狀態(tài)存入移動步聚表；
    設(shè)置其它初值；
    d=0; /*當前試探深，或當前狀態(tài)位置*/
    do
    {
    if(當前狀態(tài)為盒子排列的終態(tài))
    {
    保存解；
    記錄當前解的試探深度；
    回溯；
    if(取盡所有可能的解)break;
    }
    if(試探深度超過設(shè)定值，或取盡當前狀態(tài)的所有選擇)
    {
    回溯；
    if(取盡所有可能的選擇)break;
    }
    else
    {
    求新狀態(tài)的空盒位置；
    取當前狀態(tài)的移動方法和當前狀態(tài)；
    設(shè)定當前狀態(tài)的下一個移動方法；
    掠過各種不希望的方法；
    生成新狀態(tài)；