【python】求数组中两个元素的最小距离？

题目：给定一个数组，数组中含有重复元素，给定两个数组num1和num2，求这两个数字在数组中出现的最小距离。

分析：动态规划法。动态规划的方法可以把每次遍历的结果都记录下来从而减少遍历次数。当遍历数组时，会遇到以下两种哪茄情况：

（缓碰1）当遇到num1时，记录下num1值对应的数组下标的位置lastPos1，通过求lastPos1与上次遍历到扰缓谈num2下标位置的值lastPos2的差可以求出最近一次遍历到num1与num2的距离。

（2）当遇到num2时，记录下num2值对应的数组下标的位置lastPos2，通过求lastPos1与上次遍历到num2下标位置的值lastPos2的差可以求出最近一次遍历到num1与num2的距离。

code:

def minDis(arr, num1, num2):

    if arr is None or len(arr) <= 0:

        return 2 ** 32

    lastPos1 = -1

    lastPos2 = -1

    minDis = 2 ** 32

    i = 0

    while i <len(arr):

        if arr[i] == num1:

            lastPos1 = i

            if lastPos2 >= 0:

                minDis = min(minDis, abs(lastPos2 - lastPos1))

        if arr[i] == num2:

            lastPos2 = i

            if lastPos1 >= 0:

                minDis = min(minDis, abs(lastPos2 - lastPos1))

        i += 1

    return minDis

if __name__ == "__main__":

    arr = [4, 5, 6, 4, 7, 4, 6, 4, 7, 8, 5, 6, 4, 3, 10, 8]

    num1 = 4

    num2 = 8

    print(minDis(arr, num1, num2))

程序运行结果为:

2

据 Drew 所知最短路经算法现在重要的应用有计算机网络路由算法，机器人探路，交通路线导航，人工智能，游戏设计等等。美国火星探测器核心的寻路算法就是采用的D*（D Star）算法。

最短路经计算分静态最短路计算和动态最短路计算。

静态路径最短路径算法是外界环境不变，计算最短路径。主要有Dijkstra算法，A*（A Star）算法。

动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。如在游戏中敌人或障碍物不断移动的情况下。典型的有D*算法。

　

这是Drew程序实现的10000个节点的随机路网三条互不相交最短路

　

真实路网计算K条路径示例：节点5696到节点3006，三条最快速路，可以看出路径基本上走环线或主干路。黑线为第一条，兰线为第二条，红线为第三条。约束条件系数为1.2。共享部分路段。 显示计算部分完全由Drew自己开发的程序完成。

　

参见 K条路算法测试程序

Dijkstra算法求最短路径：

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。

大概过程：

创建两个表，OPEN, CLOSE。

OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。

2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。

3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。

4． 重复2，3，步。直到OPEN表为空，或找到目标点。

这是在drew 程序中4000个节点的随机路网上Dijkstra算法搜索最短路的演示，黑色圆圈表示经过遍历计算过的点由图中可以看到Dijkstra算法从起始点开始向周围层层计算扩展，在计算大量节点后，到达目标点。所以速度慢效率低。

提高Dijkstra搜索速度的方法很多，据Drew所知，常用的有数据结构采用Binary heap的方法，和用Dijkstra从起始点和终点同时搜索的方法。

推荐网页：http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/ZJS04505/zjs045050a.htm

简明扼要介绍Dijkstra算法，有图解显示和源码下载。

A*（A Star）算法：启发式（heuristic）算法

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。

公式表示为：f(n)=g(n)+h(n),

其中f(n) 是节点n从初始点到目标点的估价函数，

g(n) 是在状态空间中从初始节点到n节点的实际代价，

h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

如果 估价值>实际值, 搜索的点数少，搜败闷索范围小，效率高，但察拿弯不能保证得到最优解。

估价值与实际值越接近，估价函数取得就越好。

例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多敏轿或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。

conditions of heuristic

Optimistic (must be less than or equal to the real cost)

As close to the real cost as possible

主要搜索过程：

创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->

While(OPEN!=NULL)

{

从OPEN表中取估价值f最小的节点n

if(n节点==目标节点) break

else

{

if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值

if( X的估价值小于OPEN表的估价值 )

　更新OPEN表中的估价值//取最小路径的估价值

if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值

if( X的估价值小于CLOSE表的估价值 )

　更新CLOSE表中的估价值把X节点放入OPEN //取最小路径的估价值

if(X not in both)

求X的估价值

　并将X插入OPEN表中　//还没有排序

}

将n节点插入CLOSE表中

按照估价值将OPEN表中的节点排序//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

}

---