{*****************************************************************}

{*                   Algoritmos de búsqueda                      *}

{* Para que se entienda mejor , se ha concretado un problema que *}

{* consiste en buscar el camino que debe seguir un caballo en un *}

{* tablero de ajedrez para llegar desde una posición inicial a   *}

{* una posición final . La estructura de tablero es un registro  *}

{* con tres campos : la fila , la columna y la profundidad en el *}

{* árbol de búsqueda del nodo . El primer nodo tiene profundidad *}

{* de 1 por convención                                           *}

{*****************************************************************}

 

program Busqueda;

 

interface

 

uses Listas;

 

var PosicionInicial,PosicionFinal:TipoValor;

    Abierta,Cerrada,Expandidos:TipoPuntero;

 

implementation

{$R *.DFM}

 

{Comprueba que una posición generada es válida}

function PosicionValida(p:TipoValor):Boolean;

begin

  if (p.Fila>0) and (p.Fila<9) and (p.Columna>0) and (p.Columna<9) then Result:=True

  else Result:=False

end;

 

{Genera los movimientos posibles a partir de una cierta posición}

procedure GeneraMovimientos(var ListaMovimientos:TipoPuntero;Posicion:TipoValor);

var f,c:Integer;

  procedure Generar;

  var p:Tipovalor;

  begin

  p.Fila:=Posicion.Fila+f;

  p.Columna:=Posicion.Columna+c;

  p.Profundidad:=Posicion.Profundidad+1;

  if PosicionValida(p) then InsertarCola(ListaMovimientos,p)

  end;

begin

  IniciarCola(ListaMovimientos);

  f:=-1;c:=-2;Generar;

  f:=-1;c:=2;Generar;

  f:=1;c:=-2;Generar;

  f:=1;c:=2;Generar;

  f:=-2;c:=-1;Generar;

  f:=-2;c:=1;Generar;

  f:=2;c:=-1;Generar;

  f:=2;c:=1;Generar

end;

 

{Comprueba si una posición dada es la solución}

function Solucion(PosiIni,PosiFinal:TipoValor):Boolean;

begin

  If CompararRegistrosPosicion(PosiIni,PosiFinal) then Result:=True

  else Result:=false

end;

 

function Busqueda_En_Anchura(PoicionInicial,PosicionFinal:TipoValor):Boolean;

var m,n:TipoValor;

begin

  IniciarCola(Abierta);

  IniciarCola(Cerrada);

  InsertarCola(Abierta,PosicionInicial);

  n.Fila:=0;

  n.Columna:=0;

  n.Profundidad:=0;

  While (ColaVacia(Abierta)=false) and

        (Solucion(PosicionFinal,n)=false) do

  begin

    m:=SacarCola(Abierta);

    InsertarCola(Cerrada,m);

    GeneraMovimientos(Expandidos,m);

    While ColaVacia(Expandidos)=False do

    begin

      n:=SacarCola(Expandidos);

      if Solucion(PosicionFinal,n)=true then

      begin InsertarCola(Cerrada,n);Break end

      else InsertarCola(Abierta,n)

    end

  end;

  if Solucion(PosicionFinal,n) then Result:=True else Result:=False

end;

 

function Busqueda_En_Profundidad(PosicionInicial,PosicionFinal:TipoValor;

         lp:Integer):Boolean;

var m,n:TipoValor;

begin

  IniciarPila(Abierta);

  IniciarCola(Cerrada);

  InsertarPila(Abierta,PosicionInicial);

  n.Fila:=0;

  n.Columna:=0;

  n.Profundidad:=0;

  While (PilaVacia(Abierta)=false) and

      (Solucion(PosicionFinal,n)=false) do

  begin

    m:=SacarPila(Abierta);

    if m.Profundidad<=lp then begin

      InsertarCola(Cerrada,m);

      GeneraMovimientos(Expandidos,m);

      While ColaVacia(Expandidos)=False do begin

        n:=SacarCola(Expandidos);

        if Solucion(PosicionFinal,n)=true then

        begin InsertarCola(Cerrada,n);Break end

        else InsertarPila(Abierta,n)

      end

    end

  end;

  if Solucion(PosicionFinal,n) then Result:=True else Result:=False

end;

 

begin

 

  {Aquí se introduce la posición inicial y final cargando los registros

  teniendo en cuenta que la profundidad inicial es 1 y la final cualquiera

  ya que la desconocemos . Para el caso de la búqeuda en profundidad , hay

  que introducir la variable lp que señala la profundidad máxima a buscar .

  Luego se llama al algoritmo deseado de búsqueda y nos devuelve true si ha

  encontrado la solución y false si no la ha encontrado . El camino

  recorrido lo obtenemos de la cola "Cerrada" . Podemos leerla con esta

  secuencia (debemos definir la manera de ver los nodos . Por ejemplo ,

  creamos un procedimiento para imprimir nodos en impresora "ImprimirNodo(n)"

  While ColaVacia(Cerrada)=false do begin

    n:=SacarCola(Cerrada);

    ImprimirNodo(n)

  end;

  Ademas , aquí se introducen todas las sentencias del programa en sí}

 

end.