Memecahkan 15Puzzle dengan Julia

Sep 03 2020

Bertanya di sini, bukan SO seperti yang disarankan.

Saya mencoba menggunakan Julia untuk memecahkan permainan ubin umum 15 Puzzle menggunakan Julia menggunakan algoritma A *. Saya cukup baru dalam bahasa ini dan gaya saya mungkin terlihat sangat mirip C. Ketika saya mencoba kode berikut, saya kehabisan memori. Saya tidak yakin apakah ini terkait dengan penggunaan gaya penunjuk di struct saya atau hanya desain yang buruk.

struct Node
    parent
    f::Int64
    board::Array{Int64,1}
end

function findblank(A::Array{Int64,1})
    x = size(A,1)
    for i = 1:x
        if A[i] == x
            return i
        end
    end
    return -1
end

function up(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    blank = findblank(A)
    B = copy(A)
    if blank / Nsq <= 1
        return nothing
    end
    B[blank-Nsq],B[blank] = B[blank],B[blank-Nsq]
    return B
end

function down(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    blank = findblank(A)
    B = copy(A)
    if (blank / Nsq) > (Nsq -1)
        return nothing
    end
    B[blank+Nsq],B[blank] = B[blank],B[blank+Nsq]
    return B
end

function left(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    blank = findblank(A)
    B = copy(A)
    if (blank % Nsq) == 1
        return nothing
    end
    B[blank-1],B[blank] = B[blank],B[blank-1]
    return B
end

function right(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    blank = findblank(A)
    B = copy(A)
    if (blank % Nsq) == 0
        return nothing
    end
    B[blank+1],B[blank] = B[blank],B[blank+1]
    return B
end

function manhattan(A::Array{Int64,1})
    N = size(A,1)
    Nsq = isqrt(N)
    r = 0
    for i in 1:N
        if (A[i]==i || A[i]==N)
            continue
        end
        row1 = floor((A[i]-1) / Nsq)
        col1 = (A[i]-1) % Nsq
        row2 = floor((i-1) / Nsq)
        col2 = (i-1) % Nsq
        r+= abs(row1 - row2) + abs(col1 - col2)
    end
    return r
end  

# start = [1,2,3,4,5,6,7,9,8]
# start = [6,5,4,1,7,3,9,8,2] #26 moves
start = [7,8,4,11,12,14,10,15,16,5,3,13,2,1,9,6] # 50 moves
goal = [x for x in 1:length(start)]
# println("The manhattan distance of $start is $(manhattan(start))")
g = 0
f = g + manhattan(start)
pq = PriorityQueue()
actions = [up,down,left,right]
dd = Dict{Array{Int64,1},Int64}()
snode = Node(C_NULL,f,start)
enqueue!(pq,snode,f)
pos_seen = 0
moves = 0
while (!isempty(pq))
    current = dequeue!(pq)
    if haskey(dd,current.board)
        continue
    else
        push!(dd, current.board =>current.f)
    end
    if (current.board == goal)
        while(current.board != start)
            println(current.board)
            global moves +=1
            current = current.parent[]
        end
        println(start)
        println("$start solved in $moves moves after looking at $pos_seen positions")
        break
    end
    global pos_seen+=1
    global g+=1
    for i in 1:4
        nextmove = actions[i](current.board)
        if (nextmove === nothing || nextmove == current.board || haskey(dd,nextmove))
            continue
        else
            global f = g+manhattan(nextmove)
            n = Node(Ref(current),f,nextmove)
            enqueue!(pq,n,f)
        end
    end
end
println("END")

Jawaban

3 phipsgabler Oct 11 2020 at 15:23

Itu adalah latihan yang menyenangkan untuk dikerjakan! Saya benar-benar mengubah kode; masalah kompleksitas dasar yang disebutkan Marc masih berlaku.

Saya merekomendasikan posting blog ini untuk trik pengindeksan cartesian.

# we need this include
using DataStructures


# let's define some constants -- barcode is explained below
const Barcode = Int64 # can be switche out for a larger type if necessary
const Board = Matrix{Int64}

# assuming `board` is a square matrix
boardsize(board) = size(board, 1)

# shorter version, altough we get rid of this below
# by storing the blank position instead of recalculating
findblank(board) = findfirst(==(length(board)), board)

# save some array allocation: instead of hashing, we can directly 
# encode each board permutation in a sufficiently large integer
# by using the length of the board as basis of a number system
function barcode(board)
    s = one(Barcode) # be type stable!
    bc = zero(Barcode)
    base = length(board)
    
    for n in board
        bc += n * s
        s *= base
    end

    return bc
end

# those four function can be generalized.  we conveniently use 
# `CartesianIndex`s here, as in `manhattan`.
function try_move(board, blank, action)
    delta = CartesianIndex(action...)
    moved = blank + delta
    
    if !checkbounds(Bool, board, moved)
        return nothing
    else
        new_board = copy(board)
        new_board[blank], new_board[moved] = new_board[moved], new_board[blank]
        return new_board, moved
    end
end

# I think I got this right... since we store the board as a matrix 
# anyway, we can directly access the indices.
function manhattan(board)
    N = boardsize(board)
    
    return sum(CartesianIndices(board)) do ix
        row1, col1 = Tuple(ix)
        col2, row2 = divrem(board[ix] - 1, N) .+ 1 # column major!
        abs(row1 - row2) + abs(col1 - col2)
    end
end


# redo some things.  storing the `f` here is not necessary; on the 
# other hand, we can get rid of recalculating the blank position and 
# and simply store it here, after every move.
# the parent can become a small `Union`, no need for pointers
# (never use `C_NULL` unless for interop!)
# the barcodes also only need to be calculated once
struct Node
    board::Board
    blank::CartesianIndex
    parent::Union{Node, Nothing}
    barcode::Barcode

    function Node(
        board::Board,
        blank::CartesianIndex,
        parent::Union{Node, Nothing}
    )
        @assert size(board, 1) == size(board, 2)
        return new(board, blank, parent, barcode(board))
    end
end

Node(board, blank) = Node(board, blank, nothing)

# factor out this loop into its own function -- it is not part of the 
# solution, but needed only once the solution is found
function backtrace(node)
    current_node = node
    trace = Board[current_node.board]
    
    while !isnothing(current_node.parent)
        current_node = current_node.parent
        push!(trace, current_node.board)
    end

    return reverse(trace)
end


# since this remains global, make it a constant. also, it is of known
# size and immutable, so a tuple is better
const ACTIONS = ((+1, 0), (-1, 0), (0, -1), (0, +1))

function try_solve(start_board, goal_board)
    g = 0
    
    pq = PriorityQueue()
    start_node = Node(start_board, findblank(start_board))
    
    enqueue!(pq, start_node, manhattan(start_board))
    seen_barcodes = Set{Barcode}([start_node.barcode])
    goal_barcode = barcode(goal_board)

    # early return, since otherwise we only check immediately
    # after a move
    (start_node.barcode == goal_barcode) && return start_node, 1
    
    while !isempty(pq)
        g += 1
        current_node = dequeue!(pq)
        
        for action in ACTIONS
            move_result = try_move(current_node.board, current_node.blank, action)
            
            if !isnothing(move_result)
                moved_board, new_blank = move_result
                new_node = Node(moved_board, new_blank, current_node)
                
                if new_node.barcode == goal_barcode
                    return new_node, length(seen_barcodes)
                elseif new_node.barcode ∉ seen_barcodes
                    f = g + manhattan(moved_board)
                    enqueue!(pq, new_node, f)
                    push!(seen_barcodes, new_node.barcode)
                end
            end
        end
    end

    # I tried to keep `print`s out of the calculation function; this
    # one's useful for debugging, though:
    # println("Tried $(length(seen_barcodes)) boards") return nothing end # put main code into a function -- always put as many things into # functions as possible function main() # Again, Julia matrices are column major, so I needed to # transpose the boards to meaningfully work with the indexing # 0 moves # start_board = [ # 1 4 7 # 2 5 8 # 3 6 9 # ] # 4 moves # start_board = [ # 1 9 4 # 2 5 7 # 3 6 8 # ] # 26 moves # start_board = [ # 6 1 9 # 5 7 8 # 4 3 2 # ] # 50 moves start_board = [ 7 12 16 2 8 14 5 1 4 10 3 9 11 15 13 6 ] # quick way to initialize the reference matrix goal_board = reshape(1:length(start_board), size(start_board)) println("The manhattan distance of the start board is $(manhattan(start_board))")
    
    # let's also print some time and memory statistics
    @time solution = try_solve(start_board, goal_board)
    
    if !isnothing(solution)
        solution_node, pos_seen = solution
        trace = backtrace(solution_node)

        println("Solved puzzle in $(length(trace)) moves after looking at $pos_seen positions.  Steps: ")
        foreach(println, trace)
    else
        println("Failed to solve puzzle")
        println(start_board)
    end
end

# corresponds to `if __name__ == __main__` in Python; only run
# `main()` when called as a script
if abspath(PROGRAM_FILE) == @__FILE__
    main()
end

Perbaikan keren akan menggunakan multithreading untuk memproses antrian. Dan orang mungkin juga dapat sepenuhnya menghindari penyimpanan papan sebagai matriks dengan beralih ke representasi barcode di mana-mana (pada dasarnya, bitvector secara umum) - keduanya dibiarkan sebagai latihan. Bahkan ada kode succinter untuk permuasi .