Problema C - Humanitarian Logistics


Autor: Alexandre Francisco (Instituto Superior Técnico)
Tipo de problema: Greedy + buckets/intervalos
Número de ficheiros de teste: 15

Neste problema era pedido que arranjassemos uma maneira de entregar os contentores de modo a minimizar as perdas. Este problema é no fundo uma concretização do problema de escalonamento de tarefas de tempo constante (pois todos os contentores demoram o mesmo tempo a ser entregues).

Testar todas as ordens possíves de entrega (todas as permutações possíveis dos contentores) não passava obviamente no tempo pois podiamos ter 100,000 contentores! Mas como fazer então?

Um "ditado" que pode ajudar em concursos e que costumo dar aos alunos que treino é "se não sabes o que fazer... ordena!". A verdade é que em muitos problemas, se tivermos os dados ordenados de algum modo, poderemos olhar para eles de um ângulo diferente.

Se queremos minimizar a perda, intuitivamente temos de conseguir alocar os contentores de maior valor. Imaginemos agora que temos os contentores ordenados por ordem decrescente do seu valor (em caso de empate, colocamos ordenados por id, tal como é pedido no enunciado).

Agora colocamos os contentores por esta ordem, para maximizar o valor dos contentores transportados (e minimizar o valor dos não transportados). Mas como colocá-los para não "influenciar" a possibilidade de colocação dos que estão a seguir?

Uma ideia é, de forma greedy, colocar sempre na posição "livre" o mais tardia possível tal que o contentor ainda é transportado dentro do seu prazo. Porquê? Seja P a tal posição mais tardia onde colocamos o contentor anterior. Se um outro contentor de menor valor também puder ser transportado:

  1. Pode ser colocado depois de P e portanto não fazia diferença o contentor ter sido colocado antes de P;
  2. pode ser colocado em posição ≤P e portanto colocar em P é o que garante mais "posições livres o mais tardiamente possível" para os contentores seguintes.

Caso o contentor actual não possa ser colocado, colocamos na posição livre o mais tardia possível (ou seja, no "final" do escalonamento) usando a mesma intuição de não "prejudicar" o escalonamento dos contentores que se seguem.

Provar que este algoritmo funciona sempre de forma óptima está fora do alcance desta pequena explicação e iria ocupar algum espaço, mas o que quero mostrar são as intuições por detrás das ideias. Nota que saber se um algoritmo greedy funciona sempre não é trivial! É preciso ter experiência. Um conselho que posso dar é implementarem uma versão "bruta", exaustiva, que teste todos os casos, e depois compararem os resultados em testes mais pequenos com os resultados do vosso algoritmo greedy.

Com tudo isto ainda falta algo. Como disse anteriormente, vamos precisar de saber implementar a operação "descobrir a posição livre o mais tardia possível que seja menor do que uma dada posição. Esta operação, se for feita trivialmente, é linear, ou seja, tem complexidade O(N). Como vamos ter de a fazer para todos os contentores, isto daria uma complexidade final quadrática O(N^2), o que não passa nos limites dados (cem mill contentores). Como fazer melhor?

Vou aproveitar a oportunidade para falar de um técnica interessante: o uso de buckets. Imagina que dividimos o espaço possível de Nposições em diferentes buckets, ou seja, em diferentes intervalos. Agora imagina que dividimos exactamente em sqrt(N) buckets. Então teremos sqrt(N) buckets, cada um com sqrt(N) posições: Agora imagina que cada bucket sabe se todas as suas posições já estão ou não ocupadas. Para sabermos a posição livre o mais tarde possível, teremos o seguinte apenas tems de:

No total, na pior hipóteses apenas precisamos de fazer 3*sqrt(N) "operações", o que daria uma complexidade final de O(sqrt(N)) para cada procura da primeira posição livre e O(N*sqrt(N)) para todos o processo (fazer essa operação para cada um dos N contentores).

Nota: existiam outras maneiras greedy de resolver o problema. Aqui apenas indiquei a que me veio primeiramente cabeça, e para poder exemplificar o uso desta técnica dos buckets.


Ligações interessantes: