53
edits
Changes
Jump to navigation
Jump to search
→Árvores de Extensão
== Á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:
<pre>
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:
</pre>
Nós demonstramos o uso do procedure de depth-first search com o seguinte exemplo:
<pre>
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);
</pre>
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;
<pre>
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);
</pre>
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:
<pre>
BackColor := proc(G::graph,n::integer)
local i,k, v, V, cur_vertex, Assigned, Available,
used , N, cur_color;
V:= convert(vertices(G), list );
</pre>
inicialize as cores atribuídas e disponíveis
<pre>
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];
</pre>
Atribua a menor cor ao vértice atual. Reuna todos os vizinhos do vértice atual.
<pre>
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;
</pre>
Faça um backtrack se tal cor não existir
<pre>
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:
</pre>
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.
<pre>
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);
</pre>
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.
<pre>
addedge(A,D,A,C, C1):
BackColor(C1,3);
BackColor(C1,4);
</pre>
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.
<pre>
ValidQueens:=proc(Q::matrix,
row::integer, col::integer, size::integer)
local i,return_value;
return_value:=true;
</pre>
Verifique se as dimensões são válidas
<pre>
if row > size or col > size then
return_value := false;
else
</pre>
Cheque as rainhas horizontalmente. Note que o algoritmo principal nunca posiciona duas rainhas na mesma coluna. então checagem vertical não é necessária.
<pre>
for i from 1 to col-1 do
if Q[row, i] = 1 then
return_value:=false;
fi;
od;
</pre>
Cheque as rainhas em duas diagonais.
<pre>
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;
</pre>
Retorne o valor
<pre>
return_value;
end:
</pre>
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:
<pre>
NQueens:=proc(n::integer)
local cur_col, cur_row, Q, bad_position, Assigned;
</pre>
Inicie Queens
<pre>
Q:=linalg[matrix](n, n, 0);
cur_col:=1; Assigned:=[];
while cur_col >= 1 and cur_col <=n do
</pre>
Atribua uma rainha a próxima coluna
<pre>
bad_position := true;
cur_row:=0;
</pre>
a primeira posição disponível funciona?
<pre>
while cur_row < n and bad_position do
cur_row := cur_row+1;
bad_position := false;
</pre>
bad é true se houver um vizinho com vértice colorido
<pre>
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;
</pre>
Usa backtrack se não tiver nenhum posição disponível pra rainha.
<pre>
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
</pre>
Se o posicionamento da rainha é atualmente válido, mova para a próxima
<pre>
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:
</pre>
Agora nós usamos o procedure NQueens para resolver o problema de n-rainhas quando n = 3 e n = 4.
<pre>
NQueens(3);
NQueens(4);
</pre>
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.
<pre>
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:
</pre>
A segunda função ajudante, chamada de ListInd determina um subconjunto de uma lista S que é indicada pelas posições armazenadas na lista J.
<pre>
ListInd:=proc(S::list, J::list) local i, T;
T:=[seq(S[J[i]],i=1..nops(J))];
end:
</pre>
O procedure principal para determinar a possível solução para o problema do subconjunto da soma, chamado SubSum, é o seguinte
<pre>
SubSum:=proc(S::list, M::integer)
local CurSub, next_index, T, Ind, CurSum,i;
</pre>
Inicializa variáveis
<pre>
Ind:=[];
CurSum:=0;
i:=1;
next_index:=0;
T:=S;
</pre>
Repetir o laço até alcançar o valor de soma dada.
<pre>
while not (CurSum = M) do
printf(`The current subset %a has sum %d`,
ListInd(T, Ind), CurSum);
next_index:=next_index+1;
</pre>
se alcançarmos um impasse, use backtrack.
<pre>
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
</pre>
se não houverem valores para a cima, utiliza-se backtrack.
<pre>
if next_index > nops(T) then
next_index:=Ind[nops(Ind)]+1;
Ind:=subsop(nops(Ind)=NULL, Ind);
CurSum:=ListSum(T,Ind);
fi;
</pre>
Se o atual subconjunto é menor que M, então adicionamos o próximo valor ao subconjunto;
<pre>
if CurSum+T[next_index] < M then
Ind:=[op(Ind), next_index ];
CurSum:=ListSum(T, Ind);
fi;
fi;
</pre>
Se tivermos usado todos os índices, setar as variáveis para valores genéricos.
<pre>
if Ind=[] then
T:=subsop(1=NULL, T);
break;
fi;
od;
</pre>
Retorna a lista sum
<pre>
ListInd(T,Ind);
end:
</pre>
Executamos esse procedure no Exemplo 6 na página 588 do texto:
<pre>
SubSum([31,27,15,11,7,5], 39);
</pre>
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 ==
