Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como resolver o slide puzzle-15 usando backtracking?

+1 voto
487 visitas
perguntada Mai 31, 2016 em Ciência da Computação por Marcleiton Morais (21 pontos)  

Resolva o slide puzzle-15 usando backtracking. Discuta a sua solucao para o problema.

Compartilhe

1 Resposta

+1 voto
respondida Mai 31, 2016 por Marcleiton Morais (21 pontos)  

Inicialmente implementei um algoritmo de busca em profundidade transversal como uma forma de bracktracking, expandindo o "grafo" por meio dos possíveis movimentos do estado atual, gerando filhos a serem visitados. Porém, o algoritmo avançava erroneamente apenas sobre estados em que a quantidade de valores deslocados era menor, considerando uma heurística que computava tais valores. Com a orientação do professor, implementei alterações considerando o algoritmo A* e fazendo uso de uma heurística que computa a chamada distância de Manhattan. No algoritmo final, a cada ponto do grafo, define-se um novo caminho a partir da distância já percorrida e a distância a se percorrer no novo estado descontada a distância percorrida no nó final. Isso ocorre enquanto o estado do nó final não se iguala ao estado objetivo. O algoritmo faz uso de duas funções auxiliares, uma função (mover), que gera uma lista dos movimentos possíveis diante de um estado do puzzle, e uma função heurística que retorna a distância de Manhattan.

import pprint
pp = pprint.PrettyPrinter(indent=4)

def puzzleBacktracking(estadoAtual,objetivo):
    nivel = [[heuristica(estadoAtual), estadoAtual]]
    expandido = []
    nosExpandidos=0
    while nivel:
        i = 0
        for j in range(1, len(nivel)):
            if nivel[i][0] > nivel[j][0]:
                i = j
        caminho = nivel[i]
        nivel = nivel[:i] + nivel[i+1:]
        noFinal = caminho[-1]
        if noFinal == objetivo:
            break
        if noFinal in expandido: continue
        for k in mover(noFinal):
            if k in expandido: continue
            novoCaminho = [caminho[0] + heuristica(k) - heuristica(noFinal)] + caminho[1:] + [k]
            nivel.append(novoCaminho)
            expandido.append(noFinal)
        nosExpandidos += 1 
    print "Total de nós expandidos:", nosExpandidos
    print "Solução:"
    pp.pprint(caminho)

def heuristica(puzzle):
    distanciaManhattanTotal = 0
    m = eval(puzzle)          
    for i in range(4):
        for j in range(4):
            if m[i][j] == 0: continue
            distanciaManhattanTotal += abs(i - (m[i][j]/4)) + abs(j -  (m[i][j]%4));
    return distanciaManhattanTotal

def mover(puzzle):
    listaMovimentos = []  
    m = eval(puzzle)
    i = 0
    while 0 not in m[i]: i += 1
    j = m[i].index(0);
    if i > 0:                                   
      m[i][j], m[i-1][j] = m[i-1][j], m[i][j];
      listaMovimentos.append(str(m))
      m[i][j], m[i-1][j] = m[i-1][j], m[i][j]; 
    if i < 3:                                   
      m[i][j], m[i+1][j] = m[i+1][j], m[i][j]
      listaMovimentos.append(str(m))
      m[i][j], m[i+1][j] = m[i+1][j], m[i][j]
    if j > 0:                                                      
      m[i][j], m[i][j-1] = m[i][j-1], m[i][j]
      listaMovimentos.append(str(m))
      m[i][j], m[i][j-1] = m[i][j-1], m[i][j]
    if j < 3:                                   
      m[i][j], m[i][j+1] = m[i][j+1], m[i][j]
      listaMovimentos.append(str(m))
      m[i][j], m[i][j+1] = m[i][j+1], m[i][j]
    return listaMovimentos

if __name__ == '__main__':
    estadoAtual = str([[1, 2, 6, 3],[4, 9, 5, 8], [7, 13, 11, 15],[12, 14, 0, 10]])
    objetivo = str([[0, 1, 2, 3],[4, 5, 6, 7], [8, 9, 10, 11],[12, 13, 14, 15]])
    puzzleBacktracking(estadoAtual,objetivo)
...