Loading...
墨滴

张春成

2021/07/06  阅读:76  主题:默认主题

最小连通图

最小连通图

本文将介绍最小连通图原则,及其在图构建过程的应用。


图 = 节点 + 边

图是一种数学结构,但并不复杂。

图 = 节点 + 边

可以将它想象成一些建筑,以及连通它们的道路,如下图所示

LeastLengthRoute
LeastLengthRoute

而原始的散点图如下

ScatterPlot
ScatterPlot

最小连通原则

那么如何从最初的散点生成连通图就是一个很现实的问题。 解决这个问题的常用手段之一,即是“最小连通原则”方法。

使用边连通所有节点,使得这些边的总长度最小。

我们可以使用基于动态规划的局部贪婪算法对其进行求解, 求解过程如下图所示

Route
Route

图示了这样的求解过程,

  • 从左上角开始不断迭代;
  • 通过不断选择局部最短边,可以逐渐达到最右边的同色节点;
  • 通过这样的过程,可以连通所有节点;
  • 由于每次添加的边都是可以找到的最短边,所以根据迭代过程进行分析,最终找到的连接方案一定是总长度最小的方案。

实现代码

由于本部分代码将隶属于一个较大规模的工程,目前并没有上传到GITHUB,现将关键代码不加解释地给出,它仍待完善。

@timer
def mk_route_least_length(df, dist=None, start=0, end=-1):
    '''
    Method: mk_route_least_length

    Make Routing Link to the graph of [df],
    - The start idx is [start];
    - The end idx is [end];
    - The end is -1 refers Routing all the Nodes;
    - The dist refers the distance between Nodes,
      if the dist is not given, the matrix is calculated based on Norm2.

    Todo:
    - How to use Customized [dist] Matrix;
    - Test on Provided [end] index.

    Args:
    - @df, dist, start, end

    Outputs:
    - The Routing Table.
    '''


    n = len(df)

    assert(n > 3)

    d = df.values.copy()
    if dist is None:
        dist = np.zeros((n, n))
        for j in range(n):
            dist[j] = np.linalg.norm(d - d[j], axis=1)
            dist[j][j] = np.inf

    df['state'] = 'outside'
    route = []

    j = np.argmin(dist[start])
    route.append((start, j))
    df.loc[start, 'state'] = 'inside'
    df.loc[j, 'state'] = 'inside'

    if j == end:
        return route, dist

    for _ in tqdm(range(n)):
        inside = df.query('state=="inside"').index
        outside = df.query('state=="outside"').index
        _dist = dist[inside][:, outside]
        a, b = np.unravel_index(np.argmin(_dist), _dist.shape)
        a, b = inside[a], outside[b]
        route.append((a, b))
        df.loc[a, 'state'] = 'inside'
        df.loc[b, 'state'] = 'inside'

        if b == end:
            print('I: Break Adding because End is Reached.')
            break

        if 'outside' not in df['state'].values:
            print('I: Break Adding because No Node is Left.')
            break

    return route, dist

`

张春成

2021/07/06  阅读:76  主题:默认主题

作者介绍

张春成