Loading...
墨滴

张春成

2021/07/14  阅读:49  主题:默认主题

学而不思则罔

学而不思则罔

这是解决寻路问题代码的最后一篇,尝试让算法再快一点。 天知道我在贪婪算法上已经水了多少天。 水日常到此为止。


学而实习之

之前几篇连续的文档已经说明了寻路问题的

  • 问题属性,《私人订制》;
  • 计算难点,《贪婪算法及其困境》;
  • 优化思路,《以空间换时间》;

本文则对算法进一步优化,使其达到约每秒寻路1000条路径的较高计算效率。

由贪婪算法的原理可知

寻路算法若能够寻得两点之间的最短路径,则该路径上的任意子路径都是最短的。

那么,若我们寻得节点5145之间的最短路径,如下图所示,

greedyFaster
greedyFaster

则图中的子路径,如51 -> 8065 -> 54等等路径都是局部最短的。 我们只要能够在每次寻路中记住这些路径,就可以避免之后的重复计算。

不宜代码乎

核心代码非常简短。

memory = dict()


# @timer
def shortest_trace(start, end, dist):
    '''
    Method: shortest_trace

    Compute the Shortest Trace of the Common Graph.
    The [dist] is the distance matrix of the available Edges,
    the <inf> values refers the Edge is invalid.

    Args:
    - @start, end, dist

    Outputs:
    - The Computed Trace

    '''

    inside = [start]
    outside = [e for e in range(len(dist)) if not e == start]

    trace = dict()

    accum = np.zeros(dist.shape)

    def trace_back(e):
        back = [e]
        while back[-1] != start:
            back.append(trace[back[-1]])
        return back[::-1]

    for ____ in dist:
        x = dist + accum
        _dist = x[inside][:, outside]
        a, b = np.unravel_index(np.argmin(_dist), _dist.shape)
        a, b = inside[a], outside[b]
        trace[b] = a
        inside.append(b)
        outside.remove(b)
        accum[b, :] = x[a, b]
        if b == end:
            break
        if len(outside) == 0:
            break

    tbr = trace_back(end)

    tb = tbr.copy()
    while len(tb):
        for j in range(len(tb)-1):
            memory[(tb[j], tb[-1])] = tb[j:]

        for j in range(1, len(tb)):
            memory[(tb[0], tb[j])] = tb[:j]

        tb = tb[1:-1]

    return tbr

张春成

2021/07/14  阅读:49  主题:默认主题

作者介绍

张春成