Estratégia gananciosa para calcular o número mínimo de raios que atingem todos os balões

7

O problema mínimo de zap abaixo é o Exercício 11 na palestra de Jeff Erickson sobre "Algoritmo Greedy" .

O problema mínimo de zap pode ser declarado mais formalmente da seguinte maneira. Dado um conjuntoC do n círculos no plano, cada um especificado por seu raio e pela (x,y) coordenadas do centro, calcule o número mínimo de raios da origem que cruzam todos os círculos C. Seu objetivo é encontrar um algoritmo eficiente para esse problema. (Veja um exemplo de "9 balões com 4 raios" na figura abaixo)

9balloons-4rays

Pergunta: Suponha que seja possível disparar um raio que não cruze nenhum balão. Descreva e analise um algoritmo ganancioso que resolva o problema mínimo de zap nesse caso especial.


Estou tendo problemas para abordar esse problema. Eu pensei que uma abordagem gananciosa seria usar o raio que cruza mais círculos e recuar, mas me disseram que isso estava errado. Por que é isso?

E qual é o sentido do fato de haver um raio que não cruza balões? Devo provar que alguma solução ótima usa esse fato?

Qualquer ajuda seria apreciada! Recentemente, comecei a aprender algoritmos :)


Algoritmo baseado na resposta de hengxin: https://cs.stackexchange.com/a/52293/42816

Prova por indução matemática

Nota: Não utilizou a implementação O (n log n)

Agora vamos provar a correção desse algoritmo usando indução matemática. Mostraremos que nosso algoritmo ganancioso não pode fazer pior do que a solução ideal.

Deixei Sseja o conjunto de raios disparados pelo nosso algoritmo ganancioso. DeixeiS ser o conjunto de raios disparados por outra solução ideal.

Nosso caso base é quando n=1 1. Existe apenas um objeto para destruir, e nosso algoritmo ganancioso usa 1 raio, o que também é ideal. Então, isso dá uma olhada.

Agora, para nossa hipótese de indução, assumiremos que nosso algoritmo guloso é ideal para até n objetos.

Afirmamos agora que o primeiro raio de α do S não pode fazer pior do que o de S.

Agora vamos considerar um n+1 1situação do objeto. Então, nós classificamosS e S de acordo com α, sentido horário. Agora vamos examinar o primeiro raio que ocorre a partir deαsentido horário. NoS, esse primeiro raio, chame-o R, não pode ser pior do que o de S, chame-o R, porque nosso algoritmo ganancioso diz que esse raio cruza a maioria dos objetos, incluindo o primeiro α. Portanto,R intercepta tanto ou menos objetos do que R. Assim, podemos substituirR com R na solução ideal S.

Agora, temos que descobrir se o resto S é ideal, cortando R, que chamaremos T. No entanto, como agora existem no máximon objetos, nossa hipótese de indução diz que nosso algoritmo ganancioso encontra uma solução ótima para T. Como tal, oR+TO problema tem uma solução ideal do nosso algoritmo ganancioso. QED

pinoyboy
fonte
"nosso algoritmo ganancioso diz que esse raio cruza a maioria dos objetos". Não vejo como essa afirmação se justifica. A maioria dos objetos de que conjunto de direções possíveis?
GTC

Respostas:

1

Princípio: Você precisa disparar os raios em alguma ordem e escolher cuidadosamente a direção / ângulo adequados para o primeiro raio.

Q1 1:Eu pensei que uma abordagem gananciosa seria usar o raio que cruza mais círculos e recuar, mas me disseram que isso estava errado. Por que é isso?

Veja a figura no problema. Suponha que haja apenas 4 balões: os dois verdes e os azuis. Se você disparar seu primeiro raio ao longo do eixo x (isso é permitido por sua estratégia gananciosa. Observe que suponho que os três balões maiores não possam ser atingidos por um único raio; caso contrário, mova-os levemente), você deixará os dois outros balões distantes. Como resultado, custa 3 raios, mas o ideal é 2.

Q2: Qual o sentido do fato de haver um raio que não cruza balões?

Portanto, o ponto principal é disparar o primeiro raio na direção certa. Aí vem o fato de que "existe um raio que não cruza nenhum balão".

A ideia básica é a seguinte:

  • encontre primeiro a direção / ângulo α ao longo do qual um raio não cruza balões;
  • identifique o primeiro balão (digamos, no sentido horário) b em relação a esta direção / ângulo α; Aquib é definido como o primeiro balão que você deixa quando você varre uma linha começando na direção / ângulo α sentido horário.
  • disparar um raio que é blinha tangente à direita (no sentido horário) eu, Remova todos os balões atingidos por eu,
  • e depois recursar.

Q3: Devo provar que alguma solução ótima usa esse fato?

Não é fácil provar que uma estratégia gananciosa está correta. Você pode tentar provar a idéia acima aplicando argumentos matemáticos de indução e troca ( ou talvez mostre que está errado! ). Uma dica é considerar o conjunto de raios disparados por um algoritmo arbitrário, classificá-los por ângulos em relação aα (horário) e compare-a com a solução ideal, uma a uma.


Implementação: nos comentários, o OP solicita umanregistronalgoritmo. Bem,nlgngeralmente significa que você pode resolver algumas coisas primeiro. Talvez classifique todos os balões pelos ângulos das linhas de emaranhado direitas (no sentido horário novamente). Então é fácil aplicar a estratégia gananciosa acima. Essa é uma ideia aproximada. Como implementá-lo eficientemente, escolhendo / projetando boas estruturas de dados, é deixado como um exercício.

hengxin
fonte
Obrigado pela resposta! Está começando a ficar mais claro para mim agora. No entanto, agora eu preciso descobrir uma idéia básica de como tornar esse algoritmo O (n log n). Você teria algum pensamento inicial? obrigado novamente!
pinoyboy
@pinoyboy nregistron? Bem, isso geralmente significa que você pode primeiro classificar algumas coisas. Talvez classifique todos os balões pelos ângulos das linhas de emaranhado direitas (no sentido horário novamente). Então é fácil aplicar a estratégia gananciosa.
Hengxin
Ahhh, isso faz sentido! Sinto muito por fazer tantas perguntas. Mas está fazendo muito sentido para mim agora!
pinoyboy
@pinoyboy Fico feliz em ajudar. Note que eu não o provei formalmente. Você deveria tentar. Tentar provar uma estratégia gananciosa é uma boa chance de aprender.
precisa saber é
11
Como você lidaria com o caso em que inicialmente não há direção ao longo da qual um raio não cruze nenhum balão? Iniciar um algoritmo de um ângulo arbitrário neste caso não parece levar a uma solução ideal ...
Maxim Mikhaylov