寻友之旅 - 利用剪枝降低bfs算法的时空复杂度

xss

February 12, 2023

2233 views

No comments

2930 words

便签

当青训营遇上码上掘金

题目寻友之旅

小青要找小码去玩，他们的家在一条直线上，当前小青在地点 N ，小码在地点 K （0≤N , K≤100 000），并且小码在自己家原地不动等待小青。小青有两种交通方式可选：步行和公交。
步行：小青可以在一分钟内从任意节点 X 移动到节点 X-1 或 X+1
公交：小青可以在一分钟内从任意节点 X 移动到节点 2×X （公交不可以向后走）

请帮助小青通知小码，小青最快到达时间是多久？
输入：两个整数 N 和 K
输出：小青到小码家所需的最短时间（以分钟为单位）

思路和解题过程

首先看一下限定条件小码所在的地点 k<1000 小青所在地点N大于等于0。
其次通过题目可以得知小青如何走，有三种方法：

N-1：向后走
N +1：向前走
N *2：坐公交

如果我只考虑每一步当前的离K最短的距离其实可以这么写

package main
import (
    "fmt"
    "math"
)

func main() {
    var N, K int
    
  N=13
  K=24

    numStep := 0
    for N != K {
        numStep++
        plan1 := N - 1
        plan2 := N + 1
        plan3 := 2 * N
        if plan1 < 0 || plan1 > 100000 {
            plan1 = N
     
        }
        if plan2 < 0 || plan2 > 100000 {
            plan2 = N
      
        }
        if plan3 < 0 || plan3 > 100000 {
            plan3 = N
     
        }
        len1 := int(math.Abs(float64(plan1 - K)))
        len2 := int(math.Abs(float64(plan2 - K)))
        len3 := int(math.Abs(float64(plan3 - K)))
        if len1 > len2 {
            if len3 > len2 {
                N = plan2
            } else {
                N = plan3
            }
        } else {
            if len3 > len1 {
                N = plan1
            } else {
                N = plan3
            }
        }
    }
    fmt.Println(numStep)
 
}

在线运行

这个方法算是使用了贪心算法，把问题拆解成一步一步的去完成，每一步选择最优的方法，但是会出现一些问题。举个例子，如果小码在24，小青在13的话，我们令N=13，k=24，运行代码显示是3分钟到达,即 13-26-25-24 是三分钟到达，显然还有一种解法是 13-12-24是2分钟到达，贪心算法没有搜索到这种情况。
~~那么让我们回顾一下贪心算法的定义~~（凑一下字数.jpg）

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的

那么既然贪心算法并不能覆盖所有的情况，有必要考虑一下更加暴力的一些方法（雾）

然后死去的数据结构与算法突然开始提醒我，可以使用 宽度优先搜索（BFS） 的方式来对所有可能的方式进行一个历的遍
最开始我们要输入小青的当前位置N 和分钟数0 而且这个数值会在后续变化，所以定义一个结构体来保存分钟数t_num和当前位置pos

判断N是否和K相等如果相等则返回当前分钟数，然后判断所有可能的下一步是不是已经执行过，若没有执行过，那么去判断下一步之后是否符合0-100 000这个范围，符合则标记这个已经执行，并将当前位置的分钟数+1
循环执行上面的步骤，直到所有路径都被标记或者到达终点，当到达的下一个点就是终点，即小青到了小码家，这时候我们就可以将搜索结果返回，因为此时是第一次到达指定的点位，在BFS中，首次到达特定点位即路径最短，亦时间最短

特殊地有

当小码的位置位于小青后方时(N>K)，因为公交车不能往后走，因此小青只能选择步行的方式来去到达小码的位置

然后由于是宽度优先算法，时间、空间开销较大，有一些违反常理的路径要进行剔除。比如，执行下一步后，小青坐公交超过了小码的位置，而且停止后两人距离比目前更远，还只能走着回去，显然是不符合人类的思维方式，也不会是最优解。

最终代码

 package main

import (
 "fmt"
 "math"
)

type node struct {
 Timenum int
 pos     int
}//结构体，标注当前位置和所用时间

func main() {
 var N, K int
 N=0
 K=15 //不会用码上掘金输入参数，故固定参数
//当小码的位置位于小青后方时(N>K)，因为公交车不能往后走，因此小青只能选择步行的方式来去到达小码的位置
 if N > K {
     fmt.Println(N - K)
     return
 }
  
//定义队列，curNode赋初值
 que := make([]node, 0)
 curNode := node{
     Timenum: 0,
     pos:     N,
 }
 que = append(que, curNode)
  /*判断N是否和K相等 如果相等则返回当前分钟数，然后判断所有可能的下一步是不是已经执行过，若没有执行过，那么去判断下一步之后是否符合0-100 000这个范围，符合则标记这个已经执行，并将当前位置的分钟数+1
循环执行上面的步骤，直到所有路径都被标记或者到达终点，当到达的下一个点就是终点，即小青到了小码家，这时候我们就可以将搜索结果返回，因为此时是第一次到达指定的点位，在BFS中，首次到达特定点位即路径最短，亦时间最短*/
 for curNode.pos != K {
 //三种走法 前进 往回走 坐公交车
     tmp1 := node{
         Timenum: curNode.Timenum + 1,
         pos:     curNode.pos - 1,
     }

     tmp2 := node{
         Timenum: curNode.Timenum + 1,
         pos:     curNode.pos + 1,
     }

     tmp3 := node{
         Timenum: curNode.Timenum + 1,
         pos:     curNode.pos * 2,
     }



     if tmp1.pos >= 0 || tmp1.pos <= 100000 {
         que = append(que, tmp1)
     }
     if tmp2.pos >= 0 || tmp2.pos <= 100000 {
         que = append(que, tmp2)
     }
 //执行下一步后，小青坐公交超过了小码的位置
     if tmp3.pos >= 0 || tmp3.pos <= 100000 || tmp3.pos-K < int(math.Abs(float64(curNode.pos-K))) {
         que = append(que, tmp3)
     }

     curNode = que[0]
     que = que[1:]
 }

 fmt.Println(curNode.Timenum)
}

在线运行

作者：xss6
链接：https://juejin.cn/post/7198905912685625403
来源：稀土掘金/个人博客
著作权归作者所有。转载请联系作者获得授权。

寻友之旅 - 利用剪枝降低bfs算法的时空复杂度