Résoudre 15Puzzle avec Julia

Sep 03 2020

Demander ici au lieu de SO comme suggéré.

J'essaie d'utiliser Julia pour résoudre le jeu de tuiles commun 15 Puzzle en utilisant Julia en utilisant l'algorithme A *. Je suis assez nouveau dans la langue et mon style peut sembler très C. Lorsque j'essaye le code suivant, je manque de mémoire. Je ne sais pas si cela est lié à l'utilisation d'un style de pointeur dans mes structures ou simplement à une mauvaise conception.

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

Réponses

3 phipsgabler Oct 11 2020 at 15:23

C'était un exercice amusant sur lequel travailler! J'ai complètement remanié le code; la question fondamentale de la complexité que Marc mentionne tient toujours.

Je recommande ce billet de blog pour les astuces d'indexation cartésiennes.

# 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

Une amélioration intéressante serait d'utiliser le multithreading pour traiter la file d'attente. Et on pourrait probablement aussi éviter complètement de stocker la carte en tant que matrice en passant à la représentation de code à barres partout (en gros, un bitvector dans une base généralisée) - les deux sont laissés comme un exercice. Cependant, il existe même des codages succincts pour les permuations .

J'ai essayé d'exécuter le problème de 50 coups, mais j'ai tué le programme à 1 Gio.

3 MarcMush Sep 10 2020 at 09:47

On dirait que vous stockez la carte après chaque mouvement pour chaque possibilité, c'est beaucoup de tableaux en mémoire, pas étonnant que cela remplisse votre mémoire

pour votre deuxième exemple, votre code recherche 157523 positions, ce qui représente la moitié des possibilités totales.

le nombre de permutations pour 1:16est énorme, l'algorithme a-star n'est probablement pas suffisant

même si vous ne regardez que 1% des possibilités totales, vous auriez besoin de centaines de gigaoctets sinon de téraoctets pour les stocker

[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