《算法图解》笔记 iii

迪克斯特拉算法

在图中，搜索最小的“段”数可以用广度优先算法，这就相当于默认每条边的权重是相同的，如果每条边的权重不同呢？那就需要用到迪克斯特拉算法。

概括来说，迪克斯特拉算法就是从起点开始，首先寻找最廉价的节点，更新其开销并标记为已处理，然然后在未处理的节点中寻找开销最小的节点，然后以此往复下去。

针对书中的这样一个问题，我把题干提取出来：目标是用乐谱换钢琴。现在乐谱可以免费换海报；海报加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千亿种可能。可以看到，没有算法能很快的计算出这个问题，那么我们可以使用贪心算法，求局部最优解，然后将最终得到的视为全局最优解。

那么在这个问题下如何使用贪心算法？核心在于什么是局部最优条件？可以这样：

1. 选择一家覆盖了最多未覆盖省的公司。
2. 重复第一步。

我们在进行测试的时候稍稍简化一下问题，将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