朱莉娅的自我回避漫步

Question

我正在尝试编写 Julia 中的自我回避行走代码，这是我的代码：
这里我定义了NxN矩阵中的position函数

function position(vertical, horizontal, N)
            
    ud = BitArray(a == vertical  for a = 1:N )              # Goes up or down
    lr = transpose(BitArray(a == horizontal  for a = 1:N )) # Goes left or right

    return ud * lr
end

这是描述矩阵内部运动的助行器代码，其中 1 表示助行器一直在该位置，0 表示它从未到过。（另外，walker是不允许斜着走的，这部分我写对了）

using StatsBase, LinearAlgebra

function SAW(N, Iterations=5) # SAW, Self Avoiding Walk
    
    x = ceil(N/2) 
    y = ceil(N/2)
    Mat = zeros(Int8, N , N)
    pos = zeros(Int8, N , N)
       
    for i in 1:Iterations
        
        RandomOnes = sample(-1:2:1, 2, replace = false)[1]  #gives the values -1 or 1
        ZeroOne = sample(0:1, 1, replace = false)[1]   #gives the values 0 or 1
    
        
        # In order to avoid moving diagonally, only one of the two variables (x,y)
        # can have the values 1 or -1, the other one has to be 0 (e.g. if x = 1 then y = 0)       
        if ZeroOne == 1 
            x += RandomOnes
            y += 0
        else
            x += 0
            y += RandomOnes
        end
               
        Mat += position(y,x,N)
        pos  = position(y,x,N)
    end
    
    for i in 1:N
        for j in 1:N
            if Mat[i,j] > 1
                Mat[i,j] += 1 # Here the process should restart, because the walker ran into itself
            end
        end
    end
                
    return Mat, pos
end

SAW(7)[1]

我不知道walker遇到自己时如何重启进程

Answer 1

这里有一些您可能会觉得有用的东西。这是一个假设您的格子可能非常大的解决方案（因此按照您的方法存储矩阵将不适合内存）。为了简单起见，我没有优化它：

function SAW(N::Integer, Iterations::Integer)
    @assert N >= 1
    @assert Iterations >= 0
    # this will store the path we have traversed
    path = Tuple{Int, Int}[]
    cur = ((N+1) ÷ 2, (N+1) ÷ 2)
    push!(path, cur)
    for i in 1:Iterations
        x, y = cur
        # now check the four possible movement directions
        # store moves that are allowed in valid vector
        valid = Tuple{Int, Int}[]
        if x > 1 && !((x-1, y) in path)
            push!(valid, (x-1, y))
        end
        if x < N && !((x+1, y) in path)
            push!(valid, (x+1, y))
        end
        if y > 1 && !((x, y-1) in path)
            push!(valid, (x, y-1))
        end
        if y < N && !((x, y+1) in path)
            push!(valid, (x, y+1))
        end
        if isempty(valid)
            # we are stuck and failed to generate a walk of length N
            # no moves are possible and we still have not made N moves
            return nothing
        end
        # randomly pick a move from valid moves
        cur = rand(valid)
        push!(path, cur)
    end
    # we have successfully generated the walk - return it
    return path
end

很明显，这段代码可以很容易地变得更快，但我不想让它复杂化。此外，您可能希望生成的行走具有不同的分布（即此代码可能会生成所有可能的行走，但模拟过程假设它们有一个特定的分布）——同样可以更改。

编辑：

将结果存储在矩阵中的最简单方法是：

julia> N = 10
10

julia> Iterations = 5
5

julia> path = SAW(N, Iterations)
6-element Vector{Tuple{Int64, Int64}}:
 (5, 5)
 (4, 5)
 (3, 5)
 (3, 6)
 (3, 7)
 (4, 7)

julia> m = zeros(Int, N, N)
10×10 Matrix{Int64}:
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0

julia> foreach(p -> m[p...] = 1, path)

julia> m
10×10 Matrix{Int64}:
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  1  1  1  0  0  0
 0  0  0  0  1  0  1  0  0  0
 0  0  0  0  1  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0  0  0

（假设 N 较小）

朱莉娅的自我回避漫步

Self Avoiding Walk in Julia

linear-algebra

julia

random-walk