Por exemplo, se temos um conjunto cujas tarefas são vestir cada peça de roupa, a seguinte ordem parcial pode ser formulada, onde uma peça só pode ser vestida depois que as peças sobre as quais ela se apoia (no desenho) já foram vestidas.
O desenho mostra, por exemplo, que não podemos calçar os sapatos sem antes ter colocado as meias e a calça.Existem várias ordens lineares para se vestir que obedecem à ordem topológica acima. A saída do código abaixo mostra uma das ordem possíveis. Por exemplo:
Meias, roupa íntima, camisa, calça, sapatos, cinto, luvas, casaco e chapéu.
No final do código, temos uma análise da complexidade do algoritmo, mostrando que este algoritmo é quadrático na entrada. O livro propõe um algoritmo linear, que, para ser alcançado, requer uma modificação sutil no algoritmo (ver aula 3).
/**
* MAC 2301 - Laboratório de Programação
*
* Exercício da aula 2
*
* Assunto: Lista ligada
* Aplicação: ordenação topológica
*
* O que é "ordem topológica"?
* É uma ordem parcial.
* Os inteiros possuem uma ordem "total", já que todos os elementos são
* comparáveis entre si). Já as tarefas para se construir uma casa possuem
* apenas uma ordem parcial, porque nem todos os elementos vêm necessariamente
* um antes ou depois do outro. Assim: a fundação deve ser feita antes de
* tudo. Então entre a fundação e a pintura há uma ordem: fundação < pintura
* Mas entre a pintura e a colocação do piso, não há uma ordem fixa. Com isso,
* há várias ordem possíveis em que uma casa pode ser montada.
*
* A tarefa deste
* programa é, dada uma ordem parcial de tarefas, exibir uma das possíveis
* seqüências para execução das tarefas.
*
**/
#include
#include
#define MAX 100
struct cel
{
int chave; /* conteúdo */
struct cel *prox; /* ponteiro para o próximo elemento */
} ;
/* Para não termos que digitar struct cel toda hora... */
typedef struct cel celula;
/* Inserção no começo de uma lista com cabeça */
void insere (int x, celula *lista)
{
celula *nova;
nova = malloc (sizeof (celula));
nova->chave = x;
nova->prox = lista->prox;
lista->prox = nova;
}
/* Função de remoção. Remove a lista inteira. */
void removeLista(celula *lista)
{
celula *temp;
if(lista != NULL)
{
temp = lista->prox;
while(temp != NULL)
{
lista->prox = temp->prox;
free(temp);
temp = lista->prox;
}
free(lista);
}
}
/* usado apenas para depuração */
void imprimeLista(celula *lista)
{
celula *varre = lista->prox;
printf("\n Conteúdo da lista: \n");
while(varre != NULL)
{
printf(" %d ", varre->chave);
varre = varre->prox;
}
printf("\n-----\n\n");
}
void inicializaLista(celula ** ptrLista) /* com cabeça */
{
*ptrLista = malloc(sizeof(celula));
(*ptrLista)->prox = NULL;
(*ptrLista)->chave = -1;
}
/**
* A idéia do algoritmo é termos dois vetores:
* Um guarda em [i] a quantidade de tarefas antecessores da tarefa i que
* estão ainda pendentes (i.é, que não foram executados).
* O outro guarda em [i] a lista de sucessores de da tarefa i.
*
* Lê-se os dados e monta-se essa estrutura.
*
* Então busca-se uma tarefa que possa ser executada de primeira (i.é, com
* zero antecessores), executa-se essa tarefa (no caso, apenas imprimimos na
* tela) e varre-se a lista de sucessores desta tarefa decrementando o número
* de antecessores pendentes de cada elemento dessa lista.
* Continua-se procurando outra tarefa com zero antecessores e assim
* por diante.
*
**/
int main()
{
int i,j; /* contadores */
celula *sucessores[MAX]; /* vetor com as listas (no livro é o CB)*/
int antecessores[MAX]; /* vetor que guarda em [i] o número de
antecessores pendentes da tarefa i */
int quantidadeDePares;
int quantidadeDeTarefas;
/* variáveis temporárias */
int umaTarefa, outraTarefa; /* usadas na leitura */
celula *varre; /* usada para percorrer uma lista */
printf("\n Ordenação topológica\n --------------------\n\n");
/* vamos agora ler os dados e preencher o vetor de listas */
printf("\n Digite a quantidade de tarefas a serem executadas: ");
scanf("%d", &quantidadeDeTarefas);
printf("\n Digite a quantidade de dependências entre as elas: ");
scanf("%d", &quantidadeDePares);
/* inicializando os dois vetores */
for(i = 0; i < quantidadeDeTarefas; i++)
{
inicializaLista(&(sucessores[i]));
antecessores[i] = 0;
}
printf("\n Digite os pares representando as precedências entre as");
printf("\n tarefas. As tarefas devem ser números inteiros de zero a ");
printf("\n %d e os pares devem relacionar tarefas", quantidadeDeTarefas-1);
printf(" \"vizinhas\", ou seja,\n se A antecede B que antecede C, entre");
printf(" com os pares \n A B\n e\n B C\n e não entre com o par");
printf(" implícito A C.\n\n ");
/* agora leremos os pares da entrada padrão e montaremos as listas */
for(i = 0; i < quantidadeDePares; i++)
{
scanf("%d %d", &umaTarefa, &outraTarefa);
/* A entrada quer nos dizer que umaTarefa precede outraTarefa */
/* Então insiro outraTarefa na lista de sucessores de umaTarefa */
insere(outraTarefa, sucessores[umaTarefa]);
/* E incremento o número de antecessores de outraTarefa */
antecessores[outraTarefa]++;
printf(" ");
}
printf("\n >>> Uma ordem possível: ");
/* agora vamos percorrer as listas e imprimir a resposta na saída padrão */
for(j = 0; j < quantidadeDeTarefas; j++)
{
i = 0;
while(antecessores[i] != 0)
i++; /* encontro o primeiro zero no vetor */
/* Como i não tem antecessores, essa tarefa já pode ser executada */
printf(" %d ", i);
/* agora excluímos essa tarefa (fazemos não entrar mais neste if)*/
antecessores[i] = -1;
/* agora varremos sua lista de sucessores e
decrementamos o número de antecessores deles */
varre = sucessores[i]->prox;
while(varre != NULL)
{
antecessores[varre->chave]--;
varre = varre->prox;
}
/* não vamos mais usar esta lista */
removeLista(sucessores[i]);
}
printf("\n\n ");
system("pause");
return 0;
}
/**
* Análise da complexidade:
* O laço da variável j nos diz que a complexidade do programa
* é o somatório para j variando de 0 até N-1 da complexidade do bloco
* interno a este laço. Vejamos a complexidade do bloco interno:
* 4*O(1) + O(N-j) + 2*O(M_i) = 4 + N - j + 2*M_i
* onde
* M := número de pares da entrada
* N := número de tarefas
* M_i := número de sucessores da tarefa i
* Logo, a complexidade do programa é o somatório citado da expressão acima.
* Então fica:
*
* somatório (j = 0 até N-1) de 4
* + somatório (j = 0 até N-1) de N
* - somatório (j = 0 até N-1) de j
* + 2*somatório (j = 0 até N-1) de M_i
*
* E tudo isso é igual a
* 4*N + N*N - (N*N - N)/2 + 2*M = N*N/2 + 4,5*N + 2*M = O(N*N + M)
* (note que somatório de M_i para i variando de zero a N-1 resulta em M)
*
* Deu quadrático. Existe uma versão linear deste algoritmo!! E com uma
* modificação pequena. Veja no programa da próxima aula.
*
*/
Nenhum comentário:
Postar um comentário