免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2376 | 回复: 4

perl关于迭代回溯和递归回溯的代码实现 [复制链接]

论坛徽章:
0
发表于 2013-06-02 19:08 |显示全部楼层
20可用积分
本帖最后由 pp1984829 于 2013-06-02 21:08 编辑

如图二维数组
@a = {
(a,b,c,d,e)
(f,g,h,i,j,k)
(l,m,n,o,p)
(q,r,s,t,u)
(v,w,x,y,z)
}

题目是从二维数组的每一行的数组中选出一个元素,列举出所有的组合方式.
例如可行组合(a,f,l,q,v),(b,h,o,s,z)等。
现在我用递归回溯的算法解出了答案,遇到很比较大的数组时效率很低,想求一迭代回溯的实现方法提高效率。@a二维数组是我列举的例子,实际场景中二维数组的元素个数未知为n.

类似于这个C的题目:从m个数里面选择n个数的组合
41@YRM7GZK77N`$FJWN3}6Q.jpg















五、回溯法   

    回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。






希望高手能出手,给出迭代回溯的代码,非常感谢!

论坛徽章:
0
发表于 2013-06-02 19:14 |显示全部楼层
题目类似于经典的8皇后问题,只不过没有剪纸,而是列举出所有组合。

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2013-06-03 20:20 |显示全部楼层
大牛 bruceteen NO 递归 一个for循环来做的算法
http://bbs.chinaunix.net/thread-4084329-1-1.html
  1. my @A = ( [ 1 .. 4 ], [ 'A' .. 'C' ], [ 'a', 'b' ], [ 10 .. 13 ] );

  2. sub Combine {
  3.     my ( $all, $t ) = ( 1, 1 );
  4.     my @E = map { scalar @$_ } @_;
  5.     $all *= $_ for @E;
  6.     my @M = reverse( 1, map { $t = $t * $E[ -$_ ] } 1 .. $#E );
  7.     for my $i ( 0 .. $all - 1 ) {
  8.         my @I = map $i / $M[$_] % $E[$_], 0 .. $#M;
  9.         say join $", map $_[$_][ $I[$_] ], 0 .. $#I;
  10.     }
  11. }
  12. Combine @A;
复制代码

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2013-06-03 20:20 |显示全部楼层
本帖最后由 rubyish 于 2013-06-03 16:25 编辑

del~

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2013-06-03 20:24 |显示全部楼层
大牛 Perlvim NO 递归 for循环来做的算法:
http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=3747978
  1. my @A = ( [ 1 .. 4 ], [ 'A' .. 'C' ], [ 'a', 'b' ], [ 10 .. 13 ] );
  2. sub Combine {
  3.     my @R = @{ +shift };
  4.     for my $e (@_) {
  5.         @R = map { my $r = $_; map "$r $_", @$e } @R;
  6.     }
  7.     return @R;
  8. }
  9. my @w = Combine @A;
  10. say for @w;
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP