แก้ปัญหา 15Puzzle กับ Julia

Question

การถามที่นี่แทน SO ตามที่แนะนำ

ฉันกำลังพยายามใช้ Julia แก้เกมไพ่ทั่วไป 15 Puzzle โดยใช้ Julia โดยใช้อัลกอริทึม A * ฉันค่อนข้างใหม่กับภาษาและสไตล์ของฉันอาจดูเหมือน C มาก เมื่อฉันลองใช้รหัสต่อไปนี้หน่วยความจำไม่เพียงพอ ฉันไม่แน่ใจว่ามันเกี่ยวข้องกับการใช้สไตล์ตัวชี้ในโครงสร้างของฉันหรือแค่การออกแบบที่ไม่ดี

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

นั่นเป็นการออกกำลังกายที่น่าสนุก! ฉันปรับรหัสใหม่ทั้งหมด ปัญหาความซับซ้อนพื้นฐานที่ Marc กล่าวถึงยังคงมีอยู่

ฉันขอแนะนำบล็อกโพสต์นี้สำหรับเทคนิคการสร้างดัชนีคาร์ทีเซียน

# 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

การปรับปรุงที่ยอดเยี่ยมคือการใช้มัลติเธรดในการประมวลผลคิว และอาจหลีกเลี่ยงการจัดเก็บบอร์ดเป็นเมทริกซ์ได้อย่างสมบูรณ์โดยเปลี่ยนไปใช้การแสดงบาร์โค้ดทุกที่ (โดยทั่วไปคือบิตเวกเตอร์เป็นแบบทั่วไป) - ทั้งสองทิ้งไว้เป็นแบบฝึกหัด มีแม้กระทั่งcodings succinter สำหรับ permuationsแม้ว่า

ฉันพยายามรันปัญหา 50 ท่า แต่ฆ่าโปรแกรมที่ 1 GiB

Answer 2

ดูเหมือนว่าคุณจัดเก็บบอร์ดหลังจากการเคลื่อนไหวแต่ละครั้งสำหรับความเป็นไปได้แต่ละครั้งนั่นคืออาร์เรย์จำนวนมากในหน่วยความจำไม่น่าแปลกใจที่มันจะเต็มหน่วยความจำของคุณ

สำหรับตัวอย่างที่สองโค้ดของคุณค้นหาตำแหน่ง 157523 ซึ่งเป็นครึ่งหนึ่งของความเป็นไปได้ทั้งหมด

จำนวนการเรียงสับเปลี่ยนสำหรับ1:16เป็นจำนวนมากอัลกอริทึม a-star อาจไม่เพียงพอ

แม้ว่าคุณจะดูเพียง 1% ของความเป็นไปได้ทั้งหมด แต่คุณก็ต้องมีหลายร้อยกิกะไบต์หากไม่ใช่เทราไบต์เพื่อจัดเก็บ

[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