从可行解到最优解的思考2021-02-11（未允禁转）
实际问题一般包含若干组可行解，所有可行解中又存在最优解
可行解往往是一些局部最优解，甚至连局部最优都不具备；而最优解则是全局最优
在计算机领域，
- 常常通过贪心算法求可行解
- 常常通过滑动窗口、动态规划、回溯等基于特定规则的算法求最优解
在做了#### leetcode1631. 最小体力消耗路径之后，体会到一种思想：
最优解可以通过【不断限制可行解直到不能进一步限制】而得到
简单举个例子，
建一座桥，要求可以同时通行10辆车，最小桥面宽多少就可以满足要求了？
首先抛开【最小】的限制条件，求可行解很容易，宽1000米，500米，100米，显然都可以。那需要求最小宽度呢？我们可以不断限制压缩可行解，50米行不行？40米行不行？30米行不行？直到不能继续往下再小了，就是最优解。而这个限制的过程，结合一下二分查找的思想，可以提高效率。
给定一个二维矩阵heights
满足1 <= rows, columns <= 100，1 <= heights[i][j] <= 10^6
从左上角到右下角，每一步可以上下左右走，只要不走出矩阵。定义一条路径的代价是该路径上前后两个相邻位置的差值绝对值的最大值。求走到右下角的最小代价
思路：
由于每一步可以走上下左右，那么可能的路径就会非常复杂，这绕那绕都可能，直接想出求解最优解的规则存在一定难度。这个时候，我们可以先考虑可行解——我们发现，题目限定了1 <= heights[i][j] <= 10^6， 我们如果抛开最优解先考虑可行解，那么代价为10^6时我们必然可以走到右下角，而最小代价显然可以是0。得到代价的范围之后，我们应用二分的思想，不断调整我们的代价，保证在当前代价下问题有解，直到代价不能再小，即为所求
从算法本身的角度理解就是，先获得最优解的范围区间，再通过二分法定位
现在的关键就在于，给定一个代价，如何判断存在不高于该代价的路径可以抵达右下角？这其实是一个有解问题，那么我们只需要用贪心算法找到一条合法路径就可以证明有解——
在特定的threshold下，以【bfs+优先队列】的方法逐步搜索至右下角。
具体是，每次从优先队列中pop出与下一位置最近的position (a, b)，每次走最近的路，如果当前位置已被访问，继续从优先队列pop。检查(a,b)的上下左右4个邻居，对于邻居nei，检查(a, b)到nei的距离是否不超过threshold，如是，表示nei在threshold下可达，连同距离一起推入优先队列。如右下角加入了已访问集合，表示threshold下可达，否则threshold下不可达
import heapq
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
if not heights:
return 0
def getNeibor(i, j, heights):
for ii, jj in [-1,0],[0,1],[0,-1],[1,0]:
if 0 <= i + ii < len(heights) and 0 <= j + jj < len(heights[0]):
yield i + ii, j+jj
# 检查是否有不高于threshold代价的路径
def bfs(i, j, heights, threshold, visited):
r, c = len(heights), len(heights[0])
q = []
heapq.heappush(q,(0,i,j))
while q:
# 使用优先队列保证总是选择最近的下一站
_, a, b = heapq.heappop(q)
if (a, b) in visited:
continue
visited.add((a,b))
if (r-1,c-1) in visited:
return True
for nei in getNeibor(a,b,heights):
delta = abs(heights[nei[0]][nei[1]] - heights[a][b])
# 满足threshold限制时，nei是合法的下一站，送入优先队列排序作为下一站的候选
if delta <= threshold:
if nei not in visited:
heapq.heappush(q,(delta,nei[0],nei[1]))
return False
l, r = 0, 10**6
# 二分查找
while l < r:
mid = l + (r-l) // 2
if bfs(0,0,heights,mid,set()):
r = mid
else:
l = mid + 1
return l
另外，借助上面bfs+优先队列的思想，我们还可以直接找到最优路径，而无需多次进行二分查找判断是否有解——
在上面的做法中，优先队列内按【相邻位置间的代价】大小排序，每次都走相邻代价最小的一步。这里换一下，优先队列内按【与源点的代价】大小排序，每次都在全局层面走与源点代价最小的一步。也就是改了路径长度定义的Dijkstra算法
import heapq
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
if not heights:
return 0
r, c = len(heights), len(heights[0])
# 统计从(0,0)到(x,y)的体力值
strength = [[float('inf') for i in range(c)] for j in range(r)]
def getNeibor(i, j, heights):
for ii, jj in [-1,0],[0,1],[0,-1],[1,0]:
if 0 <= i + ii < len(heights) and 0 <= j + jj < len(heights[0]):
yield i + ii, j+jj
def bfs(heights, visited, strength):
r, c = len(heights), len(heights[0])
q = []
heapq.heappush(q,(0,0,0))
strength[0][0] = 0
while q:
# 优先队列确定访问的顺序，每次都走维护邻居距离原点的【体力】最小的位置
s, a, b = heapq.heappop(q)
if (a, b) in visited:
continue
visited.add((a,b))
# 如果右下角已经被访问，直接返回
if (r-1,c-1) in visited:
return
# 维护邻居距离原点的【体力】，并依据【体力】进入优先队列
for nei in getNeibor(a,b,heights):
delta = abs(heights[nei[0]][nei[1]] - heights[a][b])
d = max(s, delta)
if d <= strength[nei[0]][nei[1]]:
cur_nei = (d, nei[0], nei[1])
heapq.heappush(q, cur_nei)
strength[nei[0]][nei[1]] = d
visited = set()
bfs(heights, visited, strength)
return strength[-1][-1]
