NetLogo nw 扩展：如何将 nw:extension 用于多个目标

Question

大家好，netlogo nw:extension 可以计算多个目的地的路径吗？

我希望我的源 0 通过所有红色节点目的地。我尝试首先将所有目的地的 node-links 是一个列表。然后从那里我将最小数量的 node-links 作为我的第一条路径，然后将 nodes(turtle) 和 node-link 访问，这样它就不会检查节点并且它是 link 再一次。例如(node-link 0 4) (node-link 0 8)，然后添加links和目的节点8到visited。我不知道如何检查是否选择了节点 8。有什么想法吗？？

to setup
  ca
  crt Nodes
  set-default-shape turtles "circle"
  let positions [
    [-7 7] [-1 7] [5 7] [11 7] [-7 1] [-1 1] [5 1] [11 1] [-7 -5] [-1 -5] [5 -5] [11 -5]
    [-7 -11] [-1 -11] [5 -11] [11 -11]
  ]
  foreach sort turtles [
    nodePos -> ask nodePos [
      setxy (first first positions) (last first positions)
      set positions but-first positions
    ]
  ]
  ask turtles [;setxy random-xcor random-ycor
    if Show_Names? = True [show-names]]
  ;ask patches [set pcolor white]
end
to create-random-graph
  ask links [die]
  ask turtles [
    set color blue
    let neighbor-nodes other turtles in-radius 6
    create-node-links-with neighbor-nodes [
      set weight 1
      set label weight
      set color grey
      set thickness 0.1
    ]
  ]
to TEST
  let FDestin[ 9 6 8]
  let Origin 0
  let a 0
  let b []
  let i 0
  while [a < length(FDestin)  ][
    let Destin item a FDestin
    ask turtle Origin [
      set path nw:weighted-path-to turtle Destin weight
      set b lput(path ) b
    ]
    set a a + 1
  ]
let findMinPath sort-by [ [list1 list2] -> length(list1) < length (list2) ]b
let findMin []
set findMin lput item 0 findMinPath findMin
;foreach findMin [ x -> ask one-of node-links x [die]]
end

Answer 1

这有点粗糙，但可以帮助您入门。使用这些扩展和设置：

extensions [ nw ]
undirected-link-breed [ node-links node-link ] 
breed [ nodes node ]
breed [ walkers walker ]
turtles-own [ path target-nodes ]
links-own [ weight ]

to setup
  ca
  set-default-shape nodes "circle"
  set-default-shape walkers "arrow"
  let vals ( range 11 -11 -5 )
  foreach vals [ y ->
    foreach reverse vals [ x ->
      ask patch x y [
        sprout-nodes 1 [
          set color blue
          set label who
          set size 2
        ]
      ]
    ]
  ]
  create-network
  ask one-of nodes [
    hatch-walkers 1 [
      set color green
      set pen-size 5
      pd
      set target-nodes nobody
      set path []
    ]      
    ask n-of 3 other nodes [ set color red ]
  ]
  reset-ticks
end

这会创建一个节点网格，以及一个 walker 随机放置在其中一个节点上的节点。没有 walker 的三个节点是红色的，作为路径中的 'target' 个节点。然后，你的网络程序如你的问题：

to create-network
  ask links [die]
  ask nodes [
    set color blue
    let neighbor-nodes other turtles in-radius 5
    create-node-links-with neighbor-nodes [
      set weight one-of [ 1 2 3 ]
      set label weight      
      set color grey
      set thickness 0.1
    ]
  ]
end

这为您提供了一个随机加权的链接网络，供步行者遵循。

现在，要构建路径，让步行者将红色节点识别为可能的目标。然后，生成所有可能的路径排列，始终从步行者所在的节点开始。

排列是使用从

修改的代码生成的

to-report path-permutations [ node-list ] ;Return all permutations of `lst`
  let n length node-list
  if (n = 0) [report node-list]
  if (n = 1) [report (list node-list)]
  if (n = 2) [report (list node-list reverse node-list)]
  let result []
  let idxs range n
  foreach idxs [? ->
    let xi item ? node-list
    foreach (path-permutations remove-item ? node-list) [?? ->
      set result lput (fput xi ??) result
    ]
  ]
  report result
end

编辑：海龟不再是途中的最少海龟，而是 select 具有最小加权距离的路线。

计算每条可能路径的海龟数量，select整条路线上加权距离最小的路径。

to set-path
  if target-nodes = nobody [
    ; Designate any red nodes as targets
    set target-nodes nodes with [ color = red ]
    let start-node one-of nodes-here

    ; Get a list of nodes
    let target-node-list sort target-nodes

    ; Build all possible paths
    let possible-paths map [ i -> sentence start-node i ] path-permutations target-node-list

    ; Get the weighted distance turtles for each possible path
    let path-turtles map [ i -> turtles-on-path i ] possible-paths

    ; Keep the path with the smallest overall weighted distance 
    let shortest-path reduce [
      [ shortest next ] ->
      ifelse-value ( weighted-dist-of-path shortest < weighted-dist-of-path next ) [ shortest ] [ next ] ] path-turtles
    set path shortest-path
  ]
end

set-path 使用这两位记者：

to-report turtles-on-path [ in-path ]
  ; A reporter that returns the path from the start node of a given path
  ; to the final node of that path.
  let temp-path []
  ( foreach ( but-last in-path ) ( but-first in-path ) [
    [ from to_ ] ->
    ask from [
      ifelse length temp-path = 0 [
        set temp-path nw:turtles-on-weighted-path-to to_ weight
      ] [
        set temp-path sentence temp-path but-first nw:turtles-on-weighted-path-to to_ weight
        ]
      ]
    ] )
    report temp-path
end

to-report weighted-dist-of-path [ in-path ]
  let weighted-dist 0
  ( foreach ( but-last in-path ) ( but-first in-path ) [
    [ f t ] ->
    ask f [
      set weighted-dist weighted-dist + nw:weighted-distance-to t weight
    ]
    ] )
  report weighted-dist
end

一旦海龟知道它应该走哪条路，它就可以以某种方式沿着那条路走——这是一个简单的例子。

to follow-path
  if length path > 0 [
    let target first path 
    face target
    ifelse distance target > 0.5 [
      fd 0.5 
    ] [
      move-to target 
      ask target [
        set color yellow
      ]
      set path but-first path
    ]
  ]
end

所有内容都包含在 go 中，如下所示：

to go
  if not any? nodes with [ color = red ] [
   stop
  ] 
  ask walkers [
    set-path
    follow-path
  ]
  tick
end

让行为类似于：

编辑：

更简单的选择是让步行者检查最近的（按权重）目标节点，构建路径，沿着该路径行驶，然后 select 下一个最近的目标一旦到达终点那条路（等等）。但是，这可能无法给出整体最短路径 - 例如，请看下图：

绿色轨迹是路径排列步行者所走的路径。蓝色方块表示起始节点，橙色方块表示目标节点。橙色轨迹是由较简单的步行者（如上所述）拍摄的轨迹。可以看到总体来说，更简单的walker所走的路径的总权重成本更高，因为它只评估到下一个目标的加权路径，而不是整个路径的总加权成本。

NetLogo nw 扩展：如何将 nw:extension 用于多个目标

NetLogo nw extension: how to use nw:extension for multiple destination

netlogo