Problema com Grafos - "O Ladrão e o Tesouro"

[_BlondieGirl_]

Boa noite, meninos. 🙂

Trata-se do seguinte: tenho andado às voltas com um projecto e não acho uma forma eficiente de o resolver.

O enunciado é basicamente isto:

Um ladrão precisa de chegar ao tesouro, mas para conseguir isso, precisa de explodir com certas paredes, com determinada dureza, sendo que estas, protegem o tesouro.

O objectivo é determinar a quantidade mínima de explosivos necessária para o ladrão chegar ao tesouro.

Notas:

• O ladrão parte da posição (1,1), canto superior esquerdo.
  Não é possível explodir paredes "na diagonal".
  Não é possível explodir 2 paredes de seguida.
  
• 
  

O input é dado da seguinte forma:

nº linhas    nº colunas

(x, y) <--- posição do tesouro

nº paredes

(x1, y1, dureza1)

(x2, y2, dureza2)

....

(xn, yn, durezan) <-- posição de um quadrado de parede e a sua dureza.

Exemplo:

3 3  (dimensão)

5 5  (tesouro)

9    (nº paredes)

2 2 3

2 3 3

2 4 3

3 1 1

3 2 1

3 4 3

4 2 3

4 3 3

4 4 2

Sendo o resultado gráfico, isto:

http://img15.imageshack.us/img15/4927/capturaecra1i.png

Solução = 3

Porquê?

Embora fosse mais barato partir as duas paredes de "1", tal não é possível (ver notas).

Também não é possível partir paredes na diagonal, sendo que a parede "2" fica excluída.

Restam as paredes "3" e essa é a solução.

O QUE É PRECISO FAZER

Pensar! Ah pois... mas isto é alto mindfuck! Porque é possível descobrir isto facilmente "à bruta", mas o meu sistema de submissão (Mooshak) obviamente que limite a stack a 32MB, penso eu, ou qualquer coisa mesmo muito fraquinha.

A minha ideia seria ir parsando o input e construíndo conjuntos de "espaços vazios", e cada conjunto ser um nó e os arcos seriam a dureza mínima das paredes que dividem esses conjuntos.

Bastaria no fim, aplicar um Dikstra para achar o caminho mais curto do nó do ladrão ao nó do tesouro.

Vamos lá ao que interessa:

Podem ver a posição do ladrão e do tesouro e as durezas de cada parede.

http://img6.imageshack.us/img6/930/asa1.png

A ideia é preencher a estrutura à medida que se lê o input, marcando-se cada espaço vazio com o nome do seu conjunto.

Isto faz-se sempre percorrendo (linhas x colunas) quadrados... 2 for, é feio pois é, mas desta forma conseguimos o seguinte esquema:

http://img6.imageshack.us/img6/4884/asa2b.png

Em que cada letra representa um conjunto.

A laranja estão realçadas as paredes menos duras que permitem o acesso de um conjunto a outro.

A ideia é portanto, tornar cada conjunto num nó, e cada parede de acesso é um arco, com peso igual à sua dureza!

http://img16.imageshack.us/img16/8618/asa3.png

Como podem ver, a solução passa por fazer um Dikstra ao nó A e calcular o caminho mais curto até ao nó E!

Percebem?  :roll:

E de que forma preencho isto em código? Utilizando uma mega matriz, ora pois:

actual = coordenadas actuais (x,y)

input = coordenadas do prox input

à_esquerda = (x, y-1)  <--- posição à esquerda

por cima = (x-1, y) <---- posição em cima

for x = 1 until nº linhas {

    for y =1 until nº colunas {

        if ( posicao(actual) == posicao(input) )
            posicao(actual) = peso(input);

        else {

            if ( posicao(por_cima) IS conjunto
                  && posicao(à_esquerda) IS conjunto
                  && conjunto(por_cima) != conjunto(à_esquerda) )
                     conjunto(actual) = conjunto(por_cima);
                    // fazer um for aqui e andar para trás preenchendo cada espaço com o conjunto(por_cima);
                    // sair do else

            if( posicao(à_esquerda) IS conjunto)
                 conjunto(actual) = conjunto(à_esquerda);
                 // sair do else

            if( posicao(por_cima) IS conjunto)
                 conjunto(actual) = conjunto(por_cima);
                 // sair do else                
        }

    // quando se  chega aqui, vamos analisar outro quadrado.
    }
}

Desculpem o pseudocódigo manhoso, mas espero que percebam a ideia.

PORQUE É QUE ISTO É PÉSSIMO?

O máximo de linhas e colunas é 10^6, o que significa 10^12 posições. Além de extremamente lento, memória para isto... só para alocar um só inteiro, são precisos quase 40 MB.

A ajuda que eu pedia a vocês, meus caros geeks da algoritmia, era que me ajudassem numa forma de parsar o input e construir o grafo dos conjuntos sem parede, para eu depois aplicar o Dikstra!

Já ouvi falar/pensei em guardar apenas os limites de cada conjunto e fazer contas de intersecção de conjuntos, já ouvi falar em buffers temporários de algumas linhas, blá blá, muito bonito, mas ando na mesma! (entregar dia 30 de Abril)

Quero reforçar aqui a ideia de que não ando a pedinchar solução nenhuma, apenas precisava, se pudessem, de umas luzes para iluminar esta pobre cabeça universitária.

O meu obrigada (1º post  😛 )

Enunciado: http://pdfvia.com/showfile-1508/proj2.pdf

Adenda: http://pdfvia.com/showfile-1509/adenda.pdf

[mogers]

Olá,

Ainda não tive tempo de ler tudo, mas queria saber o seguinte:

Que algoritmos de grafos conheces? (para saber o que é que já dominas)

Qual é a linguagem de programação que estás a usar?

edit:

5  5  (tesouro)

3  3  (dimensão)

deveria ser

5  5  (dimensão)

3  3  (tesouro)

Preferia ver o enunciado original. Acho que estás um pouco confusa e a forma que descreveste não serve para o problema.

Qual é o limite para o número de paredes?

[_BlondieGirl_]

Olá,

Ainda não tive tempo de ler tudo, mas queria saber o seguinte:

Que algoritmos de grafos conheces? (para saber o que é que já dominas)

Qual é a linguagem de programação que estás a usar?

Preferia ver o enunciado original. Acho que estás um pouco confusa e a forma que descreveste não serve para o problema.

Qual é o limite para o número de paredes?

Isto é uma cadeira de Análise e Síntese de Algoritmos, até a semana passada tenho estado a dar toda a espécie de algoritmos em grafos: algoritmos elementares, caminhos mais curtos, fluxos máximos/mínimos, árvores abrangentes. Não te consigo dizer todos os algoritmos, porque foram imeeeensos: DFS, BFS, Tarjan, Boruvka, Floyd-Warshal, Ford-Fulkerson, Edmonds-Karp, Kruskal, Bellman-Ford, Dikstra, Johnson, Prim, ai tantos senhores, que eu sei lá.

Agora já vou em Programação Linear, mas isso já não é chamado para aqui.

Tinhas razão, alterei o meu post em cima. Tens aqui o enunciado e uma pequena adenda:

Enunciado: http://pdfvia.com/showfile-1508/proj2.pdf

Adenda: http://pdfvia.com/showfile-1509/adenda.pdf

O nº máximo de paredes é, no limite, o caso da figura 3 da adenda, penso eu.

Obrigada pela disponibilidade, desde já.

[Pedro Ribeiro]

Por respeito ao Vasco Manquinho (professor no IST, penso que também dá ASA), não te posso responder, _BlondieGirl_. Isto porque sou "colega" dele (embora eu ainda seja aluno de doutoramento)

mogers, se te "ajudar", podes ver a discussão no fórum do IST 😛

http://leic.estudante.com.pt/forum/viewtopic.php?f=38&t=4292

[mogers]

Nesse forum falam no grafo dual que era o que tinha em mente também.

Mas antes de o construir é preciso saber o limite máximo de paredes que não me parece nada que seja o daquele exemplo da adenda - edit: acho que percebi mal o que querias dizer. De qualquer modo um caso desses dava algo na ordem de 10^10 ou 10^11 paredes e isto não é praticável. Eu ainda não pensei muito a sério por causa de não conhecer este limite.

Acho que os limites do número de linhas e colunas não servem para nada.

PS: os limites de N e M estão no mooshak? No enunciado e na adenda não vi nada sobre isso.

[Warrior]

Qual é o limite de memória mesmo?

No pior caso, o número de nós será n*m/2, com 4 arcos aproximadamente cada um (obviamente que nos extremos não temos 4 arcos).

Assumindo que isto cabe em memória, podes perfeitamente usar o input a teu favor, visto vir ordenado por X e Y.

Com um algoritmo de Union Find podes montar o grafo à medida que vais lendo o input, em algo como n*m*log(n).

Vai dar um bocadinho de trabalho, mas acho que funciona.

Edit: Se por acaso o teu professor colocar o Mooshak público depois do prazo de entrega deixa por aqui o link porque fiquei com vontade de o resolver.

[mogers]

O máximo de linhas e colunas é 10^6, o que significa 10^12 posições.

Leste mesmo na diagonal pah 😛

Eu tenho dúvidas sobre o uso do Union Find aqui por causa daquela restrição de não poderes furar paredes adjacentes.

Depende do número de paredes...

[Warrior]

Basta-te verificar se as paredes são adjacentes.

A minha ideia envolvia ler "linha a linha", e tendo por base a linha anterior, ligar as células, e passar ao tratamento da próxima.

Eu não perguntei o número de linhas, mas os limites de memória.

[mogers]

Eu sei, mas manténs

em algo como n*m*log(n).

isto??

com aqueles limites é impensável...

[Warrior]

não preciso disso, basta K*log(n) em que K é o número de paredes.

O pior caso é n*m/2, mas isso nem dá para ler o input..

[_BlondieGirl_]

O limite para o 10^6 tanto para o M como para o N.

Eu penso que o limite da memória seja 32MB.

É que estamos meio desesperados, estamos quase na data de limite, e em 224 alunos, existem apenas 5 positivas (19, 15, 12, 11, 10) e 9 submissões com menos de 10...

Saí agora de um teste de Compiladores, embora com laboratórios para fazer, posso-me dedicar mais a isto.

Como alguém já falou, como o objectivo é ler o input e construir um grafo imediatamente, pensei no seguinte:

1 ou 2 buffers contendo linhas lidas anteriormente, um para a linha anterior e outro para a linha que estamos a ler e ir fazendo comparações na vizinhança de cada posição... a complexidade não deixa de ser O(N*M)... ainda não testei isto no papel a fundo.

É o caminho mais viável, não acham?

Vou pensar no assunto. Se alguma alma genial me puder aconselhar sobre como optimizar o processo, sou toda ouvidos!

@Pedro Ribeiro

Compreendo perfeitamente. 😉

[mogers]

Essa solução talvez dê para positiva.

Para mim, a chave para o problema é identificar os circuitos fechados de paredes como podes ver na primeira imagem do enunciado e construir um grafo entre as regiões fronteira destes circuitos, com peso igual à parede visinha de cada par de regiões com menor custo. Then dijkstra como já referiste: desde a região que contém 1,1 até à região que contém o tesouro.

Para a construção do grafo está a parecer-me ser necessário O(P^2) mas não tenho bem a certeza e sabendo o limite já dava para dar uma indicação se a solução era viável ou não.

Com estas ideias, para a solução óptima, os limites de N e M são irrelevantes porque o tempo de execução não depende destes.

[Warrior]

1 ou 2 buffers contendo linhas lidas anteriormente, um para a linha anterior e outro para a linha que estamos a ler e ir fazendo comparações na vizinhança de cada posição... a complexidade não deixa de ser O(N*M)... ainda não testei isto no papel a fundo.

É o caminho mais viável, não acham?

Não precisas de ir posição a posição.

O truque está no facto que se sabes que numa determinada linha há uma parede na posição K, e outra na posição L, todas as células desde K até L pertencem ao mesmo nó do teu grafo, logo não precisas de estar a criar vários nós.

[_BlondieGirl_]

Não precisas de ir posição a posição.

O truque está no facto que se sabes que numa determinada linha há uma parede na posição K, e outra na posição L, todas as células desde K até L pertencem ao mesmo nó do teu grafo, logo não precisas de estar a criar vários nós.

Sim, mas entre essa parede em K e a outra em L, esses espaços "vazios" podem estar em contacto com outros conjuntos (diferentes até) da linha anterior, e ser preciso actualizá-los.

Logo esse segmento sem paredes pertente a um conjunto sim... e qual? É necessário "olhar" para cima.

Estou certa?

[Warrior]

Exacto, só precisas de intersectar esse intervalo com todos os intervalos da linha de cima, e onde houver células em comum, juntas os conjuntos (ou seja, passa a ser um nó único).

Julgo que podes achar esses intervalos em log n com uma espécie de pesquisa binária.