Desenvolvimento de Aplicações Orientadas a Objetos: Árvores Genéricas

DAOO DESENVOLVIMENTO DE APLICACOES ORIENTADAS A OBJETOS Arvores Genéricas 1 Definigées 2 Representacées de Arvores Uma arvore genérica ou simplesmente arvore 6 um conjunto Genéricas em C finito nado vazio de elementos dos quais 3 Arvores de Jogos e um échamado raiz e os restantes estado divididos em m 0 subconjuntos disjuntos cada um deles sendo uma arvore Os termos nos folhas pai filho ancestral descendente nivel e profundidade de arvores binarias tém definigdes equivalentes para arvores genéricas O grau do no de uma arvore corresponde ao numero de seus filhos m Pela definigdo de arvores genéricas acima as arvores a e b abaixo sao equivalentes pois a definigao nao distingue a ordem das subarvores a b FIGURA 1 Exemplos de arvores genéricas Arvores ordenadas sdo arvores nas quais as subarvores de cada no formam um conjunto ordenado Quando a arvore é ordenada podemos falar de primeiro filho segundo filho e assim por diante Se consideradas ordenadas as arvores acima nao sao equivalentes A 21 Representacgdo com vetor de filhos constexpr unsigned int MAXFILHOS6 struct No TipoDado info No pai No filhosMAXFILHOS Nesta representação usase um vetor com um ponteiro para cada filho FIGURA 2 Representação por vetores Evidentemente não é uma boa idéia ter um número fixo e limitado de filhos MAXFILHOS para cada nó da árvore pois há circunstâncias em um nó deveria ter mais filhos Se aumentarmos muito o valor de MAXFILHOS podemos ter desperdício de memória A alternativa então é usar um tipo de lista ligada para os filhos a Representação Dinâmica 22 Representação Dinâmica Um nó na representação dinâmica possui os seguintes campos struct No TipoDado info No pai No filho 1o filho No prox próximo irmão A árvore genérica FGIURA 1a acima passa então a ser representada em C da seguinte forma FIGURA 3 Representação dinâmica de um árvore genérica onde os campos de cada nó são respectivamente info pai filho e prox 23 Representação de árvores genéricas como sendo árvores binárias Note a semelhança que existe entre um nó de uma árvore binária representação explícita por nós e o nó da árvore genéria representação dinâmica Assim se pensarmos no campo filho como sendo um ponteiro para a raiz da subárvore esquerda e prox como sendo o ponteiro para a raiz da subárvore direita teremos uma árvore binária A árvore binária correspondente à árvore genérica a acima seria portanto FIGURA 4 Árvore binária correspondente 3 Aplicações de Árvores Genéricas Árvores de Jogos Árvores são usadas em diversos contextos O mais familiar possivelmente é o seu uso na organização de arquivos de um sistema computacional nós da árvore são diretórios pastas e arquivos são folhas Outro uso importante no entanto é na área de jogos e inteligência artificial Game Trees Arvores de Jogos sao arvores que representam as possibilidades de jogadas para um jogador a partir de um estado do jogo Através da construgao de game trees podese determinar qual é a melhor proxima jogada a se fazer tendose como critério uma fungao chamada Avalia que retorna um valor representando quao boa uma situagao do jogo posigao do tabuleiro é para um determinado jogador Tomemos por exemplo a fungdo Avalia para 0 jogo da velha como sendo o numero de linhas colunas e diagonais que ainda estado abertas para um jogador menos 0 numero de linhas colunas e diagonais abertas para o seu adversario 0 valor maximo deve ser atribuido para uma posigao ganhadora 9 e um valor minimo para a posigao perdedora 9 Exemplo de aplicagao da fungao Avalia 2 test fey Avalia OM X 342 1 ft 2 a O X Avalia O X 9 X ganhou X O FIGURA 5 A fungao Avalia Exercicio 1 Escreva em C 0 programa que implementa a fungdo Avalia 2 Vocé consegue pensar em uma fungao Avalia melhor do que esta que esta proposta acima O problema com a fungao Avalia é que ela calcula estaticamente o valor de uma posigao do tabuleiro sem levar em conta as possiveis futuras jogadas do adversario e do proprio jogador Se for possivel prever por antecipagao o desenrolar do jogo a escolha da melhor prdéxima jogada melhoraria consideravelmente O nivel de previsao de uma game tree corresponde ao numero de jogadas futuras a considerar a partir de um dado estado do jogo e na verdade corresponde a profundidade da game tree Quanto maior o nivel de previsdo maior a quantidade de memoria e processamento exigidas para calcular e armazenar a arvore com suas numerosas possibilidades mas menor a probabilidade de se escolher uma ma jogada Exemplo de Arvore do Jogo da Velha com nivel de previsao 1 Fungdo Avalia aplicada nas folhas FIGURA 6 Árvore de jogos com nível de previsão 1 Após a construção da game tree com todas as possibilidades de jogadas alternando os jogadores e em um determinado nível de previsão para avaliar a melhor jogada para um jogador J basta avaliar as folhas da árvore com a função de avaliação estática Avalia para cada nó que não for folha e corresponder à vez do jogador J escolher o valor máximo dos filhos para cada nó não folha correspondendo à vez do adversário de J escolher o valor mínimo dos filhos supondo que o adversário fará a jogada que é pior para J Este método chamase método MINIMAX 2021 Luiz A de P Lima Jr