BFS(四):搜索状态判重

2019-08-16 07:47:16来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

BFS(四):搜索状态判重

      在采用广度优先算法进行搜索时,一个需要重点注意的是在搜索过程中判重和去重。前面介绍的几个例子中,判重都较简单,如采用vis[]数组,若vis[i]==0,则i未访问过,i入队列;若vis[i]!=0,则i已访问过,不再重复访问。

      但在有些实际应用中,判重不是简单一个设置就可完成的。例如,给出一个由1、2、3、4、5、6组成的6位数,相邻的两个数字可以交换位置,问最少经过多少次交换,可以到达另一个目标6位数。例如:对于123456,最少经过两次交换,可以变成231456。 

      在解决这个问题时,一定要注意判重。例如:由123456可以变成213456,而213456又可以变成123456,这样形成了循环。因此,若某个状态已出现过,当前再出现这个状态时,应判定重复出现,不能入队进行处理。

      显然,这个问题中不能仿照以前的例子,定义一个vis[654322]数组,若某个状态231456出现就置vis[231456]=1。为什么呢?因为6个数字组成的不同状态最多6*5*4*3*2*1=720种,vis数组的元素个数是状态种数的900多倍,太浪费存储空间。

       在状态判重方法中,hash法是一种常用的方法。

【例1】最少交换。

      给出一个由1、2、3、4、5、6组成的6位数,相邻的两个数字可以交换位置,问最少经过多少次交换,可以到达另一个目标6位数。例如:对于123456,最少经过两次交换,可以变成231456。

      (1)编程思路。

       用广度优先搜索完成。在搜索中,需要解决状态判重问题。状态判重常用hash法。具体做法是:找到一种办法,把数字1~6的排列映射为一个整数num(0<=num<=(6!-1))。例如,排列123456映射为0、213456映射为1、132456映射为2、231456映射为3、…、654312映射为718、654321映射为719。这样,每种状态就可以对应一个整数。反过来说,0~ (6!-1)之间的任一整数,也可以唯一对应一种状态。因此,可以定义一个数组hash[720](初始值全部为0,代表未出现过),某个状态next出现了,先求出其对应的整数值num,然后置hash[num]=1。这样,判断状态next是否出现过,先求出next对应的整数值num,若hash[num]!=0,则表示状态next出现过。 

      n! 与n个数字组成的全排列如何映射呢?我们以3个数字1、2、3组成的全排列来说明问题。

      设排列中所有数字满足从小到大排列,则称为正序。不是正序的排列中一定存在某个数字k后面有若干个数字比k小,比k小的数字个数n称为k的逆序个数。

      例如,123的各位逆序个数序列为:0,0,0。映射整数为:0=0*2!+0*1!+0*0!=0

                 132的各位逆序个数序列为:0,1,0。映射整数为:1=0*2!+1*1!+0*0!=1

                 213的各位逆序个数序列为:1,0,0。映射整数为:2=1*2!+0*1!+0*0!=2

                 231的各位逆序个数序列为:1,1,0。映射整数为:3=1*2!+1*1!+0*0!=3

                 312的各位逆序个数序列为:2,0,0。映射整数为:4=2*2!+0*1!+0*0!=4

                 321的各位逆序个数序列为:2,1,0。映射整数为:5=2*2!+1*1!+0*0!=5

       对6位数 654312而言,各位逆序个数序列为:5,4,3,2,0,0,应映射为:5*5!+4*4!+3*3!+2*2!+0*1!+0*0!=600+96+18+4=718。

      这实际上也很好理解,654312首位出现6,后面比它小的数字有1、2、3、4、5共5个,若首位出现6,则首位分别出现1、2、3、4和5的情况都出现过,才可能首位出现6,而对于6位数而言,首位出现1的情况有5!种,首位出现2的情况也是5!种,…,所以映射时首位5*5!。

      同理,可以理解次位是:逆序个数*4!,……。

      (2)源程序。

#include <stdio.h>

#include <string.h>

int fact[]={1,1,2,6,24,120};   //  对应0!,1!,2!,3!,4!,5!

int hash(char *s)                 // 把1..6的排列*s 映射为数字 0..(6!-1)

{   

       int i, j, temp, num;   

       num = 0;   

       for (i = 0; i <6-1; i++)

       {     

            temp = 0; 

            for (j = i + 1; j < 6; j++)

            {

                  if (s[j] < s[i])

                       temp++;       

           }

           num += fact[6-i-1] * temp;

       }

       return num;

}

int BFS(char src[],char dest[])

{

       int vis[720]={0},step[720],front,rear,s0,s1,ts,i;

       char q[720][7],cur[7],next[7],tmp;

       front=rear=0;

       s1=hash(dest);

       strcpy(q[rear++],src);

       s0=hash(src);

       vis[hash(src)]=1;

       step[s0]=0;

       while (front<rear)

       {

              strcpy(cur,q[front++]);  // 出队列

              s0=hash(cur);

              if (s0==s1)             // 达到目标状态

                     return  step[s0];

              for (i=0;i<6-1;i++)

              {

                    strcpy(next,cur);

                    tmp=next[i]; next[i]=next[i+1];next[i+1]=tmp;  // 交换位置i和i+1中的数字

                     ts=hash(next);

                     if (vis[ts]==0)   // 状态未出现过

                     {

                            vis[ts]=1;

                            step[ts]=step[s0]+1;  // 记录步数

                            strcpy(q[rear++],next);

                     }

              }

       }

}

int main()

{

         char src[7],dest[7];

         while(scanf("%s%s",src,dest)!=EOF)

        {

              printf("%d\n",BFS(src,dest));

        }

        return 0;

}

 


原文链接:https://www.cnblogs.com/cs-whut/p/11162392.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:彻底弄懂UTF-8、Unicode、宽字符、locale

下一篇:“直男”与“暖男”的区别——const