很快,一幅山区地势图出现在杨成眼前:
0,0,1,1
0,1,2,3
1,2,5,4
0,1,1,0
“咦,这上面这么多数字,代表什么意思?”
杨成端详了半天,没看出个究竟。
“数字代表局部区域的海拔高度,以千米作为计量单位”。
“我们目前正处于地图的最左上角,也就是坐标[0, 0]的位置,当前海拔不足1千米,所以记作0”。
“此行的目的地是最右下角,坐标[3, 3],那里的高度也是0”。
经理耐心地逐一解释道。
“如你之前讲的,不想去攀登高峰(海拔高的地方)”。
“那小伙子你就找出一条最能够节省体力的路径来嘛!”
杨成这下子才有了些眉目。
对于登山而言,如果两个区域高度差越大,肯定消耗体力就越大。
这个问题可以归纳为:
找到从出发点到达目的地消耗体力最小的路径。
那怎么根据这个问题建立模型呢?
杨成仔仔细细地观察这个地图,决定采用一个通用的模型。
加权有向图!