迪克斯特拉算法
在图中，搜索最小的“段”数可以用广度优先算法，这就相当于默认每条边的权重是相同的，如果每条边的权重不同呢？那就需要用到迪克斯特拉算法。
概括来说，迪克斯特拉算法就是从起点开始，首先寻找最廉价的节点，更新其开销并标记为已处理，然然后在未处理的节点中寻找开销最小的节点，然后以此往复下去。
针对书中的这样一个问题，我把题干提取出来：目标是用乐谱换钢琴。现在乐谱可以免费换海报；海报加30元换吉他；海报加35元换架子鼓；乐谱加5元可以换唱片；唱片加15元换吉他；唱片加20元换架子鼓；吉他加20元换钢琴；架子鼓加10元换钢琴。
现在我用图把这个关系表示出来：
image
可以看出这是一个加权图，现在我们要使用迪克斯特拉算法寻找最短路径。
代码实现：
#检索图
def dijkstra_find(costs,parent,processed):
#找到当前最廉价的节点
node =lowest_cost_node(costs,processed)
while node is not None:
cost=costs[node]
if not graph.__contains__(node):
break
neighbours=graph[node]
for key in neighbours.keys():
new_cost=cost+neighbours[key]
if costs.__contains__(key):
if costs[key] > new_cost:
costs[key] = new_cost
parent[key] = node
else:
costs[key]=new_cost
parent[key] = node
processed.append(node)
node = lowest_cost_node(costs,processed)
#在开销表中寻找最廉价的节点
def lowest_cost_node(costs,processed):
lowest_cost=float("inf")
lowest_node=None
for node in costs:
cost=costs[node]
if cost<lowest_cost and node not in processed:
lowest_cost=cost
lowest_node=node
return lowest_node
if __name__ == '__main__':
#要检索的图
graph={}
graph['music']={}
graph['music']['record']=5
graph['music']['poster']=0
graph['record'] = {}
graph['record']['guitar']=15
graph['record']['drum']=20
graph['poster'] = {}
graph['poster']['guitar']=30
graph['poster']['drum']=35
graph['drum'] = {}
graph['drum']['piano']=10
graph['guitar'] = {}
graph['guitar']['piano']=20
#开销表
infinity=float('inf')
cost={}
cost['record']=5
cost['poster']=0
#线路表
parent={}
parent['record']='music'
parent['poster']='music'
#已检索过的节点
processed=[]
dijkstra_find(cost,parent,processed)
#打印父子节点表，通过父子节点表可以找到路径
print(parent)
输出：
image
最后的最低开销表为：
| 节点 | 开销 |
---|-----|------|
| 海报 | 0 |
| 唱片 | 5 |
| 吉他 | 20 |
| 鼓 | 25 |
| 钢琴 | 35 |
父子节点表为：
| 父节点 | 子节点 |
---|-----|------|
| 乐谱 | 唱片 |
| 乐谱 | 海报 |
| 唱片 | 吉他 |
| 唱片 | 鼓 |
| 鼓 | 钢琴 |
可以看出，最优的交换的路径为：piano-drum-record-music
最低开销为：35元
贝尔曼-福德算法
在迪克特拉斯算法的基础上，我们考虑这样一种情况，假如边的权重存在负值。
在迪克特拉斯算法中，我们首先寻找最廉价的节点，更新其开销，再寻找未处理节点中最廉价的节点，以此往复。
可能出现这样一个情况：
image
在将海报标记为已处理后，开始处理唱片，但是唱片到海报的路径使得海报的开销更小，又将更新海报的开销，但是海报已经标记为已处理。那么就会出现一些问题。假如继续使用迪克特拉斯算法，最后的结果肯定是错的，大家可以更改参数试一下。为了正确解决问题，这时需要使用贝尔曼-福德算法。
贪心算法
对于一些比较复杂的问题，使用一些算法不能简单有效地解决，这时候往往会使用贪心算法：每步操作都选择局部最优解，最终得到的往往就是全局最优解。这似乎是想当然的做法，但是很多情况下真的行之有效。当然，贪心算法不适用于所有场景，但是他简单高效。因为很多情况并不需要追求完美，只要能找到大致解决问题的办法就行了。
假如我们面对这么一个问题：假设我开了一家网店，在全国各省都有生意，现在面临发快递的问题，假设现在的基础物流不是很完善，每家快运公司只能覆盖很少几个省，那么我该如何在覆盖全国34个省级行政区的情况下，选择最少的快运公司？
这个问题看似不难，其实很复杂。
现在假设有n家快运公司，那么全部的组合有2^n种可能。
| N | 2^N |
---|-----|------|
| 10 | 1024 |
| 20 | 1048576 |
| 50 | 1125899906842624 |
可以看到，假如有50家快递公司，我将要考虑1125千亿种可能。可以看到，没有算法能很快的计算出这个问题，那么我们可以使用贪心算法，求局部最优解，然后将最终得到的视为全局最优解。
那么在这个问题下如何使用贪心算法？核心在于什么是局部最优条件？可以这样：
- 选择一家覆盖了最多未覆盖省的公司。
- 重复第一步。
我们在进行测试的时候稍稍简化一下问题，将34个省改为10个省。
代码实现：
def func(company,province):
result = set()
province_need=province
#当存在未覆盖的省时，循环一直继续
while province_need:
best_company=None
province_coverd=set()
#查找局部最好的选择
for temp_company,temp_province in company.items():
coverd=province_need & temp_province
if len(coverd)>len(province_coverd):
best_company=temp_company
province_coverd=coverd
province_need-=province_coverd
result.add(best_company)
return result
if __name__ == '__main__':
province=set(["河北","山西","辽宁","吉林","黑龙江","江苏","浙江","安徽","福建","江西"])
company={}
company["顺丰"]=set(["河北","山西","辽宁","江苏","浙江"])
company["圆通"]=set(["吉林","浙江"])
company["中通"]=set(["黑龙江","江西"])
company["韵达"]=set(["江苏","浙江","江苏"])
company["EMS"]=set(["浙江","安徽","河北","山西"])
company["德邦"]=set(["福建","江西","安徽"])
select_company=func(company,province)
print(select_company)
输出结果：
image
image
网友评论