Capítulos:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Apêndice B

• Figura 1.1: Cálculo do tempo de execução do algoritmo arrayMax.
• Figura 1.2:Exemplo de um diagrama de classes que mostra que as classes seres_humanos e cachorros são descendentes da classe Mamíferos.
• Figura 1.3:Exemplo de uma hierarquia de classes com mais níveis. A classe Veículos Terrestres é sub-classe de Veículos e super-classe de Carros e Motos. Isto faz com que a classe Veículos seja uma classe ancestral destas duas últimas, que podem herdar atributos e métodos tanto de Veículos Terrestres como de Veículos.
• Figura 1.4:Exemplo de herança múltipla (não disponível em Java).

• Figura 2.1: Modelo do funcionamento do splicing. Neste, os introns (região não codificante de um gene) são removidos, deixando apenas os exons. Algo que contribui para a imensa complexidade do ser humano é que existem várias maneiras de fazer splicing. No lado inferior direito vemos o mesmo gene sendo “cortado” de outra maneira, em um processo que chamamos de splicing alternativo. Cada forma diferente de splicing gera uma proteína diferente, posto que cada seqüência final do gene pós-splicing é diferente
• Figura 2.2: O dogma central da biologia. O dogma central não é totalmente verdadeiro. Em alguns experimentos pôde-se verificar que a quantidade de proteína não é perfeitamente correlacionada com a quantidade de RNA que a codifica (na verdade, a correlação se aproxima mais de 0,5). Isto se deve a outros fatores não embutidos no dogma central, como o controle da degradação das moléculas de mRNA e entrada de substâncias vindas do ambiente extra-celular, entre outros, mas nós não discutiremos o conhecimento biológico com este nível de profundidade aqui. Para nós, o dogma central serve como uma excelente aproximação da realidade.
• Figura 2.3: Processo completo de crossover.
• Figura 2.4: Dois crossomos realizando o crossover.
• Figura 2.5: Modelo do grafo formado pelas redes de regulação celular. Em (a) nós vemos um gene sendo regulado por vários outros genes reguladores. Entretanto, esta diferença entre regulados e reguladores não existe. A realidade é como mostrada na figura (b) em que vemos um modelo de rede formado por cinco genes que assumem o papel de regulados e reguladores dependendo de qual processo se está considerando.

• Figura 3.1: Diagrama que posiciona os algoritmos evolucionários como técnica de busca. Eles são técnicas aleatórias-guiadas que, assim como as técnicas de resfriamento simulado (simulated annealing), têm componentes aleatórios, mas dependem do estado corrente para determinar seu próximo estado. Isto é, a informação conhecida direciona a busca, o que diferencia os algoritmos evolucionários de métodos puramente aleatórios como as “random walks”. Em cinza vemos os principais tópicos deste livro, que serão cobertos em detalhes. As outras técnicas de busca são descritas de forma breve no apêndice B.
• Figura 3.2: Função hipotética com um máximo local e outro global. Uma técnica de gradiente (hill climbing que) se inicie em qualquer um dos pontos de início marcados seguirá o gradiente (direção de maior crescimento) e acabará presa no ponto d emáximo local (onde a derivada é zero). Algoritmos genéticos não têm esta dependência tão forte dos valores iniciais.
• Figura 3.3: Intuição por trás do teorema NFL. Um algoritmo elaborado especificamente para o problema A terá performance ótima para este algoritmo e seu desempenho se deteriorá rapidamente conforme nos afastamos para problemas bem diferentes de A. Um algoritmo genérico sempre terá um desempenho razoável, mas será incapaz de bater o algoritmo específico na classe de problemas para as quais este é desenhado.

• Figura 4.1: Esquema de um algoritmo genético
• Figura 4.2: Exemplo de interpretação de números reais codificados de forma binária
• Figura 4.3: Roleta viciada para indivíduos do exemplo 4.2
• Figura 4.4: Exemplo de pontos de corte
• Figura 4.5: Descrição da operação do operador de crossover de um ponto e mutação
• Figura 4.6: Diagrama mostrando a estrutura das classes definidas neste livro e seu relacionamento. A classe GA implementa todo o funcionamento do algoritmo genético e contém um Vector que armazena todos os indivíduos da população, cada um dos quais é um objeto da classe elementoGA.
• Figura 4.7: Versão final do nosso GA mais simples
• Figura 4.8: Roleta completa para a população da primeira geração do exemplo da seção 4.8.
• Figura 4.9: Operadores genéticos aplicados aos pais selecionados na primeira geração do exemplo da seção 4.8.
• Figura 4.10: Roleta completa para a população da segunda geração do exemplo da seção 4.8. Note-se que o total da soma das avaliações de todos os indivíduos aumentou, indicando que, em média, esta população é mais adaptada ao problema do que a geração anterior.

• Figura do exercício resolvido número 1.

• Figura 6.1: Funcionamento do crossover de dois pontos. O primeiro filho é formado através da escolha do material genético do primeiro pai que está fora dos pontos de corte mais o material genético do segundo pai entre os pontos de corte. O segundo filho é formado com o “resto”.
• Figura 6.2: Funcionamento do crossover uniforme
• Figura 6.3: Exemplo de operação do crossover de maioria. No caso, foram selecionados três pais e cada vez que um gene é igual em pelo menos dois indivíduos, ele é passado para o filho. No caso dos genes das posições 1, 2 e 4 (contando a partir da esquerda), dois pais decidem por maioria. No caso do gene 3, existe uma unanimidade entre os pais. Uma outra versão associa probabilidades a cada um dos genes de acordo com os pais. Assim, para determinar o primeiro bit do filho a se gerar faríamos um sorteio associando 2/3 de probabilidade ao valor 1 e 1/3 ao valor 0. No caso do terceiro bit, o filho teria 100% de chance de ter um bit igual a 1.
• Figura 6.4: Exemplo das técnicas de interpolação parâmetros, cada uma das quais está interpolando a probabilidade de um parâmetro desde 80% até o valor final de 20%.
• Figura 6.5: Exemplo de escolha do esquema dominante. Quatro indivíduos foram selecionados e foi verificado com o operador XNOR (XOR invertido) quais posições eram iguais em todos os bits. Isto permitiu criar uma máscara contendo um para os bits que são parte do esquema e zero para os bits que não são comuns a todos os indivíduos selecionados. A caixa pontilhada envolvendo três zeros mostra um problema desta abordagem: e se “quase todos” forem iguais? Isto sugere que talvez seja razoável usar uma abordagem de maioria em vez de consenso absoluto.
• Figura 6.6: Exemplo de operação do crossover uniforme com 3 pais. O primeiro sorteio escolhe os elementos que vão compor o primeiro filho. São necessários 2 sorteios, pois temos três pais e o segundo sorteio escolhe, em cada posição, um número de 0 a 2 diferente do primeiro valor sorteado para aquela posição. O terceiro filho é composto com o que sobra após compormos os seus dois irmãos.
• Figura 6.7: Exemplo de operação do crossover de dois pontos com três pais. O primeiro filho é composto pelas partes brancas de cada pai, o segundo filho é composto pelas partes cheias de cada pai e o terceiro filho pelas partes quadriculadas.

• Figura 7.1: Exemplo de uma situação em que a diversidade de uma população não pode ser medida pela função de avaliação. Todos os elementos denotados pelos círculos têm exatamente a mesma função de avaliação. Entretanto, eles são bastante distintos, representando uma boa cobertura do espaço de soluções. Já os elementos denotados pelas cruzes têm avaliações bem distintas, entretanto estão concentrados em um pequeno pedaço do espaço de estados e, como população, apresentam os efeitos diretos da convergência genética.
• Figura 7.2: Avaliação do melhor indivíduo no caso patológico apontado no exercício resolvido 7.1.a. Para que um indivíduo da primeira geração chegue “vivo” ao fim do GA, Isto implica em que o melhor de todos os indivíduos seja sempre o mesmo, do começo até o fim do GA.
• Figura 7.3: Gráficos para o exercício 2.

• Figura 8.1: Exemplo de aplicação da técnica de windowing. a) antes da aplicação da técnica. A pequena diferença entre o valor da função de avaliação (fitness) de cada indivíduo se reflete na roleta, que apresenta valores praticamente iguais para cada indivíduo. b) Aplicamos a técnica de windowing, diminuindo 19 de cada um dos membros da população, o que faz com que as qualidades que levam o indivíduo C a ser melhor que o resto passam a se destacar e seu espaço na roleta passa a ser 8 vezes maior que o espaço associado ao indivíduo B.
• Figura do exercício 14.

• Figura 9.1: Exemplo de aplicação do método do torneio com k=3. à esquerda nós temos a população com a avaliação de cada indivíduo. à direita, os elementos sorteados para cada torneio e o vencedor do mesmo, marcado com fundo cinza, que se torna o pai selecionado para o operador a ser aplicado.
• Figura 9.2: Exemplo de aplicação do método de seleção de amostragem estocástica uniforme. Os indivíduos recebem um segmento de reta proporcional à sua avaliação. No caso do primeiro cromossomo, seu segmento de reta tem tamanho igual a 0,2 que é igual à sua avaliação (200) dividia pela soma total das avaliações (1000). Posteriormente, visto que queremos sortear 6 indivíduos, um número entre 0 e 1/6 é sorteado e um ponteiro é colocado para este ponto. Depois, os ponteiros são colocados a uma distância igual a 1/6 do ponteiro imediatamente anterior e os indivíduos para os quais eles apontam são os selecionados para uso dos operadores genéticos.
• Figura 9.3: Exemplo do funcionamento do operador de amostragem estocástica uniforme quando considerado como uma roleta, ao invés de uma reta.
• Figura 9.4: Exemplos de vizinhanças em formato uni e bi-dimensionais. Nada impede que sejam usadas vizinhanças tri-dimensionais ou mesmo estruturadas ou mesmo convolucionadas, apesar de não haver estudos comprovando os benefícios de estruturas mais complexas.
• Figura 9.5: Exemplo de aplicação do método de seleção por ranking. Uma vez definidos os novos valores da função de avaliação dos indivíduos, o método da roleta pode ser usado como anteriormente.

• Figura 10.1: Exemplo de formação do código de Gray de 1, 2 e 3 bits. (a) Código de Gray de 1 bit. é só escrever 0 e 1. (b) Código de Gray de 2 bits. Espelhamos o código de Gray de 1 bit e depois colocamos 0 à frente dos números acima do espelho e 1 à frente dos números abaixo do espelho imaginário. (c) Código de Gray de 3 bits, formado da mesma maneira que o código de 2 bits. Note que os números de 0 a 3 são iguais ao código de 2 bits com um zero na frente, como seria de se esperar.
• Figura 10.2: Demonstração do processo de avaliação de um cromossomo da representação baseada em ordem para solução do problema de colorir um grafo. O processo permite dois resultados: é posível colorir ou não. é necessário criar algum tipo de função que permita obter resultados intermediários. Um exemplo é a determinação do número de nós que não puderam ser coloridos, usando-se o cromossomo corrente. Isto permite que se tenha uma avaliação entre 0 (todos os nós foram coloridos) e n-k, onde n é o número de nós e k é o número de cores.
• Figura 10.3: Exemplo de utilização do crossover uniforme não adaptado para representação baseada em ordem. Note-se como cada um dos filhos gerados tem um elemento repetido, o que é proibido na representação baseada em ordem.
• Figura 10.4: Exemplo da atuação do operador de crossover baseado em ordem
• Figura 10.5: Exemplo de operador de mutação baseado em ordem
• Figura 10.6: Exemplo de operação do crossover simples. Um ponto de corte foi escolhido de forma aleatória e os elementos foram copiados para os filhos de forma similar ao crossover de um ponto.
• Figura 10.7: Exemplo de operação do crossover flat. Uma escolha completamente aleatória é feita para os valores de cada filho, os intervalos de cada escolha limitados pelos valores máximo e mínimo de cada pai. Note que este operador é extensível para o caso de múltiplos pais, só precisando determinar o máximo e o mínimo de um grupo de n elementos, n>=2.
• Figura 10.8: Exemplo de operação do crossover aritmético, definindo o parâmetro lambda de forma arbitrária com o valor 0,3.
• Figura 10.9: Exemplo de operação do crossover discreto. Ao sortearmos o valor 0, usamos no primeiro filho a coordenada do primeiro pai e ao sortearmos o valor 1, usamos a coordenada do segundo. O segundo filho é montado com as coordenadas não usadas pelo primeiro. O funcionamento é perfeitamente análogo à maneira como opera o crossover uniforme nos cromossomos binários.
• Figura 10.10: Exemplo de atuação do operador de mutação aleatória. Os limites para o sorteio do novo valor da coordenada a sofrer mutação são dados pelas restrições e definições do problema.
• Figura 10.11: A nova hierarquia de classes, incluindo as classes definidas aqui para exceções causadas por operações com objetos da classe CromossomoReal (circundadas pela linha tracejada). Note que o ramo das exceções que nós definimos é independente de todas as outras exceções, o que garante que blocos catch não capturarão inadvertidamente exceções causadas por outros métodos que não aqueles que desejamos.

• Figura 11.1: Gráfico de uma distribuição normal com média zero e desvio padrão igual a 1.
• Figura 11.2: Evolução da área sob a curva normal de média zero e desvio padrão 1 como função do valor de x.
• Figura 11.3: Funcionamento da regra dos trapézios repetida. Note que a área total é bem aproximada pela soma das áreas dos trapézios. Existe um erro, visível na figura, mas este pode ser diminuído arbitrariamente diminuindo-se o valor de delta x. Note que o valor do limite inferior do segundo intervalo é igual ao valor superior do primeiro intervalo.

• Figura 12.1: Exemplo de uso prático de uma árvore na definição de hierarquia de objetos em Java. árvores enraizadas são estruturas naturalmente indicadas para representação de hierarquias e, apesar das árvores binárias serem as mais conhecidas, não existe nenhuma restrição formal quanto ao número de filhos que um nó pode ter.
• Figura 12.2: (a) uma série de árvores compostas de um único elemento e um candidato a raiz, r. (b) Ligando todos os elementos a r, obtemos uma nova árvore, T, que pode ser usada em um processo similar ao que levou do item (a) ao item (b), substituindo um dos elementos simples, o que permitiria que conseguíssemos árvores mais complexas. O processo pode ser repetido indefinidamente, obtendo-se árvores de qualquer complexidade desejada.
• Figura 12.3: Exemplo de definição de árvores de expressões. (a) árvore definida para a expressão x/y (b) árvore definida para a expressão x+y*3. Note que a prioridade do operador de multiplicação é naturalmente expressa pois aparecendo mais baixo na árvore, vai ser calculado primeiro.
• Figura 12.4: árvore de derivação criada para um comando while típico.
• Figura 12.5: Exemplo de como calcular a avaliação de um cromossomo calculando-se a área entre a função representada no cromossomo e a função geradora dos dados (marcados com losangos). O problema desta abordagem é a necessidade de se conhecer a função geradora, o que descaracteriza o propósito fundamental do GP.
• Figura 12.6: Exemplo do efeito do outlier. Queremos descobrir uma função que modele os dados representados pela linha sólida e temos dois candidatos: a função de linha tracejada e a função de linha pontilhada. A de linha pontilhada modela muito melhor o processo e está sempre mais próxima da função original, com exceção do ponto onde x=3. A mganitude do erro neste ponto é tão grande que faz com que esta se torne pior do que a função de linha tracejada, que não tem uma trajetória nem próxima da função real.
• Figura 12.7: Exemplo da utilização do operador de crossover com duas árvores aleatórias. Fazemos o sorteio para o primeiro nível e decidimos não fazer o cruzamento naquele ponto. Procedemos para um descendente do nó corrente escolhido de forma aleatória. Como o sorteio decidiu por fazer o crossover, intercambiamos as árvores enraizadas no nó corrente de cada pai, gerando os dois filhos.
• Figura 12.8: Exemplo de utilização do operador de mutação baseado em árvores. Um nó da árvore original é selecionado ao acaso e a sub-árvore enraizada neste nó é eliminada e substituída por outra gerada ao acaso.

• Figura 13.1: Representação de um conjunto fuzzy através do diagrama de Hassi-Euler.
• Figura 13.2: Exemplo da definição de dois conjuntos expressando conceitos linguísticos antagônicos para uma mesma variável.
• Figura 13.3: Definição de cinco conjuntos fuzzy para a variável velocidade.
• Figura 13.4: Exemplo de execução do controle em nível de regras do operador de crossover. Em (a) pode-se ver a situação em que o cromossomo 1 tem apenas uma regra para o conjunto sob análise. Neste caso, esta única regra realiza o crossover com as duas regras do cromossomo 2. Em (b) pode-se ver a situação em que ambos os cromossomos têm mais de uma regra para o conjunto fuzzy. Qualquer implementação pode escolher quais regras cruzarão de forma aleatória, mas deve garantir que cada regra realize o crossover ao menos uma vez
• Figura 13.5: Estrutura básica de um neurônio natural.
• Figura 13.6: Estrutura de um neurônio artificial. Como no caso natural, existem entradas, que são recebidas via pesos, ao invés de sinapses. O somador seguido da função degrau fazem a vez de corpo somático, e a saída equivale ao que passa pelo axônio.
• Figura 13.7: Exemplo de uma rede neural multi-camada
• Figura 13.8: Desenho de uma rede neural e exemplificação da estrutura de um gene para treinamento genético dos pesos neurais

• Figura 14.1: Exemplo de situação em que temos uma função com múltiplos objetivos que são competitivos entre si (minimizar o tempo de atendimento e maximizar o lucro), e com restrições (cada CD só pode despachar no máximo a quantidade estocada). Os círculos representam os centros de distribuição, enquanto que as estrelas representam os clientes que devem ser atendidos. Os clientes envoltos pelo círculo tracejado estão a distâncias aproximadamente iguais dos centros de distribuição 1 e 3. Se usarmos a heurística de mandar pelo CD mais próximo, qual deles deve atender estes clientes?
• Figura 14.2: O espaço de soluções admissíveis é dado pela parte cheia, enquanto que o espaço em branco é composto de soluções que não respeitam as restrições do problema. Supondo cada coordenada como numérica, pegamos duas soluções válidas (círculos) e aplicamos o crossover aritmético, gerando a solução dada pelo X, que é inválida (está na parte branca). Repare entretanto que ela, apesar de inválida, está mais próxima da solução ótima (dada pelo triângulo) do que seus dois pais. Será que ela deve ser descartada ou reparada? Métodos de reparo podem levar esta solução em qualquer uma das duas direções dadas pelas linhas pontilhadas.
• Figura 14.3: Exemplo de problema de otimização sujeito a restrições. A região admissível, marcada em fundo cinza, possui uma série de soluções (círculos), algumas das quais muito próximas à solução ótima (triângulo na parte central da figura). Existem algumas soluções inadmissíveis de baixa qualidade (X) e uma muito próxima à solução ótima (quadrado). Permitir que estes quadrados reproduzam poderia aumentar a chance de encontrarmos a solução ótima na próxima geração. Por exemplo, se considerarmos o crossover aritmético, a reprodução entre o elemento dado pelo quadrado e o elemento dado pelo círculo sem preenchimento gera uma solução que é praticamente igual ao elemento ótimo. é óbvio que o exemplo é exagerado, mas todas as soluções perto da borda do espaço admissível podem trazer qualidades interessantes que poderiam melhorar o resultado final do processo de busca.
• Figura 14.4: Exemplo de mapeamento de um espaço não convexo para um espaço convexo. Repare que todas as soluções que estiverem no novo espaço de busca (preenchido pela cor cheia e cercado pela linha tracejada) devem ser mapeadas para o espaço original (preenchido em xadrez). Esta abordagem resolve o problema do crossover, mas não o da mutação. Note o ponto dentro do novo espaço admissível, mas quase sob a borda. Se usarmos qualquer operador de mutação, a região marcada pelo círculo tracejado que envolve a solução é equiprovável. Logo, as mutação deve ser aplicada com um cuidado adicional, para verificar a admissibilidade das soluções geradas.
• Figura 14.5: Exemplo de conjuntos de Pareto. Cada dimensão corresponde a um objetivo a maximizar e cada conjunto de elementos nos círculos tracejados correspondem a soluções dominadas pelo mesmo número de outras soluções. Note que cada elemento pertencente ao conjunto dominado por apenas uma solução tem uma seta ligando-o ao elemento que o domina.
• Figura 14.6: Exemplo do grande número de elementos que pertencem ao mesmo conjunto de Pareto. Na figura, podemos ver três elementos (P1, P2 e P3) que não são dominados por nenhum outro. Ao mesmo tempo, podemos ver dois grandes fronts pertencentes ao mesmo cojnunto de Pareto, de elementos que são dominados por apenas um indivíduo. Se tivermos que escolher menos do que 3 elementos para uma estratégia elitista, qual dos melhores escolheremos? E se forem quatro? Qual dos elementos dos conjuntos circulados deve ser escolhido?

• Figura 15.1: Ilustração do processo de migração de indivíduos de uma população à outra. As n melhores soluções de uma ilha (circuladas) migraram para a outra, substituindo os n piores elementos desta (cercadas pelo quadrado pontilhado). Os melhores da ilha não somem dela, mas sim são copiados para a outra e assim, cada ilha tem seus melhores e também os melhores de cada vizinho.

• Figura 16.1: Exemplo de cromossomo em dois níveis usado por (Petrovic, 2005). O primeiro nível consiste na alocação de um conjunto de tarefas para um conjunto de máquinas. Acima, estão listas as tarefas componentes de cada conjunto de tarefas e as máquinas pertencentes a cada conjunto de máquinas. Um algoritmo simples ed alocação faz a transição do primeiro para o segundo nível, podendo ser usado até mesmo um algoritmo exaustivo, visto que o número de tarefas e o número de máquinas total em cada alocação é pequeno.
• Figura 16.2: Dois nós especiais foram criados no grafo, representando o início dos trabalhos (0, ou fonte) e o fim deles (*, ou sink). As linha sólidas representam arestas conjuntivas, ou dependências temporais. Por exemplo, a existência de uma seta com linha sólida entre as tarefas O21 e O22 significa que a primeira deve ser realizada antes da segunda. As linhas tracejadas indicam arestas disjuntivas, ou compartilhamento de máquina. Assim, a existência de uma aresta de linha tracejada entre O21 e O13 indica que estas são realizadas na mesma máquina.
• Figura 16.3: Demonstração do algoritmo de determinação do número de Prufer. (a) arestas do grafo foram numeradas. (b) selecionamos a folha de menor índice, acrescentamos seu índice à lista de folhas usadas e colocamos o nó ao qual ela se liga à direita número de Prufer. (c) repetimos o processo do item (b). (d) repetimos o processo e agora sobrou apenas uma aresta no grafo, encerrando o processo. O número de Prufer calculado é então 224.
• Figura 16.4: Exemplos de árvores filogenéticas. Os círculos representam indivíduos e círculos não nomeados, supostos ancestrais que são comuns a todos os descendentes daquele círculo. (a) árvore enraizada. Quanto mais próximo o ancestral em comum de duas globinas, mais similares elas são. (b) árvore não enraizada : não é possível determinar relações de ancestralidade entre os organismos s2 e s4.
• Figura 16.5: Exemplo de interpretação de representação baseada em listas no formato LISP. Como G e H estão dentro dos parênteses de F, então eles são descendentes deste nó. O mesmo raciocínio pode ser aplicado várias vezes e vemos que A não está dentro dos parênteses de nenhum outro nó, sendo portanto a raiz da árvore filogenética.

• Figura B.1: Exemplo de execução do método da bisseção. Na iteração 1. começamos com dois valores aleatórios, a e b, tais que f(a)*f(b)<0. Escolhemos então um ponto que divide o intervalo entre eles em duas partes iguais. Como sgn(f(c))=sgn(f(a)), fazemos a=c e vamos para a segunda iteração, onde o processo se repete. Nesta iteração, sgn(f(c))=sgn(f(b)) e fazemos b=c. O processo se repetiria até que encontrássemos a raiz ou até que f(c) menor que epsilon.
• Figura B.2: Exemplo do funcionamento do algoritmo de Newton-Raphson. Começamos no ponto x0 e traçamos a reta tangente à função neste ponto. O ponto de interceptação desta reta com o eixo das abcissas é o segundo ponto da seqüência do algoritmo, x1. Mais uma iteração idêntica e chegamos a x2. Note como nos aproximamos da solução, o ponto x*.
• Figura B.3: Exemplo de situação em que o algoritmo guloso não encontra o melhor resultado. As legendas nas arestas indicam o custo do caminho e o caminho seguido é dado pelos nós de fundo escuro. O algoritmo guloso começa pelo nó 2 pois este tem o menor custo dos destinos possíveis a partir do nó de início. O mesmo vale para o nó 3 e a conseguinte chegada no objetivo. Isto faz com que algoritmo encontre um caminho de custo 43 quando existe um caminho ótimo de custo 15 (Início -> 2 -> 6 -> Objetivo).