An efficient multiple scanning order algorithm for accumulative least-cost surface calculation
An efficient multiple scanning order algorithm for accumulative least-cost surface calculation
复制标题
一种高效的多扫描顺序累积最小成本曲面计算算法
DOI：
10.1080/13658816.2022.2052885
复制
发表时间：
2022
影响因子：
5.7
通讯作者：
Wang, Zekun
中科院分区：
文献类型：
--
作者：
Yao, Yuanzhi;Shi, Xun;Wang, Zekun
最小代价曲面（LCS）计算是一个计算密集型问题，通常由基于最小代价的Dijkstra算法解决。也已经提出了替代的基于光栅的扫描算法，其使用移动窗口来迭代地扫描整个研究区域。在这里，我们提出了基于光栅的算法的改进。主要改进是实现多扫描顺序（MSO），以取代传统的单一扫描顺序（SSO，通常从左上角到右下角，逐行）。我们比较了不同的算法在不同的成本表面和不同数量的源点的性能。比较表明，基于光栅的算法，采用MSO具有明显优于传统的基于光栅的算法，使用SSO的性能。基于MSO光栅的算法通常可与基于纹理的Dijkstra算法相比较，并且在相对简单的成本表面（例如，其中成本被重新采样）上和/或当源点的数量相对较大时超过后者。我们的实证实验表明，MSO降低了时间复杂度从totoAdditionally，我们发现，MSO光栅为基础的算法可以很容易地使用共享内存并行编程并行化。
The least-cost surface (LCS) calculation is a compute-intensive problem conventionally solved by the queue-based Dijkstra’s algorithm. Alternative raster-based scanning algorithms have also been proposed which use a moving window to scan the whole study area iteratively. Here we propose improvements to the raster-based algorithms. The main improvement is to implement multiple scanning orders (MSO) to replace the conventional single scanning order (SSO, typically from upper-left corner to lower-right corner, row by row). We compared the performance of different algorithms over different cost surfaces and with different numbers of source points. The comparison shows that a raster-based algorithm adopting MSO has a substantially better performance than a conventional raster-based algorithm using SSO. An MSO raster-based algorithm is generally comparable to the queue-based Dijkstra’s algorithm, and surpasses the latter over a relatively simple cost surface (e.g. in which the cost is resampled) and/or when the number of source points is relatively large. Our empirical experiments suggest that MSO reduces the time complexity from totoAdditionally, we found that the MSO raster-based algorithm can be easily parallelized using shared-memory parallel programming.
登录
查看更多内容
利用地理信息系统网络和多准则技术分析最小成本路径
DOI：
--
发表时间：
2014
期刊：
影响因子：
--
作者：
W. A. Hassan;S. Elsheikh
通讯作者：
S. Elsheikh
改进栅格数据格式的成本路径跟踪
DOI：
--
发表时间：
1994
期刊：
影响因子：
--
作者：
Jianping Xu;R. Lathrop
通讯作者：
R. Lathrop
影响因子：
13.5
作者：
Gorelick, Noel;Hancher, Matt;Moore, Rebecca
通讯作者：
Moore, Rebecca
大规模网格上的流计算
DOI：
--
发表时间：
2001
期刊：
ACM SIGSPATIAL International Workshop on Advances in Geographic Information Systems
影响因子：
--
作者：
Laura Toma;Rajiv Wickremesinghe;L. Arge;J. Chase;J. Vitter;P. Halpin;D. Urban
通讯作者：
D. Urban