#5 Exercícios Aleatórios

Neste post vou comentar sobre os seguintes exercícios de grafo:

Defesa ao Grafo – Busca em Largura, algoritmo de Dijkstra
Preso ao Castelo – variação de Busca em Largura

Como de costume, eu recomendo que vocês tentem resolver o exercício acima antes de ler a solução abaixo. Assim suas teorias podem ser comparadas/contrastadas com as minhas, e isso pode ajudar no aprendizado.

Defesa ao Grafo – [uri]

Vejamos, para descobrir se o monstro consegue chegar até o castelo vivo precisamos saber (3) quanto de dano ele vai levar. Para descobrir quanto dano ele vai levar precisamos descobrir (2) qual caminho ele vai seguir. Para descobrir qual caminho ele vai seguir precisamos saber (1) quanto de dano cada vértice leva a cada momento.

Essa foi minha abordagem lógica “recursiva” de como resolver este exercício. Precisamos agora atacar cada um dos problemas individualmente e na ordem correta:

(1) Uma estratégia útil aqui é descobrir, para cada vértice, quanto de dano um monstro levaria se ele estivesse ali. Para descobrir isso podemos fazer uma busca em largura iniciando em cada torre, e para cada vértice v a uma distância de no máximo Ai daquela torre adicionamos Ci de dano sendo infringido em tal vértice.

(2) Agora que sabemos quanto de dano cada vértice leva, precisamos descobrir que caminho um monstro tomaria para chegar do vértice v até o castelo. Como vamos calcular isso para todos os vértices v, podemos abordar isso pela ordem contrária: que caminho um monstro tomaria para chegar do castelo até todos os outros vértices.
Se considerarmos o peso da aresta direcionada entre u e v sendo igual ao dano que as torres dão no vértice v, podemos aplicar o algoritmo de Dijkstra.

(3) Assim que descobrimos o caminho mínimo entre cada vértice v e o castelo podemos descobrir quanto de dano um monstro levaria, e comparamos então esse valor com os pontos de vida daquele monstro.

A complexidade do algoritmo aqui é (1) P*(N+M) + (2) N*lgN + (3) Q.

Há outras maneiras de se resolver este exercício, mas notem que o limite da variável Q é consideravelmente maior que os das variáveis N, M e P. Logo, é desejável que o trecho de código que envolve a maior variável seja o menos complexo (nesse caso, o algoritmo é linear em Q).

Preso no Castelo – [uri]

É possível notar que há dois grafos nesse problema: o primeiro é o grafo original, não-direcionado; e o segundo é o grafo das chaves, direcionado, com uma aresta que liga as salas que tem uma chave para as salas que são abertas com tais chaves. Por exemplo:

image

Para visitar todas as salas do exemplo acima, uma ordem válida seria: 1, 3, 2, 3 (volta) e 4.

Podemos resolver este exercício com o que pode ser considerado uma abordagem construtiva.

Em teoria, imagine dois conjuntos de vértices, dentro e fora, onde o conjunto dentro contém todos os vértices que são alcançáveis pelo vértice inicial dadas as restrições do exercício, e o conjunto fora contém todos os vértices que ou não são alcançáveis ou ainda não foram testados.

Inicialmente, adicione ao conjunto dentro o vértice inicial, e no conjunto fora todos os outros vértices do grafo.

Agora para cada vértice v do conjunto fora, procure por um vértice a no conjunto dentro que tenha uma aresta para v no grafo 1 (original), e um vértice b no conjunto dentro que tenha uma aresta para v no grafo 2 (chaves). Se ambos a e b existirem, transfira o vértice v ao conjunto dentro e repita o processo.

Essa abordagem é considerada construtiva pois a cada iteração o conjunto dentro é acrescentado de um vértice, que por sua vez pode contribuir nas próximas iterações do algoritmo.

Para implementar esse processo é possível utilizar uma variação do algorítmo de busca em largura, o qual deixo como tarefa.

 

Qualquer dúvida, sugestão ou crítica, favor deixar um comentário abaixo 😉

4 ideias sobre “#5 Exercícios Aleatórios”

  1. Confesso que ainda não tentei resolver o problema da Defesa ao Grafo, mas o do Preso no Castelo já, e tenho que admitir que sua solução é muito mais elegante que a minha (que é uma gambiarra na verdade).

    Qual seria a complexidade desse algoritmo no pior dos casos?

    Encontrei o seguinte: Para cada vértice do conjunto fora procuramos por um vértice que esteja ligado a ele que também tenha uma chave que o abra, supomos que no pior dos casos esse vértice tenha grau m, então fazemos n*m procuras. Além disso, para cada vértice temos que analisar se tem uma chave que o abra, mas isso pode ser feito apenas utilizando algum sistema de flags gerando um tempo de O(1) para essa busca. Por fim, devemos considerar também que em uma sala pode haver mais de um chave, então teríamos que iterar sobre essa lista quando selecionarmos um novo vértice para entrar ao conjunto de dentro. Ficando por fim O(n(m + k)) tal que k é o maior tamanho da lista de chaves em um vértice qualquer. Será que me precipitei ou bate com seus cálculos?

    10 doletas por mês aí Cristhian, não vai gastar tudo em café huahuahua.

    Valeu!

    1. Olá Marcos.

      Na primeira parte da sua análise eu diria que a complexidade seria n+m (para cada vértice listamos todas as suas arestas). Na segunda parte eu concordo com a flag de complexidade constante. É possível tirar vantagem da segunda parte e pular essa terceira. E por conclusão eu diria que no pior dos piores dos casos a complexidade seria igual a O(n (n + m + k)). Se quiser podemos discutir mais sobre por e-mail.

      Há de fato mais de uma maneira de se abordar esse problema. A sequência de passos que eu citei no post é bem teórica, e acredito que se seguirmos os passos literalmente chegaríamos à complexidade que acabei de citar.

      Por outro lado é possível fazermos alguns cortes, chegando a diminuir a complexidade para O(n + m + k) (busca em largura).

      Aliás, obrigado pelo apoio no Patreon, estou te devendo um exercício haha.

  2. Olá Cristhian, tenho acompanhado seu blog e foi muito produtivo para min, gostaria de te pedir, se possível, se você poderia postar sobre bipartite matching, já li em vários lugares e não conseguir entender sobre como modelar o grafo e o algoritmo para isso, tenho até uma disciplina optativa na faculdade esse semestre que só trata de algoritmos em grafos e a ultima aula foi sobre isso, tem um problema que eu gostaria que você postasse a solução se possível, Software Allocation – UVA, ou então um modelo genérico para abordagem de problemas deste tipo, desde já, obrigado.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *