to find-path [ source-node destination-node]
let search-done? false
let search-path []
let current-node 0
set list-open []
set list-closed []
let list-links-with-nodes-in-list-closed []
let list-links []
set list-open lput source-node list-open
while [ search-done? != true]
[
ifelse length list-open != 0
[
set list-open sort-by [[f] of ?1 < [f] of ?2] list-open
set current-node item 0 list-open
set list-open remove-item 0 list-open
set list-closed lput current-node list-closed
ask current-node
[
if parent-node != 0[
set list-links-with-nodes-in-list-closed lput link-with parent-node list-links-with-nodes-in-list-closed
]
ifelse any? (nodes-on neighbors4) with [ (xcor = [ xcor ] of destination-node) and (ycor = [ycor] of destination-node)]
[
set search-done? true
]
[
ask (nodes-on neighbors4) with [ (not member? self list-closed) and (self != parent-node) ]
[
if not member? self list-open and self != source-node and self != destination-node
[
set list-open lput self list-open
set parent-node current-node
set list-links sentence (list-links-with-nodes-in-list-closed) (link-with parent-node)
set g sum (map [ [link-cost] of ? ] list-links)
set h distance destination-node
set f (g + h)
]
]
]
]
]
[
user-message( "A path from the source to the destination does not exist." )
report []
]
]
set search-path lput current-node search-path
let temp first search-path
while [ temp != source-node ]
[
ask temp
[
set color red
]
set search-path lput [parent-node] of temp search-path
set temp [parent-node] of temp
]
set search-path fput destination-node search-path
set search-path reverse search-path
print search-path
end
很遗憾,我不知道如何加速这段代码。是否有一种解决方案可以在大空间尺度上快速计算最小成本路径?
非常感谢你的帮助。
sort-by
对list-open
进行排序,我不知道是否会增加额外开销。同时,设置 g 可能是 "当前路径成本 +1",这可能会给你一点小小的提升。我对语言的了解不够深入,无法提出更多建议,但它具有一些特征,让我感觉像是较慢的语言中常见的。 - Mooing Duck