У меня есть проблема со временем при получении списка размеров (количества исправлений) кластеров в среде исправлений (цветные области) в модели NetLogo. Для небольших значений сетки (размер мира в NetLogo), таких как 50 x 50, 100 x 100 или даже 150 x 150, стандартная DFS BFS становится эффективной, но по мере увеличения порядка эти процедуры становятся невозможными. Моя задача — вычислить те же результаты, но для сеток с патчами не менее 10000 x 10000 или выше.
Я попробовал Union-Find с алгоритмом Хошена-Копельмана, но моя настоящая реализация NetLogo тратит около 5 часов на сетку патчей порядка 500 x 500.
Кто-нибудь знает какой-либо алгоритм для вычисления или маркировки кластеров для миров по крайней мере 1000 х 1000 патчей?
Могу ли я получить некоторое улучшение, если вместо использования патчей и Netlogo я переключусь на C / C ++ или другой язык программирования?
Любое предложение?
Заранее спасибо,
Отличный день
Мой код в основном это модель Кластеры с рекурсией.
Модель находит кластеры очень хорошо, когда кластеры имеют умеренный размер, но если ваша процедура установки генерирует большие кластеры, тогда рекурсия говорит «слишком глубокая рекурсия» и не сообщает о результатах, теперь мой первоначальный вопрос можно перефразировать, как этого избежать »recursio слишком глубоко «с нетлого?
Нетлог код:
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
Других решений пока нет …