elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Top 20 herramientas Hacking más populares de 2020


+  Foro de elhacker.net
|-+  Programación
| |-+  Scripting
| | |-+  Backtracking
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Backtracking  (Leído 1,068 veces)
HastatusXXI

Desconectado Desconectado

Mensajes: 8



Ver Perfil
Backtracking
« en: 14 Julio 2017, 20:53 pm »

Hola. He intentado resolver el problema del 15-puzzle del Juez de la UVa en Python mediante backtracking (el problema en cuestión es este: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=36&page=show_problem&problem=1122). El problema está en que se supone que cada solución está limitada a un máximo de 50 pasos, pero el vector solución crece hasta más de 140 pasos en la mayor parte de las iteraciones, por lo que el programa no encuentra la solución en un tiempo razonable. Adjunto el código del programa completo, pero solo es necesario mirar el método backtracking (sé que nadie va a estudiar un código tan largo, pero tampoco hace falta). Solo debería generarse un movimiento como máximo en cada llamada a backtracking, y si la rama no tiene más nodos intermedios debería volver al estado anterior y borrar del vector solución el último movimiento. La condición 
Código
  1. if(a[k] != mov_inv[c[i]]):
sirve para evitar deshacer movimientos ¿Alguien puede decirme por qué el vector solución crece más allá de los 50 elementos? (Cabe decir, que efectivamente, k no sobrepasa nunca el valor 50).

Código
  1.  
  2. moves = {0:('R','D'),1:('R','L','D'),2:('R','L','D'),3:('L','D'),4:('R','D','U'),5:('R','L','D','U'),
  3.         6:('R','L','D','U'),7:('L','U','D'),8:('R','D','U'),9:('R','L','D','U'),10:('R','L','D','U'),
  4.         11:('L','U','D'),12:('U','R'),13:('L','U','R'),14:('L','U','R'),15:('U','L')}
  5.  
  6. mov_inv = {'U':'D','D':'U','R':'L','L':'R'}
  7.  
  8.  
  9. def backtracking(a,k,tab):
  10.    c = []
  11.    if is_solution(tab):
  12.        process_solution(a)
  13.    elif k < 51:
  14.        print a
  15.        c = construct_candidates(tab)
  16.        for i in range(len(c)):
  17.            if(a[k] != mov_inv[c[i]]):
  18.                a.append(c[i])
  19.                make_move(tab,a[k+1])
  20.                backtracking(a,k+1,tab)
  21.                unmake_move(tab,a[k+1])
  22.                a = a[:-1]
  23.  
  24. def inversions(a):
  25.    n_inv = 0
  26.    a_copy = a[:]
  27.    a_copy.remove(0)
  28.  
  29.    for i in range(len(a_copy)):
  30.        for j in range(i,len(a_copy)):
  31.            if a_copy[i] > a_copy[j]:
  32.                n_inv = n_inv + 1
  33.  
  34.    return n_inv
  35.  
  36. def is_solvable(a):
  37.    n_inv = inversions(a)
  38.    if ((a.index(0) % 4) % 2) == 0 and n_inv % 2 == 0:
  39.        return True
  40.    if ((a.index(0) % 4) % 2) == 1 and n_inv % 2 == 1:
  41.        return True
  42.    return False
  43.  
  44.  
  45. def construct_candidates(tab):
  46.    i = tab.index(0)
  47.    m = moves[i]
  48.    c = []
  49.    for j in range(len(m)):
  50.        c.append(m[j])
  51.    return c
  52.  
  53. def make_move(tab,m):
  54.    i = tab.index(0)
  55.    if m == 'U':
  56.        c = tab[i-4]
  57.        tab[i-4] = 0
  58.        tab[i] = c
  59.    elif m == 'D':
  60.        c = tab[i+4]
  61.        tab[i+4] = 0
  62.        tab[i] = c
  63.    elif m == 'L':
  64.        c = tab[i-1]
  65.        tab[i-1] = 0
  66.        tab[i] = c
  67.    elif m == 'R':
  68.        c = tab[i+1]
  69.        tab[i+1] = 0
  70.        tab[i] = c
  71.  
  72. def unmake_move(tab,m):
  73.    make_move(tab,mov_inv[m])
  74.  
  75. def is_solution(tab):
  76.    if(tab[15] != 0):
  77.        return False
  78.    else:
  79.        for i in range(len(tab)-1):
  80.            if tab[i] != i+1:
  81.                return False
  82.    return True
  83.  
  84. def process_solution(a):
  85.    print a
  86.  
  87. a = [-1]
  88. tab = [2,3,4,0,
  89.       1,5,7,8,
  90.       9,6,10,12,
  91.       13,14,11,15]
  92.  
  93.  
  94. if not is_solvable(tab):
  95.    print "This puzzle is not solvable"
  96. else:
  97.    backtracking(a,0,tab)


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Recursividad y Backtracking!!!!
Java
bwsr 2 7,275 Último mensaje 28 Junio 2007, 00:40 am
por bwsr
Backtracking - Laberinto
Programación C/C++
hadree 3 4,767 Último mensaje 23 Noviembre 2010, 03:08 am
por do-while
[Reto] Backtracking - Laberinto
.NET (C#, VB.NET, ASP)
hadree 7 11,409 Último mensaje 17 Diciembre 2010, 13:35 pm
por pisa2
BACKTRACKING CIRCUITO HAMILTONIANO
Programación C/C++
yeah_2796 1 1,472 Último mensaje 23 Mayo 2015, 11:19 am
por Stakewinner00
Problema en ejercicio de backtracking
Programación General
xXJoSe13Xx 0 484 Último mensaje 3 Noviembre 2018, 18:15 pm
por xXJoSe13Xx
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines