算法系列总结:回溯算法(解火力网问题)

标签: 算法 系列 回溯 | 发表时间:2011-05-20 21:33 | 作者:殷伟雄(Zealot Yin) 团子小囧
出处:http://www.cnblogs.com/

理论辅助:

回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为:

1、定义一个解空间,它包含问题的解。

2、利用适于搜索的方法组织解空间。

3、利用深度优先法搜索解空间。

4、利用限界函数避免移动到不可能产生解的子空间。

问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。

 

还是那个基调,不喜欢纯理论的东西,喜欢使用例子来讲诉理论,在算法系列总结:动态规划(解公司外包成本问题) 的那一节里面 我们举得是经典的0-1背包问题,在回溯算法里面也有一些很经典的问题,当然,动态规划的0-1背包问题其实也可以使用回溯算法来解。在诸如此类似的求最优解的问题中,大部分其实都可以用回溯法来解决,可以认为回溯算法一个”通用解题法“,这是由他试探性的行为决定的,就好比求一个最优解,我可能没有很好的概念知道怎么做会更快的求出这个最优解,但是我可以尝试所有的方法,先试探性的尝试每一个组合,看看到底通不通,如果不通,则折回去,由最近的一个节点继续向前尝试其他的组合,如此反复。这样所有解都出来了,在做一下比较,能求不出最优解吗?

例子先行,现在我们来看看经典的N后问题

问题描述:在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规矩,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n格的棋盘上方置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。我们需要求的是可放置的总数。

image

基本思路:   用n元组x[1;n]表示n后问题的解。其中,x[i]表示皇后i放置在棋盘的第i行的第x[i]列。由于不容许将2个皇后放在同一列上,所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题,这一隐约束条件可以化成显约束的形式。如果将n*n 格的棋盘看做二维方阵,其行号从上到下,列号从左到右依次编号为1,2,...n。从棋盘左上角到右下角的主对角线及其平行线(即斜率为-1的各斜线)上,2个下标值的差(行号-列号)值相等。同理,斜率为+1的每条斜线上,2个下标值的和(行号+列号)值相等。因此,若2个皇后放置的位置分别是(i,j)和(k,l),且 i-j = k -l 或 i+j = k+l,则说明这2个皇后处于同一斜线上。以上2个方程分别等价于i-k = j-l 和 i-k =l-j。由此可知,只要|i-k|=|l-j|成立,就表明2个皇后位于同一条斜线上。

代码:

View Code
#include <stdio.h> 
#include
<math.h>
 
#include
<stdlib.h>
 
static int n,x[1000
]; 
static    long
sum; 
int Place(int
k) 

for(int j=1;j <k; j++

   
if((abs(k-j) == abs(x[j]-x[k]))||(x[j]==x[k])) return 0

    
return 1

  }

void Backtrak(int
t) 

  
if(t>n) sum++

  
else
 
      
for(int i=1; i <= n; i++

       { 
            x[t]
=
i; 
           
if(Place(t))Backtrak(t+1
); 
       } 
}

int
main() 

   
int
nn; 
   
while(scanf("%d",&nn)!=
EOF) 
    { 
    n
=
nn; 
    sum
=0

   
for(int i=0;i<=n;i++

    x[i]
=0

    Backtrak(
1
); 
    printf(
"%d\n"
,sum); 

}

这段代码有必要解释一下,Place(int)即尝试看是否可以,如果不可以则回退到t+1层,再尝试其他的组合。

这里也道出了回溯算法的核心思想:但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择


算法实践:

问题描述:在一个n*n的网格里,每个网格可能为“墙壁”(用‘X’表示)和“街道”(用‘.’表示)。现在在街道放置碉堡,每个碉堡可以向上下左右四个方向开火,子弹射程无限远。墙壁可以阻挡子弹。问最多能放置多少个碉堡,使它们彼此不会互相摧毁。

如下面四张图,墙壁用黑正方形表示,街道用空白正方形表示,圆球就代表碉堡。1,2,3是正确的,4,5是错误的。以为4,5里面在某一行或者某一列有两个碉堡,这样他们就会互相攻击了。意思明白了吗?可能我的表达很不清晰,呵呵….

输入输出示例
Sample input:

4
       ——————输入的n值 
.X.. 

.... 

XX..

.... 

2
 
XX 
.X 
3
 
.X. 
X.X 
.X. 
4
 
.... 
.... 
.... 
....

Sample output:

5
 
1
 
5
 
4 

初拿到这个问题,你会不会想到回溯算法呢?有人说遍历墙的位置,然后再墙的上下左右四个格子放置碉堡会得到最优解,这个我没有验证过,细细的用笔画了画,好像是这么回事,但是很多时候要知道最优解用什么方法是很难发现的,利用通用解题方法回溯法,我们可以在一片茫然的时候开始我们的编程

首先我们来分析一下这个问题:使用回溯法,我们尝试每一种可能放置的情况,然后进行判断是否满足要求,若不满足,尝试放到下一个单元格,如此反复,最终,我们将所有可能放置的情况全部遍历出来了,连所有情况都出来了,难不成还找不到最优解吗?哈哈。。说做就做…

View Code
    #include <stdio.h>
     
char map[4][4];
     
int best,n;
     
int canput(int row, int col)
     {
        
int i;
        
for (i = row - 1; i >= 0; i--
        {
          
if (map[i][col] == 'o'return 0
          
if (map[i][col] == 'x'break;
        }
        
for (i = col - 1; i >= 0; i--)
        {
          
if (map[row][i] == 'o'return 0
          
if (map[row][i] == 'x'break;
        }
        
return 1;
     }
 
     
void solve(int k,int tot)
     {
        
int x,y;
        
if(k==n*n)
        {
          
if(tot>best) 
          {
           best
=tot;   return;
          }
        }
        
else
        {
          x
=k/n;
          y
=k%n;
          
if((map[x][y]=='.'&& (canput(x,y) ) )
          {
            map[x][y]
='o';
            solve(k
+1,tot+1);
            map[x][y]
='.';
          }
         solve(k
+1,tot);
         }
      }
 
     
int main()
     {
        
int i,j;
        scanf(
"%d",&n);
        
while(n>0)
        {
          
for(i=0;i< n;i++)
             
for(j=0;j< n;j++)
                 scanf(
"%1s",&map[i][j]); 
          best
=0;
          solve(
0,0);
          printf(
"%d\n",best);
          n
=0;                             
          scanf(
"%d",&n);
        }
        
return 0;
 }

 

对上面的代码做一下点解释,canput是做检验的,检验放在某个地点到底行不行得通,solve才是真正进行递归回溯的函数。。

作者: 殷伟雄(Zealot Yin) 发表于 2011-05-20 21:33 原文链接

评论: 4 查看评论 发表评论


最新新闻:
· Groupon与Loopt合作 向手机用户发送折扣信息(2011-05-21 14:16)
· 胡延平:互联网将会变成一个大的社会化网络(2011-05-21 14:14)
· 互联网就是一块“云”(2011-05-21 13:53)
· 有趣的 Kindle 广告互动(2011-05-21 13:26)
· 谷歌490万美元收购Modu专利(2011-05-21 13:21)

编辑推荐:码斗士的修炼之路 -- 如何保持并提升战斗力

网站导航:博客园首页  我的园子  新闻  闪存  小组  博问  知识库

相关 [算法 系列 回溯] 推荐:

算法系列总结:回溯算法(解火力网问题)

- 团子小囧 - 博客园-首页原创精华区
回溯算法也叫试探法,它是一种系统地搜索问题的解的方法. 回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试. 用回溯算法解决问题的一般步骤为:. 1、定义一个解空间,它包含问题的解. 2、利用适于搜索的方法组织解空间. 3、利用深度优先法搜索解空间. 4、利用限界函数避免移动到不可能产生解的子空间.

五大常用算法:分治、动态规划、贪心、回溯和分支界定

- - CSDN博客综合推荐文章
   在计算机科学中,分治法是一种很重要的算法. 字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并. 这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)…….

RHadoop实践系列之三 R实现MapReduce的协同过滤算法

- - 统计之都
Author:张丹(Conan). @晒粉丝 http://www.fens.me. @每日中国天气 http://apps.weibo.com/chinaweatherapp. RHadoop实践系列文章. RHadoop实践系列文章,包含了R语言与Hadoop结合进行海量数据分析. Hadoop主要用来存储海量数据,R语言完成MapReduce 算法,用来替代Java的MapReduce实现.

YOLODet检测效果图-- 包含YOLOv5、YOLOv4、PP-YOLO、YOLOv3等YOLO系列目标检测算法PyTorch版本实现

- - 开源软件 - ITeye博客
YOLODet-PyTorch是端到端基于pytorch框架复现yolo最新算法的目标检测开发套件,旨在帮助开发者更快更好地完成检测模型的训练、精度速度优化到部署全流程. YOLODet-PyTorch以模块化的设计实现了多种主流YOLO目标检测算法,并且提供了丰富的数据增强、网络组件、损失函数等模块.

[原]Lucene系列-facet

- - 文武天下
facet:面、切面、方面. 个人理解就是维度,在满足query的前提下,观察结果在各维度上的分布(一个维度下各子类的数目). 如jd上搜“手机”,得到4009个商品. 其中品牌、网络、价格就是商品的维度(facet),点击某个品牌或者网络,获取更细分的结果. 点击品牌小米,获得小米手机的结果,显示27个.

[原]Lucene系列-FieldCache

- - 文武天下
域缓存,加载所有文档中某个特定域的值到内存,便于随机存取该域值. 当用户需要访问各文档中某个域的值时,IndexSearcher.doc(docId)获得Document的所有域值,但访问速度比较慢,而且只能获得Stored域的值. FieldCache能获得域值数组,根据docId random access域值.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.