算法與程序設計中,用回溯法求解符號三角形問題,解析過程是怎樣的?

熱心網友

運用回溯法解題通常包含以下步驟：（1）、針對所給問題，定義問題的解空間；（2）、確定易于搜索的解空間結構(如子集樹、排列數或圖）；（3）、以深度優先的方式搜索解空間，并且在搜索過程中用剪枝函數（如約束函數、限界函數）避免無效搜索。（4）、由于回溯法是對解空間的深度優先搜索，因此在一般情況下可用遞歸函數來實現回溯法。 對于符號三角形問題，用n元組x[1：n]表示符號三角形的第一行的n個符號。當x[i]=1時，表示符號三角形的第一行的第i個符號為“+”號；當x[i]=0時，表示符號三角形的第一行的第i個符號為“-”號；1 ≤ i≤ n。由于x[i]是二值的，所以在用回溯法解符號三角形問題時，可以用一棵完全二叉樹來表示其解空間。在符號三角形的第一行的前i個符號x[1：i ]確定后，就確定了一個由i*（i+1）/2個符號組成的符號三角形。下一步確定了x[i+1]的值后，只要在前面已確定的符號三角形的右邊加一條邊，就可以擴展為x[1：i+1]所相應的符號三角形。最終由x[1：n]所確定的符號三角形中包含的“+”號個數與“-”號個數同為n*（n+1）/4。因此在回溯搜索過程中可用當前符號三角形所包含的“+”號個數與“-”號個數均不超過n*（n+1）/4作為可行性約束，用于剪去不滿足約束的子樹。對于給定的n，當n*（n+1）/2為奇數時，顯然不存在所包含的“+”號個數與“-”號個數相同的符號三角形。 以上就是解析過程，若要程序代碼，需要提高懸賞分喔，嘿嘿~ 。