Giải quyết 15 câu đố với Julia

Question

Hỏi ở đây thay vì SO như đề xuất.

Tôi đang cố gắng sử dụng Julia để giải các trò chơi xếp hình chung 15 Câu đố bằng cách sử dụng Julia bằng thuật toán A *. Tôi còn khá mới với ngôn ngữ và phong cách của tôi có vẻ rất giống C. Khi tôi thử mã sau, tôi hết bộ nhớ. Tôi không chắc liệu nó có liên quan đến việc sử dụng kiểu con trỏ trong cấu trúc của tôi hay chỉ là thiết kế tồi.

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")

Answer 1

Đó là một bài tập thú vị để làm việc! Tôi hoàn toàn cấu trúc lại mã; vấn đề phức tạp cơ bản mà Marc đề cập vẫn còn tồn tại.

Tôi giới thiệu bài đăng trên blog này cho các thủ thuật lập chỉ mục theo chủ đề 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

Một cải tiến thú vị là sử dụng đa luồng để xử lý hàng đợi. Và người ta có lẽ cũng có thể tránh hoàn toàn việc lưu trữ bảng dưới dạng ma trận bằng cách chuyển sang biểu diễn mã vạch ở khắp mọi nơi (về cơ bản, một bitvector trên cơ sở tổng quát) - cả hai đều để lại như một bài tập. Mặc dù vậy, thậm chí còn có mã hóa succinter cho permuations .

Tôi đã thử chạy sự cố 50 lần di chuyển, nhưng đã giết chương trình ở mức 1 GiB.

Answer 2

Có vẻ như bạn lưu trữ bảng sau mỗi chuyển động cho mỗi khả năng, đó là rất nhiều mảng trong bộ nhớ, không có gì lạ khi nó lấp đầy bộ nhớ của bạn

đối với ví dụ thứ hai, mã của bạn tìm kiếm 157523 vị trí, chiếm một nửa tổng số khả năng.

số lượng hoán vị cho 1:16là rất lớn, thuật toán a-sao có lẽ không đủ

ngay cả khi bạn chỉ nhìn vào 1% tổng số khả năng, bạn sẽ cần hàng trăm gigabyte nếu không phải là terabyte để lưu trữ chúng

[6, 5, 4, 1, 7, 3, 9, 8, 2] solved in 26 moves after looking at 157523 positions

julia> using Combinatorics

julia> length(permutations(1:9))
362880

julia> length(permutations(1:16))
20922789888000