august 发表于 2009-2-5 17:07:48

对回溯法提问

看严蔚敏书上树的那章，最后提到了一下回溯法，看完不太懂，不知有否简单一点的完整实现的程序，可以参考一下呢(最好是求幂集的)？谢了。

Zelsazgh 发表于 2009-2-8 22:37:28

关于回溯算法,最简单的应该就是8皇后问题了吧,就是指在8*8的国际象棋盘上摆8个皇后,且符合每个皇后的横,竖,斜线不存在其它皇后
#include <stdio.h>
#define MAX 8
int kpos;
int place(int count)
{
    int i;
    for(i=0;i<count;i++)
    {
        if(abs(i-kpos)==abs(count-kpos || kpos==kpos)
            return 0;
    }
    return 1;
}
int main()
{
    
    int kcount=0;
    while(kcount<MAX)
    {
        kpos++;
        for(kpos;kpos<=8;kpos++)
      {
            if(placs(kcount))
            {
                kcount++;
                break;
            }
      }
      if(kpos>MAX)
    {   
                kpos=0;
      kcount--;
      }
    }
     int i;
     for(i=0;i<MAX;i++)
            printf("No.%d:%d",i,kpos);
    return 0;
}

august 发表于 2009-2-8 23:26:04

怎么感觉好像只是很单纯的递归？

Zelsazgh 发表于 2009-2-9 10:40:09

呃,递归与回溯的区别不大,要说区别的话,递归是不会有回退再选择其它路径的
页: [1]
查看完整版本: 对回溯法提问