转自我的CSDNåšå®¢ï¼šÂ http://blog.csdn.net/njdragonfly
8皇åŽé—®é¢˜å’Œç”±ä»–推广得到的N皇åŽé—®é¢˜æ¥æºäºŽå›½é™…è±¡æ£‹çš„çŽ©æ³•ï¼Œå› ä¸ºçš‡åŽæ‰€åœ¨çš„ä½ç½®å¯ä»¥çºµå‘ã€æ¨ªå‘ã€ä¸¤ä¸ªæ–œå‘四个方å‘çš„â€œæ•æ‰â€ï¼Œæ‰€ä»¥8皇åŽé—®é¢˜å°±æ˜¯è¦æ±‚如何布置8个皇åŽåœ¨8*8çš„æ£‹ç›˜ä¸Šè€Œä½¿ä»–ä»¬äº’ç›¸æ— æ³•â€œæ•æ‰â€ã€‚也就是说ä¸å˜åœ¨ä¸¤ä¸ªçš‡åŽåŒè¡Œæˆ–åŒåˆ—,或在åŒä¸€æ–œçº¿ä¸Šã€‚而N皇åŽé—®é¢˜å°±æ˜¯å¦‚何布置N个皇åŽåœ¨N*N棋盘里使ä¸å˜åœ¨ä¸¤ä¸ªçš‡åŽåœ¨åŒè¡ŒåŒåˆ—å’ŒåŒä¸€æ–œçº¿ä¸Šã€‚å› ä¸º8皇åŽé—®é¢˜å¯ä»¥å½’为N皇åŽé—®é¢˜ï¼Œæ‰€ä»¥ä¸‹é¢æŒ‰ç…§N皇åŽé—®é¢˜æ¥è¿›è¡Œè®¨è®ºã€‚
解决N皇åŽé—®é¢˜çš„æœ€å¥½æœ€è‘—å的算法就是回溯法。在算法设计的基本方法ä¸ï¼Œå›žæº¯æ³•是最一般的方法之一。在那些涉åŠåˆ°å¯»æ‰¾ä¸€ç»„解的问题或者求满足æŸäº›çº¦æŸæ¡ä»¶çš„æœ€ä¼˜è§£çš„问题ä¸ï¼Œæœ‰è®¸å¤šå¯ä»¥ç”¨å›žæº¯æ³•æ¥æ±‚解。回溯法是一个既带有系统性åˆå¸¦æœ‰è·³è·ƒæ€§çš„çš„æœç´¢ç®—法。它在包å«é—®é¢˜çš„æ‰€æœ‰è§£çš„è§£ç©ºé—´æ ‘ä¸ï¼ŒæŒ‰ç…§æ·±åº¦ä¼˜å…ˆçš„ç–ç•¥ï¼Œä»Žæ ¹ç»“ç‚¹å‡ºå‘æœç´¢è§£ç©ºé—´æ ‘。算法æœç´¢è‡³è§£ç©ºé—´æ ‘的任一结点时,总是先判æ–该结点是å¦è‚¯å®šä¸åŒ…å«é—®é¢˜çš„解。如果肯定ä¸åŒ…å«ï¼Œåˆ™è·³è¿‡å¯¹ä»¥è¯¥ç»“ç‚¹ä¸ºæ ¹çš„åæ ‘的系统æœç´¢ï¼Œé€å±‚å‘其祖先结点回溯。å¦åˆ™ï¼Œè¿›å…¥è¯¥åæ ‘ï¼Œç»§ç»æŒ‰æ·±åº¦ä¼˜å…ˆçš„ç–略进行æœç´¢ã€‚å›žæº¯æ³•åœ¨ç”¨æ¥æ±‚问题的所有解时,è¦å›žæº¯åˆ°æ ¹ï¼Œä¸”æ ¹ç»“ç‚¹çš„æ‰€æœ‰åæ ‘都已被æœç´¢éæ‰ç»“æŸã€‚è€Œå›žæº¯æ³•åœ¨ç”¨æ¥æ±‚问题的任一解时,åªè¦æœç´¢åˆ°é—®é¢˜çš„一个解就å¯ä»¥ç»“æŸã€‚è¿™ç§ä»¥æ·±åº¦ä¼˜å…ˆçš„æ–¹å¼ç³»ç»Ÿåœ°æœç´¢é—®é¢˜çš„è§£çš„ç®—æ³•ç§°ä¸ºå›žæº¯æ³•ï¼Œå®ƒé€‚ç”¨äºŽè§£ä¸€äº›ç»„åˆæ•°è¾ƒå¤§çš„问题。
å›žæº¯æ³•çš„åŸºæœ¬æ€æƒ³ï¼šç¡®å®šäº†è§£ç©ºé—´çš„组织结构åŽï¼Œå›žæº¯æ³•å°±ä»Žå¼€å§‹ç»“ç‚¹ï¼ˆæ ¹ç»“ç‚¹ï¼‰å‡ºå‘ï¼Œä»¥æ·±åº¦ä¼˜å…ˆçš„æ–¹å¼æœç´¢æ•´ä¸ªè§£ç©ºé—´ã€‚这个开始结点就æˆä¸ºä¸€ä¸ªæ´»ç»“ç‚¹ï¼ŒåŒæ—¶ä¹Ÿæˆä¸ºå½“å‰çš„æ‰©å±•结点。在当å‰çš„æ‰©å±•结点处,æœç´¢å‘纵深方å‘移至一个新结点。这个新结点就æˆä¸ºä¸€ä¸ªæ–°çš„æ´»ç»“点,并æˆä¸ºå½“剿‰©å±•结点。如果在当å‰çš„æ‰©å±•结点处ä¸èƒ½å†å‘纵深方å‘ç§»åŠ¨ï¼Œåˆ™å½“å‰æ‰©å±•结点就æˆä¸ºæ»ç»“点。æ¢å¥è¯è¯´ï¼Œè¿™ä¸ªç»“点ä¸å†æ˜¯ä¸€ä¸ªæ´»ç»“ç‚¹ã€‚æ¤æ—¶ï¼Œåº”往回移动(回溯)至最近的一个活结点处,并使这个活结点æˆä¸ºå½“å‰çš„æ‰©å±•结点。回溯法å³ä»¥è¿™ç§å·¥ä½œæ–¹å¼é€’å½’åœ°åœ¨è§£ç©ºé—´ä¸æœç´¢ï¼Œç›´è‡³æ‰¾åˆ°æ‰€è¦æ±‚的解或解空间ä¸å·²æ²¡æœ‰æ´»ç»“点时为æ¢ã€‚
è¿ç”¨å›žæº¯æ³•解题通常包å«ä»¥ä¸‹ä¸‰ä¸ªæ¥éª¤ï¼š
(1)针对所给问题,定义问题的解空间;
(2)确定易于æœç´¢çš„解空间结构;
(3ï¼‰ä»¥æ·±åº¦ä¼˜å…ˆçš„æ–¹å¼æœç´¢è§£ç©ºé—´ï¼Œå¹¶ä¸”在æœç´¢è¿‡ç¨‹ä¸ç”¨å‰ªæžå‡½æ•°é¿å…æ— æ•ˆæœç´¢ï¼›
一般回溯法å¯ç”¨é€’å½’æ¥å®žçŽ°ï¼Œä¸‹é¢æ˜¯ä»Žç½‘上找æ¥çš„一个éžå¸¸å…¸åž‹çš„递归程åºç»“构。
procedure try(i:integer); var begin if i>n then 输出结果 else for j:=下界 to 上界 do begin x[i]:=h[j]; if å¯è¡Œ{满足é™ç•Œå‡½æ•°å’Œçº¦æŸæ¡ä»¶} then begin 置值;try(i+1); end; end; end;
说明:
i是递归深度;
n是深度控制,å³è§£ç©ºé—´æ ‘的的高度;
å¯è¡Œæ€§åˆ¤æ–有两方é¢çš„å†…å®¹ï¼šä¸æ»¡çº¦æŸæ¡ä»¶åˆ™å‰ªåŽ»ç›¸åº”åæ ‘;若é™ç•Œå‡½æ•°è¶Šç•Œï¼Œä¹Ÿå‰ªåŽ»ç›¸åº”åæ ‘ï¼›ä¸¤è€…å‡æ»¡è¶³åˆ™è¿›å…¥ä¸‹ä¸€å±‚,直到最åŽçš„å¶å输出结果。
回到N皇åŽé—®é¢˜çš„解决æ¥ï¼Œçœ‹çœ‹å¦‚何用回溯法解。首先找出解空间:给棋盘的行和列都编上1到Nçš„å·ç ,皇åŽä¹Ÿç»™ç¼–上1到Nçš„å·ç 。由于一个皇åŽåº”在ä¸åŒçš„行上,为ä¸å¤±ä¸€èˆ¬æ€§ï¼Œå¯ä»¥å‡å®šç¬¬i个皇åŽå°†æ”¾åœ¨ç¬¬i行上的æŸåˆ—ã€‚å› æ¤N皇åŽé—®é¢˜çš„解空间å¯ä»¥ç”¨ä¸€ä¸ªN元组(X1,X2,…..Xn)æ¥è¡¨ç¤ºï¼Œå…¶ä¸Xi是放置皇åŽi所在的列å·ã€‚è¿™æ„å‘³ç€æ‰€æœ‰çš„解都是N元组(1,2,3,…….,N)的置æ¢ã€‚解空间大å°ä¸ºNï¼ã€‚å…¶æ¬¡æˆ‘ä»¬çœ‹çº¦æŸæ¡ä»¶ï¼šå› 为解空间已ç»ç»™æˆ‘们排除了ä¸åœ¨åŒä¸€è¡Œï¼ˆå› 为æ¯ä¸ªçš‡åŽåˆ†åˆ«å·²ç»å¯¹åº”ä¸åŒçš„行å·ï¼‰çš„çº¦æŸæ¡ä»¶ã€‚我们è¦åˆ¤æ–的是ä¸åœ¨åŒä¸€åˆ—å’Œä¸åœ¨åŒä¸€æ–œçº¿çš„约æŸã€‚å› ä¸ºXiè¡¨ç¤ºçš‡åŽæ‰€åœ¨çš„列å·ï¼Œæ‰€ä»¥å¦‚æžœå˜åœ¨X(k)=X(i)那么肯定å˜åœ¨ç¬¬k个皇åŽå’Œç¬¬i个皇åŽåŒåˆ—。所以ä¸åŒåˆ—的判段æ¡ä»¶æ˜¯X(k)ï¼=X(i),1<k<i 。åˆå› 为åŒä¸€æ–œçº¿çš„ç‰¹å¾æ˜¯è¦ä¹ˆè¡Œå·å’Œåˆ—å·ä¹‹å’Œä¸å˜ï¼ˆå³é«˜å·¦ä½Žï¼‰è¦ä¹ˆæ˜¯è¡Œå·å’Œåˆ—å·åªå·®ç›¸ç‰ï¼ˆå·¦é«˜å³ä½Žï¼‰ï¼Œæ‰€ä»¥åŒæ–œçº¿çš„åˆ¤æ–æ¡ä»¶æ˜¯ i+X(i)= k+X(k) 或 i-X(i) =k-X(k),两å¼åˆå¹¶å¾— |X(i)-X(k)|=|i-k| 。
编程基本æ€è·¯ï¼šX(j)表示一个解的空间,j表示行数,里é¢çš„值表示å¯ä»¥æ”¾ç½®åœ¨çš„åˆ—æ•°ï¼ŒæŠ½è±¡çº¦æŸæ¡ä»¶å¾—到能放置一个皇åŽçš„çº¦æŸæ¡ä»¶(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法,当å¯ä»¥æ”¾ç½®çš‡åŽæ—¶å°±ç»§ç»åˆ°ä¸‹ä¸€è¡Œï¼Œä¸è¡Œçš„è¯å°±è¿”å›žåˆ°ç¬¬ä¸€è¡Œï¼Œé‡æ–°æ£€éªŒè¦æ”¾çš„列数,如æ¤åå¤ï¼Œç›´åˆ°å°†æ‰€æœ‰è§£è§£å‡ºã€‚
#include <iostream.h> #include <math.h> /*检查å¯ä¸å¯ä»¥æ”¾ç½®ä¸€ä¸ªæ–°çš„皇åŽ*/ bool place(int k, int *X) { int i; i=1; while(i<k) { if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k))) return false; i++; } return true; } /*求解问题的所有解*/ void Nqueens(int n,int *X) { int k; X[1]=0;k=1; while(k>0) { X[k]=X[k]+1; //䏿–的在解空间里从å°åˆ°å¤§çš„试探 while((X[k]<=n)&&(!place(k, X))) X[k]=X[k]+1; //ä¸ç¬¦åˆæ¡ä»¶çš„马上å†å–解空间的下一个值æ¥è¯•探。 if(X[k]<=n) //找到了一个ä½ç½®ï¼Œè€Œä¸”æ˜¯åˆæ³•çš„ if(k==n) //æ˜¯ä¸æ˜¯æœ€åŽä¸€ä¸ªçš‡åŽï¼Œè‹¥æ˜¯åˆ™å¾—出一个完整解 { for(int i=1;i<=n;i++) cout<<X[i]<<" "; cout<<"/n"; } else //è‹¥ä¸æ˜¯æœ€åŽä¸€ä¸ªçš‡åŽï¼Œåˆ™ç»™ä¸‹ä¸€ä¸ªçš‡åŽæ‰¾ä½ç½® { k=k+1; X[k]=0; } else k=k-1; //è‹¥æ˜¯æ‰¾äº†å…¨éƒ¨çš„åˆ—éƒ½æ— æ³•æ”¾ç½®æŸä¸ªçš‡åŽï¼Œåˆ™å›žæº¯åˆ°ä¸Šä¸€ä¸ªk的情况,让上一个kå†å¾€ä¸‹è¯• } } /*主函数*/ void main() { cout<<"|--------------N皇åŽé—®é¢˜--------------|"<<endl; cout<<"|-------------------------------------|"<<endl<<endl; int n; int *X; int i; while(i) { cout<<"请输入皇åŽçš„个数:"; cin>>n; X=new int[n]; cout<<"问题的解有:"<<endl; Nqueens(n,X); cout<<"Press<1> to run again"<<endl; cout<<"Press<0> to exit"<<endl; cin>>i; }