TALLER BACKTRACKING Y RECURSIVIDAD

TALLER
 BACKTRACKING
 Y
 RECURSIVIDAD
 

 
En
  la
  guerra
  de
  los
  “Kbots”
  se
  han
  diseñado
  robots
  que
  permiten
  explorar
  caminos
 
seguros  en
  campos
  minados.
  Los
  Humanos
  deben
  caminar
  por
  este
  campo
  minado
 
buscando
  documentos
  secretos
  que
  están
  ubicados
  en
  algún  lugar
  del
  campo.
  La
 
misión
 de
 estos
 robots
 es
 indicar
 cual
 es
 el
 camino
 más
 seguro,
 además
 de
 informar
 en
 
que
  posiciones
 están
  las
  minas
  para
  que
  los
  exploradores
  humanos
  no
  las
  pisen
  y
 
puedan
 cumplir
 con
 su
 objetivo.
 

 
En
  este
  campo
  minado
 existen
  alambres
  de
  púas
  que
  no
  pueden
  ser
  sobrepasados,
 
espacios
 seguros
 de
 camino,
 minas,
 el
 lugar
 donde
 están
 los
 exploradores humanos
 y
 
el
 lugar
 donde
 se
 encuentran
 los
 documentos
 secretos
 por
 ejemplo:
 

 


 

PPPPPMPPMM
PESSSSMSSP
SSSPPPPSSS
SMSSPPPMSM
SSSSSDSSMS
PPPSSSSMSS
SSMSMSMSMSDonde
  E
  representa
  la
  posición
  en
  la
  que
  los
  exploradores
  están,
  P
  identifica
  la
 
existencia
 de
 púas,
 M
 indica
 la
 existencia de
 una
 mina
 y
 D
 indica
 el
 lugar
 donde
 están
 
los
 documentos
 secretos.
 

 
Los
  robots
  solo
  se
  mueven
  en
  línea
  recta,
  es
 decir
  jamás
  en
  diagonal,
  considerando
 
estas
  condiciones
  encuentra
  el
  camino
  mas
  seguro
  de
  exploración.
  Tomando
  en
 
cuenta
 el
 ejemplo anterior,
 el
 camino
 mas
 seguro
 será:
 

 

(R,S), (D,S), (D,S), (D,S), (R,S), (R,S), (R, D)

 
En
 este
 caso
 se
 ha
 encontrado
 un
 camino
 sin
 minas,...