朱莉娅/元胞自动机：获取邻域的高效方式

Question

朱莉娅/元胞自动机：获取邻域的高效方式

4

我希望在Julia中实现元胞自动机（CA）。维度应该被包裹，这意味着：最左边的单元格的左邻居是最右边的单元格，依此类推。

一个关键问题是：如何获取一个单元格的邻居，以计算下一代的状态？由于维度应该被包裹，而Julia不允许负指数（如Python中），我有了这个想法：

考虑一个1D CA，一个世代是一个一维数组： 0 0 1 0 0 如果我们创建一个二维数组，其中第一行向右移位，第三行向左移位，像这样：

0 0 0 1 0
0 0 1 0 0
0 1 0 0 0

现在，第一列包含了第一个细胞及其邻居的状态等。

我认为这可以很容易地推广到两个或更多维度。 第一个问题: 你觉得这是一个好主意，还是错误的方向？

编辑：第一个问题的答案是否定的，第二个问题和代码示例都被舍弃了。 第二个问题：如果这个方法基本上是可行的，请看以下草图：

编辑：另一种方法是使用mod1()获取邻域索引的削减版本的1D CA。对于任何一个细胞： - A数组包含所有索引 - B数组包含所有邻居状态 - C状态转换为一个整数 - D查找下一个状态

function digits2int(digits, base=10)
   int = 0
   for digit in digits
      int = int * base + digit
   end
   return int
end

gen = [0,0,0,0,0,1,0,0,0,0,0]
rule = [0,1,1,1,1,0,0,0]

function nextgen(gen, rule)
  values = [mod1.(x .+ [-1,0,1], size(gen)) for x in 1:length(gen)] # A
  values = [gen[value] for value in values]                         # B
  values = [digits2int(value, 2) for value in values]               # C
  values = [rule[value+1] for value in values]                      # D
  return values
end

for _ in 1:100
  global gen
  println(gen)
  gen = nextgen(gen, rule)
end

下一步应该是将其扩展到二维，现在将尝试...

- universal_amateur

2个回答

2

通常情况下，如果细胞自动机的细胞仅依赖于它们旁边的细胞，那么最简单的方法就是通过将最后一个元素添加到前面和第一个元素添加到后面来“包装”向量，进行模拟，然后通过再次取出第一个和最后一个元素来“解包”，使结果长度与开始的数组长度相同。对于一维情况：

const lines = 10
const start = ".........#........."
const rules = [90, 30, 14]

rule2poss(rule) = [rule & (1 << (i - 1)) != 0 for i in 1:8]

cells2bools(cells) = [cells[i] == '#' for i in 1:length(cells)]

bools2cells(bset) = prod([bset[i] ? "#" : "." for i in 1:length(bset)])

function transform(bset, ruleposs)
    newbset = map(x->ruleposs[x],
        [bset[i + 1] * 4 + bset[i] * 2 + bset[i - 1] + 1
        for i in 2:length(bset)-1])
    vcat(newbset[end], newbset, newbset[1])
end

const startset = cells2bools(start)

for rul in rules
    println("\nUsing Rule $rul:")
    bset = vcat(startset[end], startset, startset[1]) # wrap ends
    rp = rule2poss(rul)
    for _ in 1:lines
        println(bools2cells(bset[2:end-1]))  # unwrap ends
        bset = transform(bset, rp)
    end
end

只要在模拟中使用相邻单元格，对于任何给定的单元格，这是正确的。

如果将其扩展到二维矩阵，则还应该将第一行和最后一行以及第一列和最后一列等进行“包装”。

- Bill

根据我的经验，这种方法通常用于在分布式计算中使用（因此您必须将数组分割成多个子数组并在不同的进程上运行）。然而，它有一个代价，就是每次更新边缘单元格后都必须同步值。 - Bogumił Kamiński

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bogumił Kamiński · Accepted Answer

通常我会使用mod1函数来进行环绕索引。

采用这种方法，无论您的数组a的维度是多少，当您想要从位置x移动dx时，只需编写mod1(x+dx, size(a, 1))即可，如果x是一个数组的第一维。

以下是在二维环面上进行随机游走并计算给定单元格被访问的次数的简单示例（这里我还使用广播处理所有维度的表达式）：

function randomwalk()
    a = zeros(Int, 8, 8)
    pos = (1,1)
    for _ in 1:10^6
        # Von Neumann neighborhood
        dpos = rand(((1,0), (-1,0), (0,1), (0,-1)))
        pos = mod1.(pos .+ dpos, size(a))
        a[pos...] += 1
    end
    a
end