Árvores

Esse capítulo é dedicado aos aspectos computacionais do estudo das árvores. Árvores são um tipo específico de grafo, que são conectados grafos simples que não tem circuitos simples.

O código Maple nesse capítulo assume que você está usando uma versão atualizada do Maple Network Package. Essas melhorias afetam principalmente a exibição das árvores. Em particular, o comando draw foi atualizado para se entender como desenhar árvores com raiz. Para testar se você está utilizando a versão correta, carregue o pacote networks e rode a versão comando, como em:

with(networks): version();

Se esse comando não produzir uma descrição da versão, então vocês está utilizando a versão errada. Uma versão apropriada pode ser encontrada no site ftp: http://www.mhhe.com/math/advmath/rosen/r5/instructor/maple.html junto com instruções de instalação.

Primeiro, nós iremos discutir como representar, desenhar, e trabalhar com árvores usando o Maple. Especificamente, nós iremos descrever como representar e construir árvores e derivar características básicas sobre árvores em Maple. Nós iremos demonstrar como utilizar o Maple para desenhar árvores.Nós iremos demonstrar como resolver vários problemas, onde árvores fazem um papel importante usando Maple, como procurando e construindo códigos prefixos, usando uma implementação específica do algoritmo de Huffman. Nós iremos descrever como usar o Maple para fazer diferentes métodos de percorrer árvore, onde o percurso é a visita dos vértices da árvore em uma ordem pré-definida. Então nós iremos discutir como esses percursos se relacionam com o tópico de organização. Continuamos mostrando como usar o Maple para criar spanning trees de grafos. Então, nós iremos mostrar como usar o Maple como resolver vários problemas utilizando backtracking. Finalmente, iremos mostrar como encontrar spanning trees de peso mínimo de grafos ponderados usando Maple.

Introdução às Árvores

Para começar, iremos demonstrar como construir árvores em Maple. Dada uma árvore sem raiz, nós podemos construir essa árvore em Maple assim como faríamos com qualquer grafo. Nós também iremos dar um procedure que usa algumas capacidades embutidas do Maple que determinam se um grafo específico é uma árvore.

Antes de entrar na implementação, há dois pontos importantes que devem ser mencionados. Primeiro, notamos que o Maple difere da terminologia de texto, no senso que o Maple refere-se a simples ciclos, quando o texto se refere a simples circuitos. O segundo ponto que vale mencionar é de que uma árvore sem raiz é um grafo simples que não tem ciclos simples. Estruturalmente falando, uma árvore com raiz é exatamente a mesma coisa que uma árvore sem raiz, com a propriedade adicional de que há um vértice específico chamado de raiz, que é visto como o ponto inicial de uma árvore. Em termos de implementação Maple, representamos árvores sem raiz como grafos, e criamos árvores sem raiz a partir de árvores sem raiz utilizando comandos Maple como spantree, que serão abordados posteriormente, especificando um nó desejado para uma árvore sem nó.

Outro tipo importante de árvore é a árvore ordenada, que é uma árvore com raiz onde os filhos de um vértice ordenados de alguma maneira como 1st, 2nd,...,m-th filhos se houverem m filhos de um dado vértice. Nós iremos fazer uso do peso dos vértices para determinar a ordem dos filhos de um vértice específico. Esse tipo de árvore irá aparecer posteriormente, mas é importante distinguir árvores sem raiz, com raiz e desordenadas, e árvores com raiz e ordenadas.

Como primeiro exemplo, iremos discutir árvores sem raiz. Criamos uma árvore exatamente da mesma maneira que criamos um grafo, usando o pacote networks do Maple. Como nosso primeiro exemplo, iremos criar uma árvore simples em 4 vértices.

with(networks):
new(T1): addvertex(a,b,c,d,f,g,T1):
addedge(a,b,a,c,a,d,b,f,b,g, T1):
draw(Tree(a),T1);

Suponha que fomos dados um grafo e se foi pedido para determinar se ele é ou não uma árvore. Pela definição de árvores, precisamos verificar as 3 seguintes propriedades:

1.O grafo é conectado.

2. O grafo é simples.

3. O grafo não tem ciclos.

Usando Maple, essas propriedades são facilmente verificadas. Em particular, podemos determinar se um grafo é conectado em Maple usando o comandoscomponents, que retorna uma coleção de conjuntos de vértices, onde cada conjunto nessa coleção contém os vértices de um componente conexo do grafo. Podemos determinar se um grafo é simples usando o comando Maple gsimp, que retorna a árvore simples por baixo de um multigrafo, e então comparando o número de arestas da árvore por baixo do grafo original. Isso nos leva até o procedure IsSimple.

IsSimple := proc(G::graph) local H;
    H := networks[duplicate](G); 
    if nops(edges(gsimp(H))) = nops(edges(G)) then true
    else false fi;
end:

Note que não devemos simplificar G por si só, pois tal simplificação é um processo irreversível.

Para testar conectividade, utilizamos o procedure IsConnected

IsConnected := proc(G::graph) 
evalb(nops(components(G)) = 1) end:

Podemos determinar se um grafo tem ou não ciclos utilizando o comando cyclebase do Maple que retorna um conjunto de ciclos, ou circuitos simples, que formam uma base de todos os ciclos (circuitos simples) no grafo dado; se o cyclebase não tiver ciclos, o grafo não tem ciclos. Isso, junto com os dois testes anteriores pode ser usado para testar se um grafo é uma árvore.

IsTree:=proc(G::graph)
  if not (IsConnected(G) and IsSimple(G)) then 
    RETURN(false); fi;
  if cyclebase(G) = {} then RETURN(true);
  else RETURN(false); fi;
end:

Se você preferir, pode substituir o teste cycle base test nesse procedure por um que verifica se o número de arestas é um a menos que o número de vértices.

Agora estamos prontos para usar o procedure IsTree para determinar se alguns grafos particulares são árvores;

IsTree(T1);  IsTree(complete(3));

Árvores com raiz

Até esse ponto, nós lidamos apenas com árvores sem raiz. Podemos usar o comando Maplespantree para mudar uma árvore sem raiz em uma árvore com raiz. Ele faz isso atualizando os conjuntos de ancestrais e filhas (descendentes) para cada vértice, para refletir a estrutura da spanning tree.

Para usar o comando spantree, devemos selecionar o vértice e formar uma spanning tree com esse vértice como raiz, direcionando todas as arestas na árvore em direção a raiz. (Estudaremos spanning trees mais tarde nesse capítulo. Geralmente, o comando spantree pega um grafo conexo indireto G e um vértice v e constrói uma spanning tree de G usando v como a raiz, direcionando todas as arestas em direção a v.) Por exemplo, podemos transformar a árvore T1 em uma árvore com raiz, tomando a como sua raiz e utilizando o comando:

T2:=spantree(T1, a):

Podemos facilmente observar relações entre vértices de uma árvore utilizando comandos embutidos no Maple. Entre os comandos que são úteis para isso estão daughter, ancestor, neighbours e departures. O comando daughter encontra os filhos de um vértice em uma árvore com raiz, e o comando ancestor do Maple encontra o vértice pai de um vértice em uma árvore com raiz. Os comandos neighbors e departures agem de maneira similar, determinando os filhos de um vértice em uma árvore com raiz.

Para ilustrar o uso de alguns desses comandos no Maple, podemos determinar relações de árvores como pais, filhos, ancestrais e descendentes de vértices específicos. Por exemplo, podemos encontrar os filhos do vértice a na árvore T2, usando o comando:

daughter(a, T2);

Para achar o pai de d na árvore T2, usamos o comando:

ancestor(d, T2);

Agora representamos um procedure que encontra todos os descendentes, ancestrais e irmãos de um vértice particular em uma árvore com raiz. Esse procedure, chamado Family, pode ser descrito usando o seguinte pseudo-código:

1. Para encontrar todos os ancestrais, usamos o comando ancestor do Maple até não haverem mais ancestrais (ex: quando atingimos o vértice raiz).

2. Para achar todos os descendentes, usamos o comando daughter repetidamente até não haverem mais descendentes(ex: quando todas as folhas de um vértice forem atingidas).

3. Para se achar todos os irmãos de um vértice v, primeiros encontramos o ancestral de v, chamado w; os irmãos de v são descendentes de outro w de v.

Uma implementação desse procedure é como a seguinte:

Family := proc(v::name,G::graph)
  local Temp, Ancestors, Descendants, Siblings;
  Ancestors := ancestor(v,G);
  Temp := ancestor(v,G);
  while not (Temp = {}) do
    Ancestors := Ancestors union Temp;
    Temp := ancestor(Ancestors,G);
  od;
  Descendants := daughter(v,G);
  Temp := daughter(v,G);
  while not (Temp = {}) do
    Descendants := Descendants union Temp;
    Temp := daughter(Descendants,G);
  od;
  Siblings := daughter(ancestor(v, G), G) minus v;
  [Ancestors,Siblings,Descendants];
end:

Agora iremos construir uma árvore mais larga, chamada T3 que é a árvore mostrada na Página 5433 do texto, e então iremos executar o novo procedure criado em um de seus vértices.

new(T3):
addvertex(A,B,C,D,E,F,G,H,I,J,K,L,M,N,T3):
addedge( [A,B],[A,J],[A,K],[B,C],[B,E],[B,F],
   [C,D],[F,G],[F,I],[G,H],[K,L],[L,M],[L,N], T3):
draw(Tree(A),T3);

Os descentendes do vértice B são obtidos pelo comando:

Bfamily := Family(B,T3);  Bfamily[3];

A seguir, determinamos o conjunto de vértices internos (galhos) e folhas de uma árvore com raiz. Lembre-se que um v é um vértice interno de uma árvore com raiz se v tiver filhos, e que v é o vértice folha de uma árvore com raiz se v não tiver filhos. Em outras palavras, em qualquer árvore com raiz não trivial (ex:.uma árvore com raiz que é mais do que apenas um vértice raiz), as folhas são essas com gráu de vértice 1, e os vértices internos são vértices com grau maior que 1.

Sabendo disso, podemos usar o comando Maplevdegree para determinar o conjunto de folhas e o conjunto de vértices internos dada uma árvore com raiz.

Leaves:=proc(T::graph, root::name) 
  select( proc(x,T) evalb( vdegree(x,T) < 2 ) end,
     vertices(T) minus root , T );
end:
Internal:=proc(T::graph, root::name) 
  select( proc(x,T) evalb( vdegree(x,T) > 1 ) end,
     vertices(T) minus root , T );
end:
Leaves(T2, a); Internal(T2,a);

Agora iremos discutir como encontrar o maior número de filhos de um vértice interno de uma árvore com raiz. Lembre-se que se m é esse número, a árvore é chamada de árvore m-ária. Também iremos descrever como determinar se uma árvore m-ária é balanceado. Lembre-se que uma árvore é balanceada se todas as folhas estão no nível h ou h-1 se uma árvore tem um total de h níveis, onde o nível do vértice é a distância do caminho único from da raiz até tal vértice.

Para utilizar o Maple para determinar se uma árvore é uma árvore m-ária, podemos simplesmente olhar a sequencia de graus do vértice, tomando em conta que para todos os vértices exceto a raiz, o grau de tal vértice é um a mais que o número de descendentes. Isso pode ser feito usando o comando vdegree no Maple. Para determinar se uma árvore é balanceada, podemos usar a estrutura de armazenamento interno de uma árvore em Maple. Iremos utilizar do fato de que o Maple armazena o nível do vértice em uma árvore como o peso do vértice para esse vértice. Por exemplo, se v é um vértice que está no nível 3 de uma árvore, então podemos extrair essa informação usando o comando vweight no vértice v.

Esaa técnica é formalizade pelo seguinte procedure no Maple:

ArityBalanced:=proc(G::graph, Root::name)
  local Leaf_Depth, V, Max_Children, is_balanced,i;
  V:=vertices(G); Leaf_Depth:={};
  is_balanced:=false;
  for v in V do
    if (not (v = Root)) and (vdegree(v,G)=1) then
      Leaf_Depth:=Leaf_Depth union vweight(v, G);
    fi;
  od;
  if nops(Leaf_Depth) > 2 then
    printf(`The tree is not balanced`);
  elif nops(Leaf_Depth) = 1 then
    printf(`The tree is balanced`);
    is_balanced:=true;
  elif nops(Leaf_Depth) = 2 
  and abs(Leaf_Depth[1] - Leaf_Depth[2]) > 1 then
    printf(`The tree is not balanced`);
  else
    printf(`The tree is balanced %a`, Leaf_Depth );
    is_balanced:=true;
  fi;
  Max_Children:=maxdegree(G)-1;
  if vdegree(Root, G) > Max_Children then
    Max_Children:=vdegree(Root, G);
  fi;
  printf(`The arity of the tree is %d`, Max_Children);
  [Max_Children, is_balanced];
end:

ArityBalanced(T3, A):

Agora iremos utilizar o procedure ArityBalanced para verificar a fórmula na página 541 do texto para árvore m-árias cheias. Isto é, iremos construir um procedure para computar o número de vértices internos e folhas de dada árvore m-ária, e comparar essas quantidades como esboçado no teorema 3 e teorema 4 da página 541 do texto. O procedure chamado TheoremVerify utilizará:

TheoremVerify:=proc(G::graph, Root::name) 
  local internal, m, leaves, n, i, V, is_full_tree;
  V:=vertices(G);
  n:=nops(V);
  i:=0; internal:=0; leaves:=0;
  is_full_tree:=true;

Use o procedure ArityBalanced para determinar o número de argumentos

  m:=ArityBalanced(G, Root)[1];
  while is_full_tree and i<n do
    i:=i+1;

Se não houverem filhos do vértice, ele é uma folha

    if nops(daughter(V[i], G)) = 0 then
       leaves:=leaves+1;

Se o número de filhos não for m, então não é uma árvore completa

    elif not (nops(daughter(V[i],G)) = m) then
       printf(`The tree is not a full tree`);
       is_full_tree:=false;

O vértice atual é um vértice interno

    else 
       internal:=internal+1;
    fi;
  od;
  if is_full_tree then 
    printf(`Vertices count is %d`, n);
    printf(`Computed count (m*i+1) is %d`, m*internal + 1);
    printf(`Leaf count is %d`, leaves);
    printf(`Computed count ((m-1)*i + 1) is %d`,
        (m-1)*internal+1);
  fi; NULL;
end:

Utilizaremos o procedure TheoremVerify para verificar os teoremas 3 e 4 do texto em uma árvore 3-ária completa.

new(Full1):
addvertex(A,2,3,4,5,6,7,8,9,10, Full1):
addedge(A,2, A,3, A,4, 2,5, 2, 6, 2,7, 
         4,8, 4,9, 4,10, Full1):

TheoremVerify(Full1, A);

Aplicação de Árvores

Essa sessão foca no uso de árvores em árvores de busca binárias. Especificamente, chamamos o uso de árvores em algoritmos de busca binária assim como o uso de árvores em código Huffman. A razão pela qual desejamos usar árvores binárias é de que podemos usar a binary estrutura binária da árvore para tomar decisões binárias(ex: true/false) quanto a inserção ou procura de caminhos.

Uma árvore é chamada de árvore binária se todos os vértices na árvore tiverem no máximo dois filhos. Nesse capítulo, iremos utilizar árvores binárias ordenadas. A ordenação dos vértices é simplesmente a marcação dos filhos de um vértice como o filho a esquerda ou o filho a direita, onde o filho a esquerda é considerado o filho que deve ser visitado primeiro, e o da direita, o que deve ser visitado em segundo.

Inserção binária

Click here to access a summary of all the Maple code used in this section. Um benefício crucial em árvores binárias ordenadas é de que o tempo de buscar exigido to para encontrar um específico elemento da árvore é logarítmico no número de vértices da árvore. A maior desvantegem é de que a inserção de um vértice é muito mais taxativa. Discutiremos estes em mais detalhe enquanto percorremos a própria impementação de um algoritmo de inserção binária.

Requerimos marcações no vértice. No Maple podemos utilizar o nome do vértice como marcação já que ele pode ser tanto inteiro como string.

Um vértice tipico na árvore tem dois descendentes (filhas). Devemos ser capazes de especificar quais desses dois vértices é o descendente da esquerda e qual é o da direita. Podemos indicar isso utilizando o peso do vértice. No Maple, cada vértice tem um peso padrão de 0, como demonstrado no simples exemplo:

new(g): addvertex(1,2,g):
vweight(1,g);

Podemos utilizar o peso do vértice para especificar uma ordenação da esquerda para a direita. Uma solução ainda mais simples é de simplesmente concordar que o peso do vértice é seu nome e impor uma ordenação nesses nomes.

Para comparar o nome de dois vértices, podemos utilizar um procedure como:

IsLessThan := proc(a,b) local t;
  if type( [a,b], [string,string]) then
      t := sort( [a,b] , lexorder );
  else 
      t := sort([a,b]);
  fi;
  if a = t[1] then true else false fi;
end:

Usar essa comparação nos permite geralmente ignorar que tipo de marcação está sendo utilizada.

IsLessThan(1,2); IsLessThan(b,a); IsLessThan(1,b);

Ela também facilita a mudança do critério de comparação em outro ponto posterior, refazendo o código do algoritmo inteiro.

Também precisaremos ser capazes de achar a raiz da árvore. O seguinte procedure calcula tal raiz e força a árvore a lembrar sua raiz, para que a computação não precise ser repetida.

FindRoot := proc(T::GRAPH)
  local v, V;
  V := vertices(T);
  if not assigned( T(Root) ) then
      for v in V do 
        if indegree(v,T) = 0 then
           T(Root) := v;   # remember the root
        fi;
      od;
      if not assigned( T(Root) ) then 
  ERROR(`no root`) fi;
  fi;
  T(Root);
end:

O procedure para construir uma árvore binária ordenadapor inserção é como o exemplo seguinte. Para facilitar, utilizamos o nome do vértice como seu valor quando fazemos comparação.

1. Dado um vértice v para inserir na árvore T, precisamos localizar o local correto na árvore T para inserir v.

2. Se a árvore T estiver vazia, inserir v como raiz.

3. Caso contrário, transforme a raiz da árvore na variável para o vértice atual cur_vertex, e compare v com cur_vertex. se v =cur_vertex, está feito.

4. se v <cur_vertex então procure o filho a esquerda, caso contrário, procure o filho a direita. Isso é feito mudando cur_vertex para ser o filho a esquerda ou a direita e comparando o novo cur_vertex com v.

5. Eventualmente, não seremos capazes de procurar na direção que a comparação diz que devemos ir. Nesse ponto, insira v como o filho não presente de cur_vertex.

A seguir, uma implementação detalhada do algoritmo:

Binsertion := proc(T::graph, x::string,integer)
  local cur_vertex, V, i, Kids, Left, Right;
  V := vertices(T);
  if nops(V) = 0 then
    addvertex(x, T);
    T(Root) := x ;  # remember the root for later
    RETURN( x );
  fi;

Temos uma árvore com raiz...

  cur_vertex := FindRoot(T);
  while x <> cur_vertex do

As ordenações relativas dos descendentes e x e cur_vertex determinam se x pode ser inserido como folha.

      Kids := daughter(cur_vertex,T);
      Kids := sort( convert(Kids,list) , IsLessThan );
      Candidates := 
       sort( [ x, cur_vertex, op(Kids)], IsLessThan );

Comece com casos fáceis

  if nops(Candidates) = 2 then

não há filhos, então adicione apenas um novo filho.

      if IsLessThan(x,cur_vertex) then
    addvertex(x,weight=`Lft`,T);
      else
    addvertex(x,weight=`Rht`,T);
      fi;
      addedge( [cur_vertex,x] , T);
      cur_vertex := x;
      break;
      elif nops(Candidates)=4 then

dois descendentes, então não há inserção nesse nível...

      if IsLessThan(x,cur_vertex) 
          then cur_vertex := Kids[1];
      else cur_vertex := Kids[2]; fi;
      next;
  elif nops(Candidates) = 3 then

não nesse nível se o padrão é [x,L,cur_vertex] ou [L,x,cur_vertex] [cur_vertex,L,x] ou [cur_vertex,x,L]

      if Candidates[1] = cur_vertex 
      or Candidates[3] = cur_vertex 
      then
          cur_vertex := Kids[1];
          next;
      fi;

Para todos os casos restantes adicione em x como um novo vértice

      if IsLessThan(x,cur_vertex) then
    addvertex(x,weight=`Lft`,T);
      else
    addvertex(x,weight=`Rht`,T);
      fi;

Sim! Esse nível.

      addedge( [cur_vertex,x] , T);
      cur_vertex := x;
      break;
  fi;
    od;
    RETURN( cur_vertex );
end:

O procedure addvertex é usado aqui em uma maneira que atualiza os pesos de cada vértice na medida que ele é criado. Isso serve para indicar se é vértice é um descendente a esquerda ou a direita. Enquanto não usamos esses pesos, eles poderiam ser utilizados como uma medida alternativa para ordenação de descendentes de qualquer vértice particular.

Ao invés disso, para a ordenação, nós usamos os nomes dos vértices para indicar a ordenação relativa dos vértices. O fato de que qaiquer dois vértices (e não apenas descendentes do mesmo vértice) podem ser comparados nos permite combinar o novo vértice, os descendentes, e o vértice atual tudo em uma lista ordenada a qual é então inspecionada para determinar qual dos vários casos especiais é relevante durante a inserção de um novo vértice. Qualquer que seja o método de comparação de vértices que for utilizado, é importante que o procedure comparação seja passado na rotina de ordenação como um argumento extra.

Para validar esse procedure, examine como a seguinte lista de inteiros é adicionada:

Num_List:=[4,6,2,8,5,3,7,1]:
new(Tree_Num):
for i from 1 to 8 do
  Binsertion(Tree_Num, Num_List[i]);
od;

Para ver a árvore resultante e sua estrutura, use o comando Mapledraw.

draw(Tree(4), Tree_Num);

O resultado é claramente uma árvore binária de busca.

Árvores binárias existem para serem procuradas. O seguinte procedure BiSearch faz isso. Declarações do tipo Print foram adicionadas para ilustrar o caminho que o algoritmo usa enquanto faz a busca na árvore.

BiSearch := proc(T::graph, v) 
   local  i, Kids, cur_vertex;
   cur_vertex := FindRoot(T);
   while v <> cur_vertex do
      print(cur_vertex);

verifique os casos fáceis

      if v = cur_vertex then RETURN(true); fi;
      Kids := daughter(cur_vertex,T);
      if Kids = {} then RETURN( false) fi;

descendentes, então comece a procurar...

      Kids := sort( convert(Kids,list) );
      Candidates := 
        sort( [v , cur_vertex, op(Kids)], IsLessThan);
      if nops(Candidates) = 4 then # both descendents 
        if IsLessThan(cur_vertex,v) then
            cur_vertex := Kids[2];
        else
            cur_vertex := Kids[1];
        fi;
    next;   # back to top of loop
      elif nops(Candidates) = 3 then

não está presente, a não ser que cur_vertex seja o primeiro ou último da lista

        if Candidates[1] <> cur_vertex 
        and Candidates[3] <> cur_vertex then
           RETURN( false );
        fi;
        cur_vertex := Kids[1];
        next;
     fi;
  od;
  RETURN(true);
end:

Para testar esse procedure, tentamos procurar por dois elementos, um que está na árvore e um que não está. Tree_Num;

BiSearch(Tree_Num,8);         
BiSearch(Tree_Num,12);

Codificação de Huffman

A codificação de Huffman é um método para construir um código prefixo eficiente para um conjunto de caractéres. Ele é baseado num algoritmo ganancioso, onde em cada passo os vértices com menos peso são examinados. A codificação de Huffman pode produzir códigos de prefixo em condições óptimas. O seguinte pseudo-código descreve um algoritmo para codificação de Huffman. (Para uma discussão mais completa sobre a codificação de Huffman, veja Cormen, Leiserson, e Rivest, Introduction to Algorithms, MIT Press, 1989.)

Comece criando uma lista ordenada de elementos a serem codificados, onde a ordenação é com respeito a frequência de ocorrência desses elementos. Considere cada elemento da lista como um vértice com peso igual a sua frequência de ocorrência.

1. Remove os dois primeiros elementos, x e y, dessa lista;

2. Atribua x como o filho a esquerda e y como o filho a direita de um novo vértice em nossa árvore;

3. Atribua o peso de z para ser a soma dos pesos de x e y;

4. Insira z na posição correta de nossa lista, e repita o passo(2).

5. Quando completar, nossa lista deve conter apenas um elemento, que é uma árvore binária com raiz.

6. Novamente, uma rotina de comparação especial é necessária. Elementos do código são representados por listas como em [a,15] and [b,10]. O seguinte procedure HuffCompare compara dois de tais elementos.

HuffCompare :=proc(a::list,b::list) 
if a[2] <= b[2] then true else false fi;
end:

Por examplo, descobrimos que [b,10] < [a,15].

HuffCompare([b,10],[a,15]);

Utilizando esse método de comparação, listas de códigos de elementos podem ser ordenadas em ordem crescente.

sort( [[a,5],[b,10],[c,8],[d,11]], HuffCompare);

O algoritmo de codificação de Huffman completo é implementado da seguinte maneira:

Huffman:=proc(L::listlist)
  local i, j, k, n, Q, T, x, y, z, Temp;
  new(T);
  Q := sort( L , HuffCompare ); i := 1;
  while(nops(Q)>1) do
     i := i+1;

pegue os dois primeiros elementos de código

     x:=Q[1]; Q:=subsop(1=NULL, Q);
     y:=Q[1]; Q:=subsop(1=NULL, Q);

construa o novo vértice e sua localização

     z := [ i , x[2]+y[2]]; 
     for j to nops(Q) while HuffCompare( z, Q[j]) do
        j := j+1;
     od;  j := j-1;

adicione os vértices e arestas a árvore

     Q := [seq(Q[k],k=1..j),z,seq(Q[k],k=j+1..nops(Q))];
     addvertex([x[1],y[1],z[1]],weights=[x[2],y[2],z[2]],T);
     addedge([z[1],x[1]],[z[1],y[1]],T);
  od;
  RETURN( eval(T) );
end:

O tipo listlist denota uma lista de listas. O eval final é incluído para garantir que o resultado retornado pelo procedure é a própria árvore, e não apenas seu nome.

Teste esse novo procedure na seguinte lista de caractéres em inglês emparelhados com uma frequência relativa de ocorrência;

Huf:=Huffman([[f,15],[b,9],[d,22],[c,13],[a,16],[e,45]]):

Para ver o resultado, novamente utilizamos o comando Mapledraw;

rt := FindRoot(Huf);
draw(Tree(rt), Huf);

Percursos em Árvores

Nessa seção, mostramos como usar o Maple para fazer percursos em árvores. Lembre-se que um algoritmo de percurso em árvore é um procedure para sistematicamente visitar cada vértice de uma árvore ordenada com raiz. Em particular, iremos dar procedures para três importantes algoritmos de percurso em árvore: pré-ordem, ordem, e pós-ordem. Então iremos mostrar como usar esses métodos de percurso para produzir as notações pré-fixa, infixa e pós-fixa para expressões aritméticas.

Esses percursos em árvore dependem da construção de árvores ordenadas com raiz. Nós devemos usar os pesos dos vértices para representar a ordem dos filhos, como foi feito nas seções anteriores.

Criamos uma árvore desordenada, baseada na árvore da figura 3 da página 5566 do texto, para ver o comportamento dos vários tipos de percurso de árvore. Então o grafo da árvore se torna:

d := 'd':

new(Trav): 
addvertex( [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p],
  weights=[0,1,2,3,1,2,1,2,3,1,2,1,2,1,2,3], Trav):
addedge( [[a,b],[a,c],[a,d],[b,e],[b,f],[d,g],[d,h],
  [d,i],[e,j],[e,k],[g,l],[g,m],[k,n],[k,o],[k,p]], Trav):
draw(Tree(a),Trav);

Os pesos adicionados aos vértices aqui representam o número que desse vértice em termos de seu pai. Por exemplo, d é o terceiro filho de a. Como nas seções anteriores, tais pesos poderiam ser usados para ordenação, apesar de que em fato, a ordenação por baixo é simplesmente alfabético nos nomes dos vértices. Primeiro implementamos o algaritmo de percurso em pré-ordem. Esse visita a raiz e então cada sub-árvore da esquerda a direita em uma maneira de percurso em pré-ordem. Em forma de pseudo-código, o algoritmo para pré-ordem é:

1. Visite a raiz de T. Ponha o atua vértice para ser a raiz.

2. Considere os filhos do vértice atual como raízes das árvores T_1, T_2, ... T_m, pegos em ordem da esquerda para a direita. Repita o passo (1) em cada sub-árvore em ordem.

Como pode ser visto no passo (2) do pseudo-código acima, esse algoritmo é recursivo. Nós providenciamos a seguinte implementação em Maple:

Preorder:=proc(G::graph, r)
  local Dep, v, T;

Visite a raiz

  printf(`%a `, r);

Considere os filhos da raiz

  Dep:= departures(r, G);

Forme a ordem correta dos filhos

  Dep:= sort( convert(Dep,list) , IsLessThan );

Percorre em pré-ordem essas sub-árvores em ordem

  for v in Dep do 
    Preorder(G, v);
  od;
  printf(``, r);
end:

A ordem em que nós percorremos os descendentes é determinada pela procedure booleana isLessThan (das seções anteriores). Para percorrer os descendentes em uma ordem diferente, use uma comparação de rotina diferente. Podemos examinar a execução esse procedure no percurso de árvore criado anteriormente, enraizado no vértice A.

Preorder(Trav, a);

Nós implementamos o percurso em ordem de maneira similar. Simplesmente alteramos a sequência na qual os vértices são visitados. Especificamente, olhamos na sub-árvore mais a esquerda dos vértices, seguida pela raiz, seguida pela sub-árvore mais a direita dos vértices. Em pseudo-código, temos:

1. Se a árvore T tem apenas um vértice, r então visite r

2. Caso contrário, a árvore T tem mais que um vértice. Chame a sub-árvore mais a esquerda(enraizada no filho mais a esquerda) T_1. Percorre em ordem T_1, então visite a raiz r de T.

3. Percorra em ordem as sub-árvores com raiz T_2,...,T_m.

Em Maple, a implementação seria a seguinte:

Inorder:=proc(G::graph, r)
  local v, Dep, T;

se tivermos atingido um vértice folha, imprima ele

  if outdegree(r, G) = 0 then
    print(r);

Estamos em um vértice interno

  else
    Dep:=departures(r, G);

Determina a ordem dos filhos e percorra a sub-árvore baseada no filho mais a esquerda

    Dep := sort( convert( Dep , list ), IsLessThan );
    Inorder(G, Dep[1]);

Visite a raiz

    print(r);

Percorra em ordem as sub-árvores restantes

    for v in Dep[2..nops(Dep)] do 
      Inorder(G, v);
    od;
  fi; NULL;
end:

Nós adicionamos um NULL como última declaração, para que nada seja retornado.

Novamente, para percorrer os filhos em uma ordem diferente, use uma comparação de rotina diferentes para ordenar os descendentes. Teste esse novo procedure executando ele em tree Trav.

Inorder(Trav, a);

O percurso final que devemos implementar é em pós-ordem. Percurso em pós-ordem é similar ao percurso em pré-ordem, exceto que visitamos a raiz após visitar cada sub-árvore. Segue o pseudo-código:

1. Considere os filhos da raiz as sub-árvores T_1, T_2, ... T_m, pegos em ordem da esquerda para a direita.

2. Percorre em pós-ordem T_1, então T_2, até T_m.

3. Imprima a raiz da atual árvore.

Em maple, temos o seguinte procedure:

Postorder:=proc(G::graph, r::name)
  local v,i, Dep, T;

Considere filhos da raiz

  Dep:=departures(r, G);

Forme a ordem correta dos filhos

  Dep:= sort( convert(Dep,list) , IsLessThan) ;

Percorra em pós-ordem essas sub-árvores em ordem

  for v in Dep do
    Postorder(G, v);
  od;

Visite a raiz

  printf(` %c`, r);
end:

Também testamos esse procedure na tree Trav com raiz A

Postorder(Trav, a);

Notações Infixa, Pré-fixa e Pós-fixa

Agora iremos discutir como usar o Maple para trabalhar com as formas infixa, pré-fixa e pós-fixa de expressões aritméticas. Essas formas são discutidas na sessão 8.33 do texto. Especificamente, iremos mostrar como criar uma representação em árvore binária de uma expressão infixa, como usar percursos em pós-ordem e pré-ordem para crias as formas pós-fixa e pré-fixa de expressões, respectivamente, e como avaliar essas expressões a partir de suas formas pós-fixa e pré-fixa. Para começar essa seção, nós construímos um procedure em Maple que pega uma expressão aritmética infixa e a converte em um representação de árvore binária. Essa representação é árvore binária pode ser percorrida usando os percursos das seções anteriores para formar vários formatos de representação aritmética. Como um exemplo, podemos construir uma árvore binária representando uma expressão infixa, como (3+10)^2 - (100-30)/(5*2), e então executar um percurso em pré-ordem nessa árvore para formar a representação pré-fixa dessa expressão aritmética.

No procedure em Maple que iremos implementear, consideraremos uma versão modificada da notação infixa, para evitar manipulações complicadas de string que depreciam o verdadeiro problema. Especificamente, iremos utilizar chaves ao invés dos parênteses normalmente utilizados na notação infixa. Adicionalmente, iremos definir nossos operadores em termos de suas representações em string: + para adição, - para subtração e assim vai. Dessa maneira, as facilidades de manipulação de lista do Maple ficam imediatamente disponíveis. Então, nós representamos expressões x + y as [x,"+",y] onde + é uma string.

Procedures do Maple podem ser usados para ajudar-nos a construir tais listas. Por exemplo,

`&Plus` := proc(a,b) [a,Unique(`+`),b] end:

nos permite escrever e usar

x &Plus y;

O Maple manipula os nomes de procedures da forma ... como operadores infixos. O procedure que Unique tem é definido especialmente para as rotinas usadas nesse artigo. O resultado é uma lista incluindo versões especialmente encodadas da string + que não colide com usos anteriores de + como nome. (Cada vértice da expressão árvore deve ter um nome diferente, mesmo que eles pareçam iguais). Similarmente, usamos

`&Times` := proc(a,b) [a,Unique(`*`),b] end:
`&Pow` := proc(a,b)   [a,Unique(`^`),b] end:
`&Div` := proc(a,b)   [a,Unique(`/`),b] end:
`&Minus` := proc(a,b) [a,Unique(`-`),b] end:

para que possamos escrever e usar

x &Times y, x &Pow y;

Esses podem ser usados para escrever a expressão aritmética ((x+y)^2)+((z-4)/3) como

Expr1:= (((x &Plus y) &Pow 2) &Plus ((z &Minus 4) &Div 3 ));

O resultado é uma lista aninhada de listas, com cada lista representando uma operação binária. Agora estamos prontos para construir uma árvore binária representando tal expressão. O algoritmo necessário em pseudo-código é:

1. Se houver uma expressão algébrica isolada (como um nome ou número), a árvore consiste de um vértice isolado.

2. Caso contrário, a lista consiste de um operando a esquerda, um operador e um operando a direita. Use o algoritmo para construir a árvore binária para operando a esquerda.

3. Repita o passo (2) no operando a direita.

4. Combina os resultados dos passos (2) e (3) para formar a árvore binária.

Nossa implementação é a seguinte:

InFixToTree:=proc(L::list,algebraic)
  local r1,r3, T1, T3,LocL; 

Se não tivermos sublistas em nossa expressão, retorne as listas de arestas e vértices como mostrado

  if type(L,algebraic) then
    new(T1); LocL := Unique(L); 
    addvertex(LocL,T1); 
    T1(Root) := LocL;
    RETURN( eval(T1) );
  fi;

L é agora uma lista como [a , + , b]

  T1 := InFixToTree(L[1]); r1 := T1(Root);
  T3 := InFixToTree(L[3]); r3 := T3(Root);

construa a nova árvore

  addvertex(vertices(T3),T1);
  addedge( ends(T3), T1 );
  addvertex( L[2] , T1 ):
  addedge( [L[2],r1], [L[2],r3]  , T1 );
  T1(Root) := L[2];
  RETURN( eval(T1) );
end:

A raiz da árvore é manipulada de maneira especial. Recomputando a raiz da árvore é estranho e caro, então nós simplesmente pedimos a cada árvore que se lembre sua própria raiz. Isso feito por declarações de tarefa como T(Root) := LocL;.

O procedure Unique é novamente usado para se assegurar que cada instancia de vértice tem nome único, mesmo que pareça igual a outro. Em todos os outros aspectos, a implementação é quase exatamente como descrito no pseudo-código. Para testar esse procedure, use-o para construir uma expressão árvore para a expressão anterior Expr1.

Expr1;
TreeExpr1:=InFixToTree(Expr1):

Para ver isso, desenhe-o como uma árvore.

r := TreeExpr1(Root);
draw(Tree(r),TreeExpr1);

Suponha que somos dados uma representação em árvore binária de uma expressão aritmética. Nós podemos usar os algoritmos anteriormente criados para expressas essas árvores como expressões pós-fixas ou pré-fixas executando os percursos de pós-ordem ou pré-ordem, respectivamente. Como isso é trivial, cabe ao leitor explorar essa técnica. Como um exemplo final dessa seção, nós demonstramos como avaliar uma dada expressão pós-fixa. Para simplificar, nós representamos as operações básicas pelas primeiras letras das palavras add, subtract, multiply, divide e exponentiate. cabe ao leitor explorar como implementar um procedure que irá avaliar uma expressão pré-fixa, dado que essa técnica é a simples modificação do argumento que será usado no caso pós-fixo.

Post1:=[7,2,3,M,S,4,E,9,3,D,A];
Postfix:=proc(T::list)
  local i, L;
  L:=T;
  while nops(L)>1 do
    i:=1;
    while not member(L[i], 'A','S','D','M','E') do
      i:=i+1;
    od;
    if L[i]='A' then
      L[i]:= L[i-2]+L[i-1];
    elif L[i]='M' then
      L[i]:= L[i-2]*L[i-1];
    elif L[i]='S' then
      L[i]:= L[i-2]-L[i-1];
    elif L[i]='D' then
      L[i]:= L[i-2]/L[i-1];
    elif L[i]='E' then
      L[i]:= L[i-2]^L[i-1];
    fi;
    L := [op(L[1..i-3]),op(L[i..nops(L)])];
  od;
  L;
end:
Postfix(Post1);

Note que em release 4, nós somos permitidos atribuir diretamente a lista elements.

Árvores e Ordenação

Essa seção explica como usar o Maple para executar e analisar algoritmos de ordenação. Árvores são frequentemente usadas para modelar algoritmos de ordenação, especialmente quando a complexidade desses algoritmos está sendo estudada. Em particular, essa seção foca em dois dos muitos tipos diferentes de algoritmos de ordenação que serão estudados, o bubble sort e o merge sort.

Bubble Sort

Para começar, nós iremos examinar a implementação do bubble sort. A razão pelo qual o bubble sort foi dado o nome "bubble" (bolha) é que o menor da lista "borbulha" em direção a frente da lista, se movendo um passo mais próximo a sua posições após cada iteração. O pseudo-código, que é destacado na página 575 do texto, é como o seguinte:

1. Recebe como entrada uma lista, L, de n elementos.

2. Entra num laço de repetição do índice i de 1 até n-1.

3. Entra num laço de repetição do índice j de 1 até n-i.

4. Se o elemento na posição j+1 na lista L é menor que o elemento na posição j de L, troque esses dois elementos.

No final de cada laço j, nós posicionamos os elementos mais largos i no final de L.

O seguinte procedure, chamado BubbleSort, é uma implementação desse pseudocódigo.

BubbleSort:=proc(L::list)
  local i, j, temp, T;
  T:= array(L);
  for i from 1 to nops(L)-1 do
    for j from 1 to nops(L)-i do
      if T[j] > T[j+1] then
        temp:=T[j];
        T[j] := T[j+1];
        T[j+1] := temp;
      fi;
    od;
  od;
  convert(T,list);
end:

Note que antes de começar a mover os elementos, nós convertemos a lista L em um arranjo. Isso porque nós podemos mudar cada elemento de um arranjo em apenas uma operação, enquanto para mudar qualquer parte de uma lista, nós devemos recopiar a lista inteira -- um processo envolvendo n operações. Quando nós terminarmos de mover os elementos, nós transformamos o arranjo novamente em uma lista.

Podemos examinar a execução desse procedure em uma lista desordenada. Note que se a lista tem cinco elementos, um total de 5*4/2 = 10 laços são usados pelo algoritmo bubble sort para ordenar esses elementos.

BubbleSort([3,2,4,1,5]);

Merge Sort

Nós iremos agora implementar o merge sort em Maple. Nós também iremos usar Maple para estudar a complexidade desse algoritmo. O algoritmo de merge sort pode ser implementado como um procedure recursivo. A idéia básica da tarefa de aplicar merge sort numa é de dividir a lista em duas de tamanhos iguais ou quase iguais, ordenando cada sub-lista usando o algoritmo merge sort, e no final juntando as listas resultantes. Isso pode ser descrito no seguinte pseudo-código:

1. Dada uma lista de elementos, se o tamanho da lista é 1, retorne essa lista.

2. Se a lista tem mais de dois elementos, use o merge sort nessas duas listas e retorne a lista fundida resultante.

Primeiro usamos um procedure, Merge, que pega duas listas ordenadas e funde elas em uma única lista ordenada, consistindo dos elementos das duas listas. Aqui está o exemplo em código Maple para o procedure de Merge:

Merge := proc(L1::list, L2::list)
  local  L, i,j,k,m,n;
  L:=[]; 
  i := 1; j := 1;  k := 1;
  m := nops(L1); n := nops(L2);
  L := array(1..m+n);
  while  i <= m and j <= n  do
      if L1[i] <= L2[j] then 
          L[k] := L1[i];
    i := i+1;
  else
    L[k] := L2[j];
    j := j+1;
  fi;
  k := k+1;
   od;
   while i <= m do 
       L[k] := L1[i];
       i := i+1; k := k+1;
   od;
   while j <= n do 
       L[k] := L2[j];
       j := j+1; k := k+1;
   od;
   convert(L,list);
end:

Nós ilustramos o uso desse procedure com o seguinte exemplo:

Merge([1,2,6,8],[3,5,7]);

Agora nós damos o pseudo-código para o algoritmo merge sort:

A descrição do algoritmo merge sort que nós iremos usar é baseada na definição recursiva. Em pseudocódigo:

1. Se a lista L tem apenas um elemento, ela é ordenada em ordem, então retornamos L como ela é.

2. Se L tem mais de um elemento, nós dividimos a lista em duas listas de mesmo tamanho, ou de maneira que a segunda lista tenha exatamente um elemento a mais que a primeira.

3. Nós recursivamente usamos o merge sort nas duas listas, e então juntamos as duas listas.

MergeSort:=proc(L::list)
  local First, Second,i, n;

Se a lista tem apenas um elemento, retorne-o

  if nops(L) = 1 then

print(L)

    L; 
  else 

A lista tem mais de um elemento print(L)

    n := nops(L);
    mid := floor(n/2);

Divida as listas em duas sub-listas de tamanho igual

    First  := L[1..mid];
    Second := L[mid+1..n];

Junte o resultado dos merge sorts nas duas listas

    Merge(MergeSort(First), MergeSort(Second));
  fi;
end:

Nós ilustramos o uso do procedure MergeSort ordenando uma lista desordenada com 100 elementos:

MergeSort([8,2,4,6,9,7,10,1,5,3]);

Nós iremos agora analizar o tempo de execução do MergeSort em relação ao BubbleSort. Especificamente, nós iremos criar uma lista desordenada com 10000 elementos aleatórios e executar o BubbleSort e o MergeSort nessa lista. Isso irá nos dar uma ilustração limitada do tempo de execução desses procedures, na qual o leitor deve expandir lendo análises teóricos no texto.

Para criar uma lista aleatória com 1000 elementos, usamos os comandos rand e seq do Maple, como representado a seguir:

A:=[seq(rand(), i=1..100)]:

Então, nós podemos usar o comando time para medir a quantidade de tempo necessário para ordenar a lista aleatória:

st:=time(): BubbleSort(A): time() - st;
st:=time(): MergeSort(A): time() - st;

O leitor é encorajado a implementar outros tipos de algoritmos de ordenação usando o Maple e a estudar a complexidade relativa desses algoritmos quando usandos para ordenar listas de vários tamanhos diferentes. Também é interessante usar técnicas de animação para ilustrar os passos dos algoritmos de ordenação. Apesar de não fazermos isso aqui, o leitor com habilidades avançadas de programação é convidado a fazê-lo. Tome nota especial para a importância de usar a estrutura de dados correta, ex: lists vs arrays.

Árvores de Extensão

Essa seção explica como usar o Maple para construir árvores de extensão (spanning trees) para grafos e como usar árvores de extensão para resolver muitos tipos diferentes de problema. Árvores de extensão já foram usadas no capítulo 7; elas tem uma grande quantidade de aplicações. Em particular, nós iremos mostrar como usar o Maple para formar as árvores de extensão usando dois algoritmos: depth-first search e breadth-first search. Então nós iremos mostrar como usar o Maple para fazer backtracking, uma ténica baseada em depth-first search usada para resolver vários problemas.

Para começar, nós iremos discutir como implementar o algoritmo de depth-first search no Maple. Como o nome do algoritmo (busca em profundidade, em português) sugere, os vértices são visitados em ordem de crescimento de profundidade da árvore de extensão. O pseudo-código é:

1. Dado um grafo G, e uma raiz vértice v, considere o primeiro vizinho de v, chamado w. Adicione aresta(v, w) a árvore de extensão.

2. Escolha x para ser um vizinho de w que não está na árvore. Adicione aresta(x,w) e conjunto w igual a x.

3. Repita o passo (2) até não haver mais vértices que não estão na árvore.

A implementação do depth-first search é a seguinte:

Depth := proc(G::graph, r)
  local v, V, N, S,In_Tree;
  new(S);
  addvertex(r, S);
  In_Tree:=[r];
  while In_Tree <>[] do
    v := In_Tree[-1];
    N:=neighbors(v, G) minus vertices(S);
    if N = {} then In_Tree := In_Tree[1..nops(In_Tree)-1]; 
        next; fi;
    addvertex(N[1],S);
    addedge([v,N[1]],S);
    In_Tree:=[op(In_Tree), N[1]];
  od;
  eval(S);
  end:

Nós demonstramos o uso do procedure de depth-first search com o seguinte exemplo:

new(G1):
addvertex(A,B,C,D,E,F,G,H,I,J,K,L,M, G1):
addedge( A,B,A,D,B,C,B,E,C,F,D,E,
   D,H,E,F,E,I,F,G,F,J,G,L,
   G,J,H,K,H,I,I,J,I,K,M, K, G1);
S1:=Depth(G1,E):
draw(Tree(E), S1);

Tendo implementado o algoritmo de árvore de extensão de depth-first search, agora nós podemos modificar levemente o código Maple e conseguir uma árvore de extensão com breadth-first search. Especificamente, o algoritmo de breadth-first search opera examinando todos os vértices da atual profundidade do grafo antes de se mover para baixo, no próximo nível do grafo. Antes de implementar esse algoritmo, nós damos uma descrição em pseudo-código do algoritmo.

1. Dado um grafo G, e uma raiz vértice v, identifique os vizinhos de v. Chame esse vizinho de conjunto N_1.

2. Adicione arestas de V até cada vértice em N_1 que ainda não está na árvore de extensão.

3. Pegue o primeiro vértice de N_1, chamado w. Considere os vizinhos de w; chame-o de conjunto de vizinhos N_2.

4. Repita o passo (2) com w substituído por v, e N_2 substituído por N_1.

5. Se todos os vértices em N_1 tiverem sido usados, mova abaixo para o próximo nível, e repita o passo (2).

A seguir, uma implementação em Maple do algoritmo breadth-first search, chamada Breadth;

Breadth:=proc(G::graph, r)
  local v, N, S, In_Tree;
  new(S);
  addvertex(r, S);
  In_Tree:=[r];
  while not(In_Tree=[]) do
    v := In_Tree[1];
    N:=neighbors(In_Tree[1], G) minus vertices(S);
    for v in N do
      addvertex(v,S);
      addedge([In_Tree[1], v],S);
      In_Tree:=[op(In_Tree), v];
    od;
    In_Tree:= In_Tree[2..nops(In_Tree)];
  od;
  eval(S);
  end:
S2:=Breadth(G1, E):
draw(Tree(E), S2);

Note que as duas árvores de extensão são diferentes mesmo que elas estejam enraizadas no mesmo vértice. Em particular, a árvore com depth-first search tem uma estrutura funda e magra, enquanto a árvore com breadth-first search é menor e mais larga. Essas representações gráficas ajudam a ilustrar o algoritmo utilizado, e heuristicamente, nós podemos usar as representações para adivinhar qual dos dois algoritmos foi usado.

Backtracking

Click here to access a summary of all the Maple code used in this section. Backtracking é um método que pode ser usado para achar soluções para problemas que poderiam ser impráticos de se resolver usando técnicas de busca excessiva, O backtracking é baseado na busca sistemática pela solução de um problema usando uma árvore de decisão. Aqui nós mostramos comos usar backtracking para reslver vários problemas diferentes, incluindo pintar um grafo, resolver o problema das n-rainhas de posicionar n rainhas em um tabuleiro de xadrez nXn de maneira que uma rainha não possa atacar a outra, e também o problema do subconjunto da soma, que consiste em encontrar um subconjunto de um conjunto de inteiros cuja soma é dado inteiro.

O primeiro problemas nós iremos atacar através de um procedure de backtracking é o de colorir um grafo usando n cores, onde n é um inteiro positivo. Dado um grafo, nós tentaremos colorir ele usando n cores de uma maneira gananciosa. No entanto, quando nós atingimos uma coloração que não nos permite colorir um vértice adicional propriamente, nós usamos backtrack, mudando a cor de um vértice anteriormente colorido e tentando novamente. Aqui está o pseudo-código para nosso procedure BackColor que executa essa coloração baseado em backtracking. Aqui nós ordenamos as cores como color1, color2, ..., colorn:

1. Ordene os vértices do grafo G como v_1, v_2, ..., v_m.

2. Atribua color1 a v_1. Sete i = 2.

3. Atribua color c a v_i, onde c é o menor inteiro para que nenhum vizinho de v_i já tenha sido atribuído com color c.

4. Se nós pudermos atribuir tal cor a v_i, incremente i e repita o passo (3).

5. Se nós não pudermos atribuir nenhuma cor a v_i, nós usamos o backtrack, setando i = i-1 e incrementando a cor de v_i, se possível.

6. Se nós não tivermos uma coloração válida, repita o passo (5).

7. Para quando tivermos colorido todos os vértices, ou usado todas as colorações possíveis.

Uma implementação desse pseudo-código no seguinte algoritmo Maple, chamado BackColor:

BackColor := proc(G::graph,n::integer)
local i,k, v, V, cur_vertex, Assigned, Available,
        used , N, cur_color;
  V:= convert(vertices(G), list );

inicialize as cores atribuídas e disponíveis

  for v in V do
    Assigned(v):=0;
    Available(v):=[seq(k, k=1..n)];
  od;
  cur_vertex:=1;
  while cur_vertex >= 1 and cur_vertex <=nops(V) do
    v := V[cur_vertex];

Atribua a menor cor ao vértice atual. Reuna todos os vizinhos do vértice atual.

    N:=neighbors(v, G);
    while Assigned(v)=0 and Available(v) <> [] do
      Used := map( Assigned , N );
      if not member( Available(v)[1], Used ) then
          Assigned(v) := Available(v)[1];
      fi;
      Available(v) := Available(v)[2..nops(Available(v))];
    od;

Faça um backtrack se tal cor não existir

    if Assigned(v) = 0 and (Available(v) = []) then
      printf(`Backtracking on %a %d`,
          v, Assigned(v));
      while (Available(v)= []) and cur_vertex > 1 do
         Available(v) := [seq(k, k=1..n)];
         Assigned(v) := 0;
         cur_vertex := cur_vertex - 1;
         v := V[cur_vertex];
      od;
      if cur_vertex > 1 then 
          Assigned(v) := 0;
      else
          break;
      fi;
    else
      cur_vertex:=cur_vertex+1;
    fi;
  od;
  if not has( map( Assigned , V ), 0 ) then
    for v in V do
      printf(`Assign vertex %a color %d`, v, Assigned(v));
    od;
  else
    printf(`There does not exist a proper vertex coloring`);
    printf(`with %a colors`, n);
  fi;
end:

Nós agora iremos testar essa implementação em um novo grafo chamado C1. Note que a saída do procedure BackColor é a atual atribuição de cores em qualquer estágio do backtracking, e a coloração final ou indicação de não-existência de possibilidade de coloração própria para o caso diante da terminação do procedure.

new(C1): addvertex([E,B,C,D,A], C1):
addedge(A,B,A,E,B,C,B,D,B,E,C,D,D,E,C1):
BackColor(C1,3);

Adiante, nós vamos examinar a execução do procedure BackColor em C1, com duas novas arestas adicionadas. Note que esse novo grafo tem K_4 como subgrafo.

addedge(A,D,A,C, C1):
BackColor(C1,3);
BackColor(C1,4);

Outro problema com uma solução elegante de backtracking é o problema de posicionar n-rainhas em um tabuleiro de xadrez nXn de maneira que nenhuma rainha tem como atacar a outra. Isso significa que nenhum par de rainhas pode ser posicionadona mesma linha horizontal, vertical ou diagonal. Nós iremos resolver esse problema usando um procedure baseado em backtracking. Iremos posicionar as rainhas no tabuleiro de uma maneira gananciosa, até que todas as rainhas estejam posicionadas ou não haja mais posição disponível para um rainha ficar sem estar na mesma linha diagonal, vertical ou horizontal que outra já posicionada. Para fazer com que o procedure principal seja mais fácil de entender, iremos criar um procedure ajudante, que irá verificar se um particular lugar do tabuleiro é válido. Se houverem duas rainhas na mesma linha, coluna ou diagonal, então ValidQuenns irá retornar false; caso contrário, o procedure irá retornar true.

ValidQueens:=proc(Q::matrix, 
 row::integer, col::integer, size::integer)
 local i,return_value;
  return_value:=true;

Verifique se as dimensões são válidas

  if row > size or col > size then
    return_value := false;
  else

Cheque as rainhas horizontalmente. Note que o algoritmo principal nunca posiciona duas rainhas na mesma coluna. então checagem vertical não é necessária.

    for i from 1 to col-1 do
       if Q[row, i] = 1 then
         return_value:=false;
       fi;
    od;

Cheque as rainhas em duas diagonais.

    for i from 1 to col-1 do
      if row>i then
        if Q[row-i, col-i] = 1 then 
          return_value:=false; 
        fi;
      fi;
      if row+i <=size then
        if Q[row+i, col-i] = 1 then 
          return_value:= false; 
        fi;
      fi;
    od;
  fi;

Retorne o valor

  return_value;
end:

O procedure principal para resolver o problema das n-rainhas, que será chamado de NQueens, segue o mesmo fluxo de controle que o procedure BackColor, como pode ser deduzido nos comentários em-linha. Especificamente, nós temos um estágio de inicialização, ou incremental, onde tentamos preencher a atual coluna, e o estágio de backtracking, onde nós usamos backtrack se não pudermos posicionar a rainha na atual coluna. A implementação Maple desse procedure é a seguinte:

NQueens:=proc(n::integer)
  local cur_col, cur_row, Q, bad_position, Assigned;

Inicie Queens

  Q:=linalg[matrix](n, n, 0);
  cur_col:=1;  Assigned:=[];
  while cur_col >= 1 and cur_col <=n do

Atribua uma rainha a próxima coluna

    bad_position := true;
    cur_row:=0;

a primeira posição disponível funciona?

    while cur_row < n and bad_position do
      cur_row := cur_row+1;
      bad_position := false;

bad é true se houver um vizinho com vértice colorido

      Q[cur_row, cur_col] := 1;
      if not ValidQueens(Q, cur_row, cur_col, n) then
        bad_position := true;
        Q[cur_row, cur_col] := 0;
      fi;
    od;

Usa backtrack se não tiver nenhum posição disponível pra rainha.

    if cur_row=n and bad_position then
      printf(`Backtracking on column`);
      printf(` %d of %a since stuck`, cur_col, Q);
      while not ValidQueens(Q, cur_row, cur_col, n) 
      and cur_col > 1 do
        cur_col := cur_col-1;
        Q[Assigned[cur_col], cur_col]:=0;
        cur_row := Assigned[cur_col] + 1;
        Assigned:=subsop(cur_col=NULL, Assigned);
      od;
      if cur_col >= 1 and cur_row <= n then
        Assigned:=[op(Assigned), cur_row];
        Q[cur_row, cur_col] := 1;
        cur_col := cur_col + 1;
      else
        cur_col := cur_col - 1;
      fi;
    else

Se o posicionamento da rainha é atualmente válido, mova para a próxima

      cur_col:=cur_col+1;
      Assigned:=[op(Assigned), cur_row];
    fi;
  od;
  if (cur_col >= 1) then
    printf(`A proper Queen placement is %a`, Q);
  else
    printf(`No Queen placement with %d Queens`, n);
  fi;
end:

Agora nós usamos o procedure NQueens para resolver o problema de n-rainhas quando n = 3 e n = 4.

NQueens(3);
NQueens(4);

Nós consideramos um terceiro problema que pode ser resolvido usando backtracking; o problema do subconjunto da soma. Dado um conjunto de inteiros S, nós desejamos encontrar um subconjunto B de S tal que a soma dos elementos de B é dado valor M. Para usar backtracking para resolver esse problema, nós sucessivamente selecionamos inteiros de S até a soma desses elementos seja igual a M ou exceda M. Caso exceda M, nós usamos backtrack removendo o último elemento da soma, e inserimos um valor diferente.

Antes de implementarmos o procedure principal, nós iremos criar duas pequenas funções ajudantes que ajudam na manipulação de listas. O primeiro procedure ajudante, chamado de ListSum determina a soma dos elementos em dada lista.

ListSum:=proc(S::list, Ind::list) local i, T;
  T:=0;
  for i from 1 to nops(Ind) do
    T:=T+S[Ind[i]];
  od;
  T;
end:

A segunda função ajudante, chamada de ListInd determina um subconjunto de uma lista S que é indicada pelas posições armazenadas na lista J.

ListInd:=proc(S::list, J::list) local i, T;
  T:=[seq(S[J[i]],i=1..nops(J))];
end:

O procedure principal para determinar a possível solução para o problema do subconjunto da soma, chamado SubSum, é o seguinte

SubSum:=proc(S::list, M::integer)
  local CurSub, next_index, T, Ind, CurSum,i;

Inicializa variáveis

  Ind:=[];
  CurSum:=0;
  i:=1;
  next_index:=0;
  T:=S;

Repetir o laço até alcançar o valor de soma dada.

  while not (CurSum = M) do
    printf(`The current subset %a has sum %d`, 
           ListInd(T, Ind), CurSum);
    next_index:=next_index+1;

se alcançarmos um impasse, use backtrack.

    if next_index > nops(T) 
    and Ind[nops(Ind)] = nops(T) then
      Ind:=subsop(nops(Ind)=NULL,Ind);
      Ind:=subsop(nops(Ind)=NULL,Ind);
      CurSum:=ListSum(T, Ind);
    else

se não houverem valores para a cima, utiliza-se backtrack.

      if next_index > nops(T)  then 
        next_index:=Ind[nops(Ind)]+1;
        Ind:=subsop(nops(Ind)=NULL, Ind);
        CurSum:=ListSum(T,Ind);
      fi;

Se o atual subconjunto é menor que M, então adicionamos o próximo valor ao subconjunto;

      if CurSum+T[next_index] < M then 
        Ind:=[op(Ind), next_index ];
        CurSum:=ListSum(T, Ind);
      fi;
    fi;

Se tivermos usado todos os índices, setar as variáveis para valores genéricos.

    if Ind=[] then
      T:=subsop(1=NULL, T);
      break;
    fi;
  od;

Retorna a lista sum

  ListInd(T,Ind);
end:

Executamos esse procedure no Exemplo 6 na página 588 do texto:

SubSum([31,27,15,11,7,5], 39);

Os três problemas foram atacados usando backtracking. Colorindo grafos, o problema das n-rainhas e o subconjunto da soma representam um vasto número de problemas que podem ser resolvidos usando backtracking, e o leitor irá certamente encontrar ocasiões onde as técnicas dessa sessão irão ajudar a resolver tais problemas.

Árvores de Extensão Mínima

Essa sessão explica como usar o Maple para achar a árvore de extensão mínima de um grafo ponderado. Lembre-se que uma árvore de extensão mínima T de um grafo ponderado G é uma árvore de extensão de G com o mínimo peso de todas as árvores de extensão de G. Os dois algoritmos mais conhecidos para construção de árvores de extensão mínimas são chamados de algoritmo de Prim e algoritmo de Kruskal; nós iremos desenvolver procedures em Maple que implementam ambos os algoritmos aqui. Iremos começar estudando o algoritmo de Prim. O algoritmo de Prim procede construindo uma árvore sucessivamente selecionando uma aresta de peso mínimo que extende essa árvore de seu atual conjunto de vértices. O pseudocódigo é o seguinte:

1. Comece a construir a árvore de extensão mínima T com a aresta de menor peso de todo o grafo.

2. Adicione a T a aresta de menor peso que é incidente ao vértice em T que não forma um circuito simples em T.

3. Repita o passo (2) até que nós tenhamos um total de n-1 arestas em T.

Para simplificar nossa implementação do algoritmo de Prim, primeiro criamos um procedure chamado de MinWeight, que determina a aresta de menor peso com exatamente um vértice em dado conjunto de vértices.

MinWeight:=proc(G::graph, S::set)
  local e, i, Candidates, Del, Min_Edge;

Determine o conjunto de arestas adjacentes.

  if S=vertices(G) then Candidates:=edges(G)
  else Candidates := incident(S,G); fi;
  if Candidates = {} then RETURN(NULL) fi;

Determine a aresta candidata de menor peso.

  Min_Edge:=Candidates[1];
  for e in Candidates do
    if eweight(Min_Edge,G) > eweight(e ,G) then
      Min_Edge:=e;
    fi;
  od;
  RETURN(Min_Edge);
end:

O caso especial de todos os vértices de G está incluído para dar um ponto de partida convenient para o algoritmo de Prim. Nesse caso, nós simplesmente retornamos a aresta de G de menor peso. Em todos os outros casos, a busca é restrita a arestas emanando do subgrafo induzido pelos vértices especificados. A implementação depende do fato de que o procedure incidente ache todas as arestas e deixe um conjunto de vértices particular. Ainda, a eficiência geral do algoritmo pode ser melhorada analisando-se sistematicamente uma lista ordenada de arestas, ao invés de procurar por novos candidatos a cada passo.

Dado o procedure MinWeight, a real implementação do algoritmo de Prim é direto ao ponto. Primeiro inicializamos a árvore mínima ponderada T para ser a árvore com apenas uma aresta, sendo essa aresta a de menor peso. A cada passo adicionamos uma aresta de peso mínimo que seja incidente com a atual árvore T.

Prim := proc(G::graph)
  local i, VT, V, T, e;
  new(T);
  V := vertices(G);

Adicione a aresta de menor peso.

  e := MinWeight(G,V);
  addvertex(ends(e, G), T);
  addedge(ends(e,G), T);

Repita o laço até que todas as arestas n-1 sejam adicionadas a árvore.

  for i from 2 to nops(V)-1 do
    e := MinWeight(G,vertices(T));
    if e = NULL then ERROR(`no spanning tree`) fi;

Adicione um novo vértice e uma nova aresta.

    addvertex(ends(e,G) minus vertices(T), T);
    addedge(ends(e,G),weights=eweight(e,G),T);
  od;
  RETURN( eval(T) );
end:

Nós retornamos eval(T) ao invés de apenas T, para se assegurar de que a própria árvore seja passada, e não apenas seu nome. Para testar o procedure Prim, nós encontramos uma árvore de extensão mínima do grafo ponderado do Exemplo 1 da página 595 do texto. Você pode construir o grafo usando os comandos:

new(City1):
addvertex(sf,chic,den,ny,atl,City1):
addedge( [sf,ny,sf,chic,sf,den,sf, atl],
  weights=[2000,1200,900,2200], City1):
addedge( [den,chic,den,ny,den, atl],
  weights=[1300,1600,1400], City1):
addedge( [chic,ny,chic,atl, atl, ny],
  weights=[1000,700, 800], City1):

Então, a árvore de extensão mínima é T1, dada por:

T1 := Prim(City1):

Essa árvore é melhor vista como uma árvore selecionando uma rai particula e então desenhando a árvore.

draw(Tree(sf), spantree(T1,sf));

O total peso de suas arestas pode ser computada como:

total := 0:
for e in edges(T1) do 
  total := total + eweight(e,T1) 
od:
total;

O algoritmo de Kruskal constrói a árvore ponderada minima adicionando sucessivamente uma aresta de peso mínimo que não forma um circuito simples em nenhum dos fragmentos de árvore previamente construídos. O pseudocódigo para esse algoritmo é:

1. Ordene as arestas do grafo em ordem crescente.

2. Escolha a aresta de menor peso, e.

3. Se e cria um ciclo T quando adicionado, descarte e da lista e repita o passo (2).

4. Adicione e a árvore ponderada de peso mínimo T.

5. Repita o passo (2) até que a árvore tenha n-1 arestas.

Antes de podermos implementar o algoritmo de Kruskal, precisamos ser capazes de ordenar arestas. Como nas sessões anteriores, podemos fazer isso usando as rotinas de ordenação embutidas no Maple, dando um ótimo procedura para comparação de quaisquer duas arestas.

A rotina de comparação necessária aqui é sutilmente mais complicada que a de antes, pois ela deve usar o grafo em adição com os nomes das arestas dentro da comparação. Isso pode ser feito usando o procedure template, como pode se observar a seguir. Um grafo específico é substituído por um placeholder em um template.

edgecompare := proc(G::graph) 
  subs(TESTG=eval(G) , 
    proc(a,b) 
        if eweight(a,TESTG) <= eweight(b,TESTG) then
        true else false fi;
    end );
end:

Chamando esse procedure em um grafo específico, como City1, nós criamos o procedure comparison customizado para esse grafo.

comp1 := edgecompare(City1):

Pode ser usado como

comp1(e1,e2);

Agora para ordenar a lista de arestas de City1 por peso, tudo que precisamos fazer é:

edgelist := convert(edges(City1),list);
edgelist := sort(edgelist,comp1);

Os pesos dessa lista ordenada estão em ordem crescente, como verificado mapeando o comando eweight na lista.

map( eweight , edgelist , City1);

Armados com essa rotina de ordenação, estamos quase prontos para implementar o algoritmo de Kruskal. A cada passo do algoritmo, temos uma aresta e, uma coleção de árvores T, formada por arestas de G, e G, e nós devemos determinar se a aresta e forma um ciclo. Isso é feito encontrando os componentes de T, e checando cada componente para ver se ambos os lados da aresta e estão no mesmo componente. Isso é feito pelo procedure:

InComponent := proc(e,T::graph,G::graph)
  local c,C;
  C := components(T);
  for c in C do
    if ends(e,G) minus c = {} then 
        RETURN(true); fi;
  od;
  RETURN(false);
end:

Ele faz uso do fato de que os comandos components representam cada componente por um conjunto de vértices. Agora estamos prontos para implementar o algoritmo de Kruskal.

Kruskal:=proc(G::graph)
  local E,T,i,n,e;
  E := convert( edges(G), list); # sort the edges
  E := sort( E, edgecompare(G));

comece a construir a floresta

  new(T); i := 0; n := nops(vertices(G)):
  while i < n  and E <> [] do 
    e := E[1];
    if InComponent( e , T , G ) then
       E := subs(e=NULL,E);
       next;
    fi;

adicione uma nova aresta a floresta

    addvertex(ends(e,G),T);
    addedge(ends(e,G),T);
    i := i+1;
    E := subs(e=NULL,E);
  od;
  eval(T);  # the new tree
end:

Esse algoritmo também pode ser testado na árvore City1, do exemplo 1 na página 595.

T2 := Kruskal(City1):
draw(Tree(sf), spantree(T2,sf));

Computações e Explorações

1. Mostre todas as árvores com seis vértices.

Solução

Para resolver esse problema nós usamos uma definição recursiva de árvores. Sabemos que um gráfo vazio é uma árvore, e que um grafo com apenas um vértice é uma árvore. Podemos então construir árvores mais largas a partir dessas árvores menores se pegarmos cada vértice e formarmos uma nova árvore adicionando uma folha conectada a esse vértice. Então, nós devemos criar um procedure em Maple chamado ExtendTree, que pega um conjunto de árvores com n vértices e adiciona uma nova aresta a cada árvore, retornando o conjunto resultante de árvores com n+1 vértices. A implementação em Maple é a seguinte:

ExtendTree:=proc(Trees::set) 
  local i, j, S, t, num_vertices, X;
  S:={};

Entra num laço sobre todas as árvores em dado conjunto

  for i to nops(Trees) do 
    T := Trees[i];

Adiciona novo vértice

    num_vertices:=nops(vertices(T));
    addvertex(num_vertices+1, T);

Para cada vértice, adicione uma nova aresta folha.

    for v in vertices(T) do 
      new(X[i][v]); 
      X[i][v]:=duplicate(T);
      addedge([v , num_vertices+1], X[i][v]);
      S:=S union X[i][v];
    od;
  od;
  S;
end:

Iremos agora ilustrar como formar todas as árvores com 4 vértices, e deixar a determinação de todas as árvores de tamanho mais largo serem determinadas pelo leitor:

new(StartingTree):
addvertex(1, StartingTree):
X:=ExtendTree(ExtendTree(ExtendTree(StartingTree))):
draw(Tree(1),X[1]); 
draw(Tree(1), X[2]): 
draw(Tree(1),X[3]): 
draw(Tree(1), X[4]): 
draw(Tree(1),X[5]): 
draw(Tree(1), X[6]):

2. Construa uma codificação de Huffman para as letras da língua inglesa baseada na frequência de sua ocorrência em textos comuns em inglês.

Solução

Esse problema pode ser quebrado em dois problemas menores. O primeiro problema é determinar como coletar a frequência de ocorrência para cada letra da língua inglesa. O segundo é como construir uma codificação de Huffman baseado nessa frequência de ocorrencia.

Nós já criamos o procedure de Huffman em Maple que pode ser usado para determinar a codificação de Huffman correta dada a frequência de ocorrencia de caractéres em inglês. Consequentemente, nós resolvemos o segundo problema.

Para resolver o primeiro problema, nós podemos usar o Maple para analisar uma string de texto e conta o número de ocorrencia de cada letra do alfabeto inglês. Especificamente, podemos usar strings em Maple da seguinte maneira. Suponha que nós temos uma passagem de texto que está em minúsculo e não tem pontuação. como:

input_text:=
  `the quick brown fox sat down and had lunch with me`;

Então, podemos inicializar a tabela indexada com cada carácter da língua inglesa, e então analisar input_text e contar as ocorrências de cada carácter.

Inicialização

alphabet:=`a bcdefghijklmnopqrstuvwxyz`;
for i from 1 to length(alphabet) do
  freq[substring(alphabet, i..i)]:=0;
od:

Conta a ocorrência de cada carácter

for i from 1 to length(input_text) do
  freq[substring(input_text, i..i)] := 
       freq[substring(input_text, i..i)] + 1;
od:
freq[a];
freq[e];
freq[q];

Para determinar a frequência de ocorrência das letras inglesas em certos contextos, nós podemos rodar esse programa em largas amostras de inputs. Podemos simplesmente extender nosso alfabeto e incluir pontuação e qualquer outro carácter especial que seja usado no conjunto dos caracteres. Vocè irá encontrar uma distribuição um pouco diferente para tipos diferentes de conteúdo, como literatura, correspondencia, programas de computador, e-mail etc. Vale notar que muitos livros sobre Criptografia contêm frequências de caracteres em inglês e muitas outras linguagens. Além disso, esse código pode ser usado para contar a frequência de ocorrência de qualquer conjunto de caracteres, como ASCII, francês, espanhol etc.

3. Compute o número de diferentes árvores de extensão de K_n para n = 1, 2, 3, 4, 5, 6. Conjecture uma fórmula para o número de tais árvores de extensão sempre que n for um inteiro positivo.

Solução

Esse problema pode ser resolvido facilmente usando o comando counttrees do Maple, que retorna o número de árvores de extensão únicas de um grafo não-dirigido. Então, para determinar o número de árvores de extensão únicas em K_n, n = 1..6, podemos executar as seguintes declarações em Maple.

counttrees(complete(1));     
counttrees(complete(2));     
counttrees(complete(3));     
counttrees(complete(4));     
counttrees(complete(5));     
counttrees(complete(6));

Deixamos para o leitor a conjectura da forma. Uma dica útil é para procurar por uma fórmula de forma n^{f(n)}, onde f(n) é uma simples função em termos de n.

4. Compute the number of different ways n queens can be arranged on an n \times n chessboard so that no two queens can attack each other for all positive integers n not exceeding 10.

Solução

Esse problema pode ser resolvido alterando o procedure NQueens que foi implementado nesse capítulo. Especificamente, quando uma solução é determinada, ao invés de sair do procedura, nós simplesmentes fazemos backtrack nessa solução e continuamos, até todos os caminhos possíveis terem sido examinados. Assim, o procedura vai sair apenas quando todas as soluções tiverem sido testadas. Deixamos para o leitor alterar o procedure NQueens e conjecturar a fórmula para o número de soluções em termos de n para o problema das n-rainhas.

5. Desenhe a árvore de jogo completa para damas em um tabuleiro 4x4.

Solução

Iremos oferecer uma solução parcial para esse problema; o leitor deve completar a solução. Especificamente, iremos criar um procedure em Maple chamado MovePiece que irá determinar todas as possíveis combinações de movimento dada uma peça específica que deve ser movida para algum espaço. Quando esse procedure for criado, o leitor deve determinar como representar essas posições no tabuleiro como vértices e arestas, como determinar o próximo nível da árvore jogo e se é necessária alguma condição de parada.

A implementação de MovePiece é bastante direta: examinamos cada peça que pode ser movida, e então determinamos se podemos mover a peça para frente e para esquerda ou direita, dependendo da posição atual da peça no tabuleiro e se há uma peça ocupando a possivelmente nova posição. Além disso, nós vamos determinar se uma peça pode pular e capturar uma peça de um oponente, dependendo do espaço do tabuleiro e a posição do oponente. Adicionalmente, nós vamos examinar ser a peça é rei, nesse caso, a peça pode mover tanto para frente como para trás no tabuleiro.

Agora damos uma implementação em Maple de MovePIece. Comentários em linha são dados para facilitar o entendimento do código.

MovePiece:=proc(A::matrix, piece::integer)
  local i, j, k, cur_column, is_king, S, Temp, direction;

Inicialize os valores, dependendo do valor da peça

  S:=[]; 
  if piece = 1 then direction:=-1;
  else direction:=1; fi;

Examine todas as posições possíveis no tabuleiro

  for i from 1 to 4 do
    for j from 1 to 4 do

Se tivermos achado um peça, determine se é ou não o rei.

      if abs(A[i,j])=piece then
        if A[i,j] < 0 then is_king:=1;
        else is_king:=0; fi;

Se a peça é um rei, então examine as direções pra frente e pra trás

        for k from 0 to is_king do
          if k>0 then direction:=-1*direction; fi;

Examine possíveis novas posições para ver se elas ainda estão no tabuleiro

          if i+direction >= 1 and i+direction <= 4 then
            for cur_column from -1 to 1 by 2 do
              if j-cur_column >=1 and j-cur_column<=4 then

Determine se a posição está livre

                if A[i+direction, j-cur_column] = 0 then

Mova uma única posição

                  Temp:=copy(A);
                  Temp[i,j]:=0; 
                  Temp[i+direction, j-cur_column]:=piece;
                  S:=[op(S), copy(Temp)];
                elif abs(abs(A[i+direction,j-cur_column])
      -piece)=1 then

Nós podemos ser capazes de pular uma peça

                  if (i+2*direction >=1 and 
      i+2*direction<=4) and 
                    (j-2*cur_column >=1 and 
      j-2*cur_column<=4) then

Pule uma peça

                     if A[i+2*direction, j-2*cur_column] 
      = 0 then             
                        Temp:=copy(A);
                        Temp[i,j]:=0; 
                        Temp[i+direction, j-cur_column]:=0;
                        Temp[i+2*direction, j-2*cur_column]
        :=piece;
                        S:=[op(S), copy(Temp)];
                     fi;
                  fi;
                fi;
              fi; 
            od;
          fi;
        od;
        if is_king=1 then direction:=-1*direction; fi;
      fi;
    od;
  od;

Procura por reis

  for i from 1 to nops(S) do
    for j from 1 to 4 do
      if S[i][1,j] = 1 then S[i][1,j]:=-1 fi;
      if S[i][4,j] = 2 then S[i][4,j]:=-2 fi;
    od;
  od;

Retorna lista de novas combinações do tabuleiro

  S;
end:

Para examinar esse procedure, nós vamos criar uma combinação inicial no tabuleiro, chamada A, usando a função matriz do Maple.

A:=linalg[matrix](4, 4, 
 [[2,0,2,0],[0,0,0,0],[0,0,0,0],[0,1,0,1]]);

Exercícios e Projetos

Como proposto pelo professor Umberto Rivechio, da turma XX da disciplina de Fundamentos Matemáticos para a Computação II, período 2016.1, aqui serão implementados dois exercícios em java, sugeridos pelo material original.

1. Desenvolver um método para listar os vértices de uma árvore ordenada com raiz em "level order".

Solução

Para realizar o exercício, vamos implementar a estrutura de dados de uma árvore binária através de duas classes: a classe Arvore e a classe No. Os vértices da árvore (da classe No) serão ordenados pela sua chave (int) e armazenarão um inteiro no campo valor. Além disso, terão campos que guardarão os filhos. Além do método construtor, criaremos um método para imprimir cada nó da árvore. Para poder imprimir os valores em level order, será preciso utilizar uma fila. Podemos utilizar a classe LinkedList do Java.

class No {
    public int chave;
    public int valor;
    public No filhoEsquerdo;
    public No filhoDireito;
    
    public No(int chave, int valor, No left, No right){
        this.chave = chave;
        this.valor = valor;
        this.filhoEsquerdo = left;
        this.filhoDireito = right;
    }

    public void printLevelOrder(){
        System.out.print(this.valor);

        LinkedList<No> nos = new LinkedList<>();
        
        if(this.filhoEsquerdo != null)
            nos.add(this.filhoEsquerdo);
        
        if(this.filhoDireito!= null)
            nos.add(this.filhoDireito);

        
        while(!nos.isEmpty()){
            No n = nos.remove();
            
            System.out.print(", " + n.valor);
            
            if(n.filhoEsquerdo != null)
                nos.add(n.filhoEsquerdo);
            
            if(n.filhoDireito != null)
                nos.add(n.filhoDireito);
        }
    }
}

A classe Arvore guardará a raiz da árvore. Temos um método para inserir os valores de forma que a árvore continue ordenada.

class Arvore {

    public No raiz;

    public Arvore(){
        this.raiz = null;
    }

    public void inserir(int chave, int valor){
        No n = raiz;
        No pai = null;

        while(n != null){
            if(n.chave > chave) {
                pai = n;
                n = n.filhoEsquerdo;
            } else if (n.chave < chave){
                pai = n;
                n = n.filhoDireito;
            } else {
                return;
            }
        }

        if(pai == null){
            this.raiz= new No(chave, valor, null, null);
        } else {
            if(pai.chave > chave)
                pai.filhoEsquerdo = new No(chave, valor, null, null);
            else
                pai.filhoDireito = new No(chave, valor, null, null);
        }
    }

    public void printLevelOrder(){
        if(raiz != null)
            raiz.printLevelOrder();

        System.out.println();
    }
}

Se rodarmos o seguinte código:

Arvore a = new Arvore();

a.inserir(5, 10);
a.inserir(6, 12);
a.inserir(3, 6);
a.inserir(7, 14);
a.inserir(1, 2);
a.inserir(9, 18);
a.inserir(4, 8);

a.printLevelOrder();

Obtemos o seguinte resultado:

10, 6, 12, 2, 8, 14, 18

Referências

Rosen, Kenneth H. (2002). "Discrete Mathematics and Its Applications". Material de apoio. Suplemento do Maple para o capítulo 9. Acesso em 29 de Maio de 2016.