Ei, pilhas completas, vamos treinar as habilidades. Sugiro que amasse o giro, parece-me, é interessante fazer isso usando um paradigma diferente e incomum. A maioria dos desenvolvedores possui uma habilidade desenvolvida em algoritmo - a tarefa se transforma em peças que precisam ser conectadas, para refletir sobre a sequência de movimentos que leva à conclusão desejada.
Aqui, há uma semana, o Prologue foi mencionado. Gostaria de responder que a linguagem Prolog é adequada para resolver problemas. Eu já falei sobre esse tópico e citei várias soluções de tarefas aleatórias disponíveis para mim em um site com tarefas para algoritmos . Gostaria de mostrar que qualquer solução complexa está disponível em uma linguagem declarativa e pode não funcionar mais devagar (bem, talvez visivelmente) não muito lento).
Demorou muito tempo para apresentar o próximo problema, e a primeira solução já foi recebida, demonstro o problema e descubro como é lento.
O prólogo é interessante, pois você pode criar um programa dedutivo que mostre muitas soluções e pode até limitá-lo, mas não fornece uma maneira de iterar,
o algoritmo será desenvolvido solucionador intérprete.
Então, a tarefa é esta :
- Captação de água da chuva ii
Dada uma matriz mxn de números inteiros positivos representando a altura de cada célula unitária em um mapa de elevação 2D, calcule o volume de água que é capaz de capturar após a chuva.
Nota:
M e n são menores que 110. A altura de cada célula unitária é maior que 0 e é menor que 20.000.
Exemplo:
Dado o seguinte mapa de altura 3x6:
[
[1,4,3,1,3,2]
[3,2,1,3,2,4]
[2,3,3,2,3,1]
]
Retorno 4.
Após longas tentativas de formular uma solução, cheguei a esta redação:
É necessário derramar um máximo de água em cada célula, que não sairia dela . Sugiro derramar uma certa quantidade de água em cada célula, mas para que seja menor que o valor máximo de todos os possíveis.
Aconteceu assim:
reptest(X0,X2):- flatten(X0,FX0), sort(0,>,FX0,Vals), repdown(X0,Vals,X0,X2),!.
esse predicado pega a lista de entrada (matriz) e a transforma em uma solução, em uma matriz na qual existem outros valores que serão uma resposta válida. Em seguida, outro predicado pega essas duas listas elemento por elemento e localiza a quantidade total.
repdown(X0,Vals,X,X1):- puts(Vals,X0,X1), X\=X1, balns(X0,X1),!. repdown(_,_,X,X).
esse predicado pegará uma das soluções e verificará se está "normalmente" preenchido, se satisfaz a condição do problema, então esta é a solução.
Este é o método "gerar e verificar", dizemos que o valor está nesse conjunto e revisamos todos os elementos desse conjunto, verificando algum tipo de condição de saída.
Então, vou obter uma nova solução com o predicado put (Vals, X0, X1), aqui em primeiro lugar está uma lista de todas as alturas possíveis que estão nessa matriz, a partir da qual vamos selecionar as alturas possíveis para cada célula. De acordo com a análise dos testes de entrada, verificou-se que, neste problema, é possível preencher a célula inteira, se tanta água puder ser inserida em torno dela, que ela será derramada "sobre a cabeça".
No total, esse predicado parece mais complicado, é necessário processar as triplas de linhas que compõem um quadrado de 3x3 (sim, não há matriz no Prolog, mas parece com a descrição dos dados de entrada; portanto, usamos na programação declarativa; talvez você não conheça os índices de elementos na matriz , há apenas uma lista com cabeçalho e cauda; descreva apenas um modelo que corresponda à especificação de entrada).
puts(_,[],[]). puts(_,[X],[X]). puts(_,[X,Z],[X,Z]). puts(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,sel_biger(R2,V,R21),puts(V,[R21,R3|T],St). puts(V,[R1,R2,R3|T],[R1|St]) :- puts(V,R2,R21),puts(V,[R21,R3|T],St).
É assim que se expressa um desvio da matriz, a partir do qual você pode obter as três primeiras (e mais) linhas, das quais também é possível selecionar, da esquerda para a direita, triplos de elementos, e entre os oito vizinhos, haverá uma célula [Itaya] [Utaya] da paisagem. Com a ajuda de sel_biger (R2, V, R21), um novo significado dessa célula é criado.
Esse valor pode ser definido como a célula atual, pode ser uma das alturas possíveis e até a lista é classificada em ordem decrescente, para que o primeiro seja a altura mais alta disponível, e depois a seguinte:
sel_biger(C,[H|_],H):-H>=C. sel_biger(C,[_|T],X):-sel_biger(C,T,X).
Era uma descrição de um “gerador de decisão” e, então, você precisa garantir que a matriz obtida, a partir das alturas preenchidas arbitrariamente em cada ponto, seja semelhante à resposta que exigimos.
E era necessário encontrar um estado em que a água se depositasse nos buracos, tentarei colocar desta maneira:
de nove valores de um quadrado é três por três, no centro sempre deve haver uma altura que não contradiga o mapa de entrada, para que a mudança de equilíbrio que estava originalmente nessas células não seja obtida, se houver altura, não deve haver células acima dela, mesmo se tudo vai inundar com água, então aqui podemos dizer que a célula alta deve permanecer por si só ou ser substituída por um valor mais alto, mas de modo que seja igual a todos os vizinhos, ou seja, as células à esquerda, à direita e de cima para baixo da corrente devem exceder ou ser iguais, se houver mais água na célula, somente se ela tiver subido ao redor ...
E os dois predicados finais, que levam a matriz de entrada, iniciam a busca por um resultado adequado, subtraem a soma dos elementos entre si e localizam a soma final necessária no problema:
diffall(L0,L2,S):- flatten(L0,F0),sum_list(F0,S0), flatten(L2,F2),sum_list(F2,S2), S is S2-S0. %% , sums(X,S):-reptest(X,X1),diffall(X,X1,S).
Vou demonstrar os testes que o site forneceu.
reptest(X0,X2):- flatten(X0,FX0), sort(0,>,FX0,Vals), repdown(X0,Vals,X0,X2),!. repdown(X0,Vals,X,X1):- puts(Vals,X0,X1), X\=X1, balns(X0,X1),!. repdown(_,_,X,X). puts(_,[],[]). puts(_,[X],[X]). puts(_,[X,Z],[X,Z]). puts(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!,sel_biger(R2,V,R21),puts(V,[R21,R3|T],St). puts(V,[R1,R2,R3|T],[R1|St]) :- puts(V,R2,R21),puts(V,[R21,R3|T],St). sel_biger(C,[H|_],H):-H>=C. sel_biger(C,[_|T],X):-sel_biger(C,T,X). % balns([],[]). balns([_],[_]). balns([_,_],[_,_]). balns([B1,B2,B3|Tb],[R1,R2,R3|T]) :- blevel(B1,B2,B3,R1,R2,R3), balns([B2,B3|Tb],[R2,R3|T]). % , 33 blevel([],[],[],[],[],[]). blevel([_],[_],[_],[_],[_],[_]). blevel([_,_],[_,_],[_,_],[_,_],[_,_],[_,_]). blevel([_,U1,U2|Tu],[R,C,L|T],[_,B1,B2|Tb], [_,U10,U20|Tu0],[R0,C0,L0|T0],[_,B10,B20|Tb0]):- equ(C,[U1,L,R,B1],C0,[U10,L0,R0,B10]), blevel([U1,U2|Tu],[C,L|T],[B1,B2|Tb], [U10,U20|Tu0],[C0,L0|T0],[B10,B20|Tb0]). % , % equ(_,[],_,[]):-!. equ(C,_,C,_):-!. equ(C0,_,C,N):-C>C0,!,findall(X,(member(X,N),X<C),[]). equ(C0,[C0|T0],C,[C|T]):-!,equ(C0,T0,C,T). diffall(L0,L2,S):- flatten(L0,F0),sum_list(F0,S0), flatten(L2,F2),sum_list(F2,S2), S is S2-S0. sums(X,S):-reptest(X,X1),diffall(X,X1,S). %unit-tests framework assert_are_equal(Goal, false):-get_time(St),not(Goal),!,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, true):- get_time(St),Goal, !,get_time(Fin),Per is round(Fin-St),writeln(Goal->ok:Per/sec). assert_are_equal(Goal, Exp):-writeln(Goal->failed:expected-Exp). :-assert_are_equal(sums([[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]],4),true). :-assert_are_equal(sums([[1,3,3,1,3,2],[3,2,1,3,2,3],[3,3,3,2,3,1]],4),true). :-assert_are_equal(sums([[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]],14),true). :-assert_are_equal(sums([[2,3,4],[5,6,7],[8,9,10],[11,12,13],[14,15,16]],0),true). :-assert_are_equal(sums([],0),true). :-assert_are_equal(sums([[1]],0),true). :-assert_are_equal(sums([[2,3]],0),true). :-assert_are_equal(sums([[3],[2]],0),true). :-assert_are_equal(sums([[18,2,3],[4,5,6],[7,8,9]],0),true). :-assert_are_equal(sums([[3,5,5],[5,4,5],[5,5,5]],1),true). :-assert_are_equal(sums([[5,5,5,1],[5,1,1,5],[5,1,5,5],[5,2,5,8]],3),true). :-assert_are_equal(sums([[2,2,2],[2,1,2],[2,1,2],[2,1,2]],0),true). :-assert_are_equal(sums([[17,2,3,4,5,6,7,8,9,10]],0),true). :-assert_are_equal(sums([[9,9,9,9,9],[9,2,1,2,9],[9,2,8,2,9],[9,2,3,2,9],[9,9,9,9,9]],57),true). %:-assert_are_equal(sums([[9,9,9,9,9,9,8,9,9,9,9],[9,0,0,0,0,0,1,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,0,0,0,0,0,0,0,0,0,9],[9,9,9,9,9,9,9,9,9,9,9]],215),true). :-assert_are_equal(sums([[11,21,31],[81,9,41],[17,61,51]],12),true). :-assert_are_equal(sums([[3,3,4,4,4,2],[3,1,3,2,1,4],[7,3,1,6,4,1]],5),true). %:-assert_are_equal(sums([[78,16,94,36],[87,93,50,22],[63,28,91,60],[64,27,41,27],[73,37,12,69],[68,30,83,31],[63,24,68,36]],44),true).
Eu tive que comentar sobre os testes. nem todos passaram.
A tarefa é como acelerar isso?
Algumas soluções não podem ser encontradas, devido a uma longa pesquisa de soluções, elas são geradas muito lentamente nessa ordem; aqui a complexidade é provavelmente n !, todos os valores possíveis para cada célula da matriz são classificados.
É conveniente expressar esta tarefa em um sistema de programação em restrições, apenas no Prolog, é assim chamado: CLP (FD): Programação de Lógica de Restrições sobre Domínios Finitos.
O clp (fd) é uma biblioteca incluída na distribuição padrão do SWI-Prolog. Resolve problemas que envolvem conjuntos de variáveis, onde os relacionamentos entre as variáveis precisam ser satisfeitos.
>>
Eu formulo o problema assim:
Precisamos dessa lista, cada elemento do conjunto de valores maior ou igual ao seu valor máximo em todo o mapa, levando em consideração a limitação de que os elementos devem ser localizados claramente na ordem do líquido derramado correspondente.
É assim que eu faço a partir da lista de entrada, uma nova lista cujos elementos se tornaram desconhecidos em um determinado intervalo (do valor R2 do elemento atual ao valor máximo de V)
Na entrada, uma lista de listas; na saída, uma nova lista com a distribuição máxima de valores,
que satisfaçam a limitação dos "balanços de balanço de fluidos":
checks(X0,X2):- flatten(X0,FX), max_list(FX,Max),checks(Max,X0,X2), balns(X0,X2), flatten(X2,FX2), labeling([down],FX2). checks(_,[],[]). checks(_,[X],[X]). checks(_,[X,Z],[X,Z]). checks(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!, R21 in R2..V, checks(V,[R21,R3|T],St). checks(V,[R1,R2,R3|T],[R1|St]) :- checks(V,R2,R21),checks(V,[R21,R3|T],St).
Isso é um gerador e uma verificação ao mesmo tempo; é indicado que os elementos estão nesse conjunto e, depois de impor gradualmente uma verificação, esse conjunto é reduzido. Além disso, algo permanece e pode ser "marcado", ou seja, defina valores inteiros que satisfaçam a soma de todas as restrições. Chamar etiquetas ([para baixo], FX2) força a preencher (contato) variáveis desconhecido com valores específicos, e pode haver várias opções, mas sempre usaremos a primeira, pois foi dito que todas as variáveis se movem para baixo na pesquisa, desde os limites superiores, essas são as opções [para baixo] da pesquisa.
E você pode ver configurações complexas como:16.2.1 estratégia de seleção de variáveis
A estratégia de seleção de variáveis permite especificar qual variável de Vars é rotulada a seguir e é uma das seguintes:
mais à esquerda - rotule as variáveis na ordem em que ocorrem no Vars. Esse é o padrão.
ff Primeira falha. Rotule a variável mais à esquerda com o menor domínio a seguir, a fim de detectar inviabilidade anteriormente. Geralmente, essa é uma boa estratégia quando existem pequenos domínios para as variáveis subsequentes quando uma primeira variável é escolhida.
ffc Das variáveis com domínios menores, o mais à esquerda que participa da maioria das restrições é identificado a seguir. A aplicação de uma restrição deve remover uma subárvore, portanto, essa pode ser uma boa estratégia.
min Rotule a variável mais à esquerda cujo limite inferior é o próximo mais baixo. Observe que este é min / 0, diferente de min / 1, que determina a solução da solução e é discutido na seção anterior acima. Essa é uma boa tática se você estiver tentando minimizar algum valor global que provavelmente será menor se várias variáveis forem (por exemplo, uma solução de custo mínimo).
max Identifique a variável mais à esquerda cujo limite superior é o mais alto a seguir. Isso também é diferente de max / 1. E o conselho para min se aplica a max ao tentar maximizar um valor global.
16.2.2 ordem de valor
A ordem do valor é uma das seguintes:
up Experimente os elementos do domínio da variável escolhida em ordem crescente. Esse é o padrão.
down Tente os elementos do domínio em ordem decrescente.
Obviamente, se você tem uma distribuição assimétrica, como demonstramos em como rotular com eficiência acima, experimente elementos na primeira ordem mais comum.
16.2.3 estratégia de ramificação
A estratégia de ramificação é uma das seguintes:
etapa Para cada variável X, é feita uma escolha entre X = V e X # \ = V, onde V é determinado pelas opções de ordenação de valores. Esse é o padrão.
enumeração Para cada variável X, é feita uma escolha entre X = V_1, X = V_2 etc., para todos os valores V_i do domínio de X. A ordem é determinada pelas opções de ordenação de valores.
bissecção Para cada variável X, é feita uma escolha entre X # = <M e X #> M, onde M é o ponto médio do domínio de X. Escolha esta opção se muitas variáveis forem seleções entre um intervalo de números inteiros, um valor, em vez de um entre um conjunto de valores enumerados (por exemplo, porcentagens, vs a = 0, b = 1, c = 2)
Agora, na verdade, o que é "equilibrado" é quando a água derramada não transborda de célula para célula. Esta é a correspondência da ordem inicial dos elementos. Você pode pensar que o preenchimento das células preservará a forma da paisagem original, o que significa que, se houver uma parede, ela poderá ser coberta com água por cima, para que se torne necessariamente igual a todos os vizinhos ou se não for uma parede coberta de água ...
Considere as situações equilibradas:
-Se a célula estiver inundada, então ao lado da mesma ou até mais alta (de repente é a parede).
-Se a célula era igual à célula vizinha, então deveria ser igual à nova célula vizinha.
-E o caso extremo, a célula não mudou seu significado, e ainda que tipo de vizinhos ela tinha:
É assim que você pode transferir sua atitude para a tarefa no programa. Não é necessário que eu pense sobre um algoritmo de decisão, é importante fornecer uma descrição correta do resultado, definir corretamente todas as restrições iniciais (conjuntos de valores). Essa abordagem pode simplesmente ser “misturada” com a pesquisa usual com retorno e recursão inerentes ao Prolog. Essa é uma maneira de formular ainda mais programas declarativos do que usar os métodos Prolog clássicos .
Vou dar a solução obtida, com um conjunto de testes:
:- use_module(library(clpfd)). checks(X0,X2):- flatten(X0,FX), max_list(FX,Max),checks(Max,X0,X2), balns(X0,X2), flatten(X2,FX2), labeling([down],FX2). checks(_,[],[]). checks(_,[X],[X]). checks(_,[X,Z],[X,Z]). checks(V,[R1,R2,R3|T],[R1|St]) :- number(R2),!, R21 in R2..V, checks(V,[R21,R3|T],St). checks(V,[R1,R2,R3|T],[R1|St]) :- checks(V,R2,R21),checks(V,[R21,R3|T],St).
E mais testes :-assert_are_equal(sums([[13,16,15,18,15,15],[14,1,8,9,7,9],[19,5,4,2,5,10],[13,1,7,9,10,3],[17,7,5,10,6,1],[15,9,8,2,8,3]],36),true). :-assert_are_equal(sums([[18,13,13,17,12,11],[17,2,6,10,5,10],[11,10,2,8,8,2],[12,6,10,8,8,7],[18,4,7,6,7,4],[20,5,9,2,3,10]],18),true). :-assert_are_equal(sums([[14,20,11,19,19,16],[11,10,7,4,9,6],[17,2,2,6,10,9],[15,9,2,1,4,1],[15,5,5,5,8,7],[14,2,8,6,10,7]],11),true). :-assert_are_equal(sums([[19383,10886,12777,16915,17793,18335,15386,10492,16649,11421],[12362,27,8690,59,7763,3926,540,3426,9172,5736],[15211,5368,2567,6429,5782,1530,2862,5123,4067,3135],[13929,9802,4022,3058,3069,8167,1393,8456,5011,8042],[16229,7373,4421,4919,3784,8537,5198,4324,8315,4370],[16413,3526,6091,8980,9956,1873,6862,9170,6996,7281],[12305,925,7084,6327,336,6505,846,1729,1313,5857],[16124,3895,9582,545,8814,3367,5434,364,4043,3750],[11087,6808,7276,7178,5788,3584,5403,2651,2754,2399],[19932,5060,9676,3368,7739,12,6226,8586,8094,7539]],79058),true). :-assert_are_equal(sums([[10795,10570,11434,10378,17467,16601,10097,12902,13317,10492],[16652,756,7301,280,4286,9441,3865,9689,8444,6619],[18440,4729,8031,8117,8097,5771,4481,675,709,8927],[14567,7856,9497,2353,4586,6965,5306,4683,6219,8624],[11528,2871,5732,8829,9503,19,8270,3368,9708,6715],[16340,8149,7796,723,2618,2245,2846,3451,2921,3555],[12379,7488,7764,8228,9841,2350,5193,1500,7034,7764],[10124,4914,6987,5856,3743,6491,2227,8365,9859,1936],[11432,2551,6437,9228,3275,5407,1474,6121,8858,4395],[16029,1237,8235,3793,5818,4428,6143,1011,5928,9529]],68900),true). :-assert_are_equal(sums([[18776,12404,14443,15763,14613,14538,18606,16840,12904,14818],[15128,688,7369,7917,9917,6996,3324,7743,9470,2183],[18490,5499,9772,6725,5644,5590,7505,8139,2954,9786],[17669,8082,8542,8464,197,9507,9355,8804,6348,8611],[13622,7828,9299,7343,5746,5568,4340,5422,3311,3810],[17605,1801,5661,3730,4878,1305,9320,8736,9444,8626],[18522,3465,6708,3416,8282,3258,2924,7637,2062,5624],[12600,2036,3452,1899,9379,5550,7468,71,973,7131],[13881,4930,8933,5894,8660,163,7199,7981,8899,2996],[12959,3773,2813,9668,7190,1095,2926,6466,5084,1340]],61413),true). :-assert_are_equal(sums([[12090,17684,13376,15542,15936,19107,17445,19756,19179,18418],[16887,9412,3348,2172,1659,2009,2336,5210,6342,7587],[18206,9301,7713,7372,5321,1255,4819,4599,7721,9904],[15939,9811,3940,5667,1705,6228,1127,9150,5984,6658],[13920,9224,2422,7269,1396,4081,5630,84,9292,1972],[17672,3850,7625,5385,1222,9299,6640,6042,3898,713],[12298,6190,524,2590,8209,8581,8819,9336,7732,1155],[15994,8004,379,4769,5273,1776,8850,7255,1860,8142],[15579,5884,1993,3205,7621,9567,2504,613,1961,2754],[11326,4259,8944,8202,3202,3506,6784,2021,2842,868]],89383),true). :-assert_are_equal(sums([[19528,15189,18872,19908,19958,10498,18036,18808,17753,16248],[13303,3333,2133,1648,2890,9754,7567,1746,368,9529],[14500,8046,3788,9797,6249,6990,3303,3033,5363,2497],[10253,4892,7686,9125,1152,3996,5975,9188,9157,3729],[15436,2460,3414,3921,460,6304,28,8027,8050,6748],[17556,8902,4794,7697,8699,1043,1039,2002,428,6403],[14500,681,7647,8538,6159,5151,2535,2134,4339,1692],[12215,6127,504,5629,49,964,8285,6429,5343,6335],[13177,2900,5238,7971,6949,289,5367,7988,2292,5795],[10743,3144,2829,8390,1682,5340,3541,569,3826,4232]],100439),true).
Foram testes do site, apenas as 30 primeiras peças. O resultado é excelente, o problema é resolvido e, mesmo rapidamente, o tempo todo, até um segundo.
Você pode conferir ...
Como conclusão
A programação declarativa envolve uma formalização detalhada da tarefa, e o solucionador procurará a solução mais eficaz que satisfaça as condições.
Um pouco mais fundo no tópico, você pode abrir o minizinc , uma linguagem de programação na qual esse paradigma está incorporado. Eles formularam muitos significados, indicaram restrições e pronto, a resposta. Eles resolvem o Sudoku , mapeiam tarefas de colorir, agendam trabalhos , problemas de recursos, agendam Sugiro treinar ...