PKU 2064 - Pipes

Autor da análise: raphael_ribasraphael_ribas

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2064

Resumo

É dado um grid com custos nas arestas, pede-se custo do caminho hamiltoniano de menor custo.

Solução

É bem sabido que encontrar o caminho hamiltoniano de menor custo é NP-difícil no caso geral, infelizmente o problema continua sendo NP-difícil em um grid. No entanto, a estrutura do grid permite um algoritmo substancialmente mais rápido do que a força bruta.

Vamos tentar reduzir o problema dividindo o grafo em duas partes. Seja uma parte as k primeiras linhas a outra parte as linha restantes. Agora queremos construir, de forma independente, caminhos que cobrem cada uma das duas partes de forma que a união desses caminhos mais algumas arestas entre as linhas k e k+1 formam um circuito hamiltoniano. Mas para que isso funcione precisamos de algumas restrições na forma que esses caminhos são construídos. A primeira restrição é que os caminhos de uma parte precisam ter extremidades em vértices vizinhos as extremidades dos caminhos da outra parte, para isso precisamos escolher previamente quais arestas de fronteira serão usadas no circuito, então os caminhos devem conectar os vértices que incidem nas arestas da fronteira. Mas resta garantir que a união dos caminhos formam um único circuito, para isso, além de escolher quais arestas de fronteira serão usadas, também vamos decidir que par de vértices da fronteira serão cobertos pelo mesmo caminho, assim podemos saber quem fecha circuito com quem se se preocuparmos com os caminhos em si, só observando as escolhas das arestas e vértices de fronteira. Então para uma dada configuração do corte, podemos computar o menor custo de construir os caminhos da parte de cima e da parte de baixo.

Essa é uma versão preliminar do algoritmo, mas ainda temos alguns problemas para serem resolvidos. O primeiro deles é, uma vez que o grafo foi quebrado em duas partes e foi escolhido a configuração do corte, como faremos para encontrar os caminhos adequados de forma eficiente? Para isso vamos mudar um pouco a forma com que é feito o corte, vamos agora tomar o corte das k primeiras linhas mais as q primeiras colunas da linha k+1. A mesma ideia anterior de configuração do corte se aplica para esse corte, a diferença maior agora é que, dado uma solução ótima para a parte superior de uma dada configuração de corte (que inclui quais arestas de fronteira serão tomadas, quais pares de vértices de fronteira serão conectados pelos caminhos, o número k e o número q), podemos estender essa configuração passando o vértice da linha k+1 e coluna q+1 para a parte de cima, apenas tomando cuidado se é possível fazer isso conforme a configuração do corte, note que pode haver mais de uma configuração diferente para o novo corte, então todas devem ser consideradas. Outro cuidado que deve ser tomado é em atualizar a configuração do corte corretamente, poise com o novo vértice, pode acontecer que dois caminhos tenha se juntado e os pares a serem juntados devem ser atualizados e nesse caso também devemos tomar cuidado para não juntar as extremidades do mesmo caminho. No caso que o vértice adicional é o último vértice da última coluna, queremos fechar o circuito, e este caso deve ser tratado separadamente.

Com o isso o algoritmo está quase completo, nos resta uma forma eficiente de codificar a configuração de um corte. Guardar os pares de extremidades de caminhos explicitamente é muito custoso e difícil de trabalhar, principalmente na hora de fazer uma programação dinâmica para as configurações de corte. Uma observação que ajudar a codificar uma configuração é que se os vértices x e y são extremidades de um mesmo caminho e esses vértices estão nas colunas a e b respectivamente, não pode existir outro caminho com extremidades em u e v tal que u está em uma coluna entre a e b e v está em uma coluna maior do que b, senão esses caminhos se cruzariam por causa estrutura do grid. então para cada vértice de fronteira, só precisamos saber se a outra extremidade do caminho é a direita, a esquerda ou se não há nenhum caminho com extremidade no vértice. Com essa informação podemos descobrir qual é a outra extremidade de um caminho dado uma das extremidades, basta percorrer no direção da outra extremidade e contar o número de extremidades com a outra ponto para a direita e o número de extremidade com a outra ponta para a esquerda. Vamos supor que o vértice que para um dado vértice a outra extremidade está para a direita, então verificar os vértices que estão a direita, se encontrarmos um vértice com extremidade a direita então somamos um, se encontrarmos um vértice com extremidade a esquerda, subtraímos um, se o contador chegou a -1, então vértice atual a extremidade procurada. Então podemos codificar as extremidade dos caminhos com 2 bits para cada vértice de fronteira, como o grid possui no máximo 10 colunas, teremos no máximo 11 vértices de fronteira logo vamos precisar de 22 bits para a configuração dos caminhos. Esse número é bem grande pode ser necessário um preprocessamento das máscaras válidas, isto é, uma mascara é válida e o número de vértices com extremidade a direita for i gual ao número de vértices com extremidade a esquerda. Felizmente, o número de mascaras válidas não excede 6 mil mesmo para 10 colunas.

O número de configurações válidas é igual a $N M K$, onde N é o número de linhas, M é o número de colunas e K é o número de máscaras válidas. A extenção de uma configuração pode ser feita em tempo proporcional ao número de colunas que é gasto na procura das extremidades dos caminhos, portanto o algoritmo tem complexidade $O(N M^2 K)$.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License