更快的递归

/

2019-6-12

背景

学习人工智能课的时候提到了CSP回溯搜索方法,想尝试用这个方法来解决数独问题
最开始用python写了一版普通的搜索,能跑,9x9的几秒就能出结果,12x12的跑了好久也跑不出来
于是想从编程的角度加快一下速度
形象的比喻一下搜索的过程:一棵树,我们在递归搜索的时候,是从根节点开始,递归的时候把根节点的所有子节点的搜索函数都写入函数栈,最先执行的递归函数,会重复这个过程,把子节点的递归函数再入栈,因此搜索顺序是深度优先的,所以程序运行过程中,同时运行的函数只有一个,顺序遵从深度优先的搜索。

思考

那有没有什么办法,让函数的运行从同时只有一个函数运行,到多个呢?有,我最先想到的就是用go语言的协程来写,原本的代码好比是一个人从根节点出发,一个一个节点的走,那我们为什么不能同时多个人出发呢

代码思路1

  1. func find(node node) err{
  2. // 搜索策略 省略
  3. for child in range(children){
  4. go find(child)
  5. }
  6. }

好的,代码一跑,不用想也是爆栈。函数栈爆了,这告诉我们,同时在运行的函数不能过多,那怎么办?我们可以尝试人为控制栈。
要知道,上面的代码在开协程的时候是没有控制的,那么我们尝试在开协程的时候加上控制

代码思路2

  1. const chan_len = 3
  2. c := make(chan int , chan_len)
  3. for i :=0;i<chan_len;i++{
  4. c <- i +1
  5. }
  6. func find(node node, c *chan int, id int) err{
  7. // 搜索策略
  8. if 搜索到终端节点{
  9. // 归还凭证
  10. *c <- id
  11. }
  12. for child in range(children){
  13. if id == 0 {
  14. // 如果id为0,则视为没有运行凭证,需要从 c 中获取
  15. id = <- *c
  16. go find(child , c , id)
  17. }else{
  18. find(child , c , id)
  19. }
  20. }
  21. }
  22. find(root, &c ,0)

不考虑操作系统层面,个人认为是可以提高递归速度的,当然了,细心的你也会发现,这样子资源占用的峰值也会提高,需要做好内存分配,否则在一些大型的搜索过程中,会使机器资源很快跑满。而且上述代码缺少同步策略,直接翻译代码是跑不了的,主进程不会等协程就早早结束了。

Reproduced please indicate the author and the source, and error a link to this page.
text link: //sealbaby.cn/fast_func