c++ - 测量大型方形网格中的簇有哪些好的替代方法？

Question

我在获取 NetLogo 模型中补丁环境(彩色区域)中簇的大小(补丁数量)列表时遇到了时间问题。对于小网格值(NetLogo 中的世界大小)如 50 x 50、100 x 100 甚至 150 x 150，BFS 的标准 DFS 变得高效，但随着阶数的增加，这些过程变得不可行。我的任务是计算相同的结果，但网格的 block 数至少为 10000 x 10000 或更高。

我尝试使用 Hoshen-Kopelman 算法进行并查找，但我的实际 NetLogo 实现花费了大约 5 小时来处理 500 x 500 阶的补丁网格。

有人知道有什么算法可以为至少 1000 x 1000 个补丁的世界计算或标记集群吗？

如果我改用 C/C++ 或其他编程语言而不是使用补丁和 Netlogo，我可以获得一些改进吗？

有什么建议吗？

提前致谢，美好的一天

Answer 1

我的代码基本上就是这个模型Clusters with Recursion .

当集群大小适中时，模型可以很好地找到集群，但是如果您的设置过程生成大型集群，则递归会说“递归太深”并且不报告结果，现在我最初的问题可以改写，如何避免这个带有 netlogo 的“递归太深”？

Netlogo 代码:

globals [npixel caux final-participante1 final-participante2 r i j intera2 clist1 clist2 nc1 nc2]
patches-own
[
  partido influencia votoduro
  cluster  
]

to find-clusters
  loop [ 
    let seed one-of patches with [cluster = nobody] 
    if seed = nobody
    [ contarclusvar
      stop ]
    ask seed 
    [ set cluster self 
      grow-cluster ] 
  ] 
  display 
end

to setup1
  __clear-all-and-reset-ticks
ask patches [set partido 0 set influencia 0 set cluster nobody]
set npixel[]
set final-participante1 0
set final-participante2 0

set r  (L + 1)   
set-patch-size ps
resize-world 0 L 0 L

set participante2 (L + 1) * (L + 1) - participante1

set i 0
set j 0

   repeat r
  [
    repeat r
    [
    set npixel sentence npixel patch i j

    set j j + 1
    ]
    set i i + 1
    set j 0
   ]
set Caux npixel

let N r * r

repeat participante1
 [
   let z random N
   ask item z npixel [set pcolor white set partido 1 set influencia 1 set votoduro 1]
   set npixel replace-item z npixel item (N - 1 ) npixel
   set N N - 1
 ]

 repeat participante2
 [
   let z random N
   ask item z npixel [set pcolor gray set partido 2 set influencia 1 set votoduro 1]
   set npixel replace-item z npixel item (N - 1 ) npixel
   set N N - 1
 ]

;------------------- Procedure
set clist1 []
set clist2 []

let ciclos 0
let intera 0
let aux 0
let nulo 0

if participante1 + participante2 > r * r
   [stop]
let C1 participante1
let C2 participante2

repeat 75
[
  set i 0
  set j 0
  set npixel Caux

   set N r * r
   set intera 0
   set aux 0
   let aux2 (((ciclos - 1) * r * r) + intera2)              

  repeat (r * r)
 [
   let z random N 
   ask item z npixel 
   [
        let sum-inf1 sum ([influencia] of neighbors4 with [partido = 1])
        let sum-inf2 sum ([influencia] of neighbors4 with [partido = 2])


   if (sum-inf2 = sum-inf1) and (partido = 1) [ask item z npixel [set pcolor black set partido 0 set influencia 0 ] set Nulo Nulo + 1 set C1 C1 - 1 set aux aux + 1 set intera2 intera] 
   if (sum-inf2 = sum-inf1) and (partido = 2) [ask item z npixel [set pcolor black set partido 0 set influencia 0 ] set Nulo Nulo + 1 set C2 C2 - 1 set aux aux + 1 set intera2 intera]

  if ((sum-inf1 > sum-inf2) and ((partido = 2) or (partido = 0))) [
         set pcolor white set partido 1 set influencia 1
         set C1 C1 + 1 set C2 C2 - 1 set aux aux + 1 set intera2 intera
       ]

 if ((sum-inf2 > sum-inf1) and ((partido = 1) or (partido = 0))) [
       set pcolor gray set partido 2 set influencia 1
       set C2 C2 + 1 set C1 C1 - 1 set aux aux + 1 set intera2 intera
     ]

   set npixel replace-item z npixel item (N - 1 ) npixel
   set N N - 1
   set intera intera + 1
   ] 

  if (intera - aux) > (r * r) - 1  [
  stop
  ]
 ] 
] 
end

to contarclusvar
let comp []

      set comp ([cluster] of patches with [pcolor = white]) 
      set comp remove-duplicates comp 
      set nc1 length comp 

  foreach comp [ set clist1 sentence clist1 count patches with [cluster = ? and pcolor = white]
        ]
   set comp []

      set comp ([cluster] of patches with [pcolor = gray]) 
      set comp remove-duplicates comp 
      set nc2 length comp 

 foreach comp [ set clist2 sentence clist2 count patches with [cluster = ? and pcolor = gray]
      ]
end

to grow-cluster  
  ask neighbors4 with [(cluster = nobody) and (pcolor = [pcolor] of myself)]
  [ set cluster [cluster] of myself
    grow-cluster ] 
end

to show-clusters
  let counter 0
  loop [ 
    let p one-of patches with [plabel = ""] 
    if p = nobody
      [ stop ] 
    ask p
    [ ask patches with [cluster = [cluster] of myself]
      [ set plabel counter ] ]
    set counter counter + 1
  ] 
end