● 优化的回溯算法 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: jek (好好学习天天向上), 信区: Program
标  题: 优化的回溯算法
发信站: BBS 荔园晨风站 (Fri Mar 31 19:25:54 2000), 转信

传统的回溯法时间复杂度大，在有些情况下效率很底，例如，当主串
为‘0000000000000000000000000000000000000000000000001’，而模
式串为‘00000001’时，由于模式中前7个字符均为0，又，主串中前
52个字符均为0，每趟比较都是在模式的最后1个字符出现不等，此时
需将指针i回溯到i-6的位置上，并从模式的第一个字母开始重新比较，
整个回溯过程中指针需回溯45次，则while循环次数为46*8。此时时间
复杂度为O（n*m）。
但稍做改动，却可以避免这种情况的出现。思想如下：
在搜索过程中遇到不等的字符时不马上回溯，而是继续搜索直到该原
来不等的字符找到相等的字符为止，接着再回溯到i=i-j+2、j=1开始
从新比较，直至找到为止。用以下类pascal程序实现。

CONST maxlen=?
TYPE strtp=RECORD
            ch:ARRAY[1..maxlen] OF char;
            curlen:1..maxlen
           END;
FUNCITON index_BF(s,t:strtp):integer;
  i:=1;j:=1;
  WHILE (i<=s.curlen) AND (j<=t.curlen) DO
    IF s.ch[i]=t.ch[j]
      THEN BEGIN
             i:=i+1;j:=j+1
           END
      ELSE BEGIN
             WHILE (s.ch[i]<>t.ch[j]) AND (i<=s.curlen) DO
               i:=i+1;
             i:=i-j+2;
             j:=1;
           END;
  IF j>t.curlen
      THEN RETURN(i-t.curlen)
      ELSE RETURN(0);
ENDF;

该改进的回溯法对上面特别的情况非常有用，外while循环次数为2*8，内
while只用一次，其循环次数为46，一共while次数仅为（46+2*8），比
（46*8）改进了很多，时间复杂度为O（n+2m），远远比O（n*m）小。

--
※ 修改:·jek 於 Mar 31 19:41:26 修改本文·[FROM: 192.168.1.118]
※ 来源:·BBS 荔园晨风站 bbs.szu.edu.cn·[FROM: 192.168.1.118]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店