algorithm - Netlogo - 根据曼哈顿距离找到最近的代理

问题描述

我正在为大型仓库操作建模（见下图）。

我在每个补丁（绿点）上实现了一个顶点并将它们链接起来，以便我可以计算从每个顶点到所有其他顶点的最短路径（使用 dijkstra 算法），存储在每个顶点的表（字典）中。此过程在设置阶段完成，非常耗时。然后黄色库存单元格（矩形）将发出任务完成的需求请求。

叉车（一些在路径中）假设它不忙时停留在顶点（节点）之一。当得到需求请求时，它会询问它当前的常设顶点（节点）来获取它要去的库存单元的starting_node和end_node。然后叉车要求starting_node从它的表中获取最短路径以获得最短路径（节点的组合）并驱动到end_node（黄色单元格）。

目前，黄色牢房只是在仓库里随意挑选免费的叉车。作为进一步的开发，我想添加允许黄色单元格根据实际距离（不是 Netlogo 中内置的欧几里德距离）识别离它最近的空闲卡车的功能。由于有很多卡车，所以使用“foreach”循环遍历所有可用的卡车并使用上述方法计算实际距离并不好。您可以使用原始的“距离自己”来快速定位卡车，但这并不准确。有没有一种用更快的计算方法来识别最近的卡车的好方法？

标签： algorithmnetlogodijkstra

我不知道这是否适用于您当前的设置，但您可能会发现该nw扩展程序很有帮助。例如，试试这个设置（我为长度道歉，只是近似你的世界）：

extensions [ nw ]

breed [ nodes node ]
breed [ trucks truck ]
breed [ cells cell ]

to setup
  ca

  resize-world -29 29 -14 14

  ask patches with [ ( pxcor mod 5 = 0 or pycor = 0 ) ] [
    set pcolor grey 
    sprout-nodes 1 [
      set size 0.5
      set shape "circle"
      set color green
    ]
  ]

  ask nodes [
    create-links-with turtles-on neighbors4 [
      set color green  
    ]
  ]

  ask n-of 5 nodes [
    hatch 1 [
      set size 1
      set color red
      set breed trucks 
      set shape "car"
    ]
  ]

  ask n-of 2 trucks [
    set color blue
  ]

  ask one-of nodes [
    ask one-of neighbors with [ pcolor = black ] [
      sprout-cells 1 [
        set size 1.5
        set shape "box"
        set color yellow
      ]
    ]
  ]
  reset-ticks
end

给出一个像这样的简单世界：

您可以使用nw扩展程序即时计算距离，而不是将它们存储在每个单元格表中，并让叉车（此处为卡车）遵循最短路径。评论中的更多细节：

to summon-nearest-truck 
  ; Treat blue trucks as 'empty' and ready to go to a cell
  let ready-trucks trucks with [ color = blue ]

  ; Get the nodes associated with those ready trucks
  let truck-proxies turtle-set map [ i -> [nodes-on patch-here] of i ] sort ready-trucks

  ; Randomly ask one of the cells to
  ask one-of cells [

    ; Choose one of the neighboring road nodes as a proxy for distance calculation
    let node-proxy one-of nodes-on neighbors4 

    ; Get the node proxy to:
    ask node-proxy [
      ; Find the nearest (by network distance) trucks, and select the node
      ; located on the same patch as that truck
      let my-truck-proxy min-one-of truck-proxies [length ( nw:turtles-on-path-to myself) ]

      ; Get that truck-proxy node to generate the path to the original asking node
      ; and have the appropriate truck follow that path
      ask my-truck-proxy [
        ; Generate the path to follow
        let path-to-follow nw:turtles-on-path-to myself

        ; Highlight that path for visualization
        ask turtle-set path-to-follow [
          set color orange
        ]

        ; Get the truck ready to move
        let ready-truck one-of trucks-here with [ color = blue ]
        ask ready-truck[
          set color yellow
        ]

        ; Move that truck along the path-to-follow
        ask ready-truck [
          foreach path-to-follow [
            n ->
            face n
            move-to n
            ; For visualization only
            wait 0.1
          ]
        ]
      ]
    ]
  ]
end

这使黄色框根据nw:turtles-on-path-to返回的长度召唤最近的卡车。那辆卡车沿着通往召唤节点的路径：

algorithm - Netlogo - 根据曼哈顿距离找到最近的代理

问题描述

解决方案

推荐阅读