你能解释一下我以下运行时的现象吗?
1视图(30天)
显示旧的评论
你好,
我写我的国家考试论文对算法求解最短路径问题的图表。
论文的核心算法是Dijkstra算法和A *。
有一章对两种算法的比较。比较是扫描/关闭节点的数量,需要单独的步骤和所需的运行时。为此,我写了一个脚本,该脚本创建了250图根据计划。(见图1,
)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520927/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520932/image.jpeg)
(图1)
在另一个脚本,我有Dijkstra算法计算最短路径
来
和一个最短路径
来
为每个250图。脚本测量了三个参数。
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520937/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520942/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520947/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520952/image.png)
我创建的图后测量参数:图2显示了扫描节点的数量。
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520957/image.png)
(图2:蓝色的序列=最短路径
来
橙色的序列=最短路径
来
)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520962/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520967/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520972/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520977/image.png)
根据图(和数据),序列似乎广场。下一个图显示所需的运行时。
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520982/image.png)
(图3:蓝色的序列=最短路径
来
橙色的序列=最短路径
来
)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520987/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520992/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/520997/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521002/image.png)
令人惊讶的是,有一个运行时“跳”。
根据测量数据,运行时
是蓝色的30秒左右,橙色的56秒左右。
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521007/image.png)
然后,测量运行时
是蓝色的大约68秒,橙色的大约121秒。
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521012/image.png)
因此,运行时几乎翻了一倍。
我有检查Dijkstra算法的图形和脚本,没有问题。的运行时也会发生“跳”*
。(见图4)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521017/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521022/image.png)
(图4:蓝色= Dijkstra´s最短路径序列
来
橙色的序列= *´s最短路径
来
)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521027/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521032/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521037/image.png)
![](http://www.tianjin-qmedu.com/matlabcentral/answers/uploaded_files/521042/image.png)
在论文的讨论,我想解释这一现象,需要你的帮助。(可能是一个软件问题?)
我的计算机科学知识是非常有限的但我想理解它。