À questão de Wirth e correntes

Algoritmos + estruturas de dados = programas - Virt N.

“Tivemos uma oportunidade maravilhosa de realizar um exercício tático pequeno, mas extremamente instrutivo”

Apesar da primeira epígrafe deste post, permito-me discordar do autor e tento mostrar que, em alguns casos, a escolha certa da estrutura de dados pode ser mais significativa do que a escolha certa de algoritmos. Para ilustrar uma tese tão sediciosa, consideremos uma tarefa simples, mas promissora, para estudar o jogo "Cadeia".

Primeiro, sobre as regras do jogo - dois jogadores jogam, a posição inicial consiste em N objetos localizados nas proximidades. O próximo passo é remover qualquer um ou dois objetos localizados nas proximidades (você pode tentar dar uma definição formal de "localização próxima", mas é compreensível em um nível intuitivo). O jogador que remove o último objeto ganha - o jogo direto, ou aquele que deve (você não pode pular a jogada) pegar o último objeto - o jogo inverso vence. Como nesta versão das regras, um jogo direto será simplesmente desinteressante (mais sobre isso mais tarde), uma restrição adicional é introduzida - apenas um objeto pode ser excluído na primeira jogada.

Primeiro, determinamos que o jogo é finito, porque a cada movimento o número de objetos diminui estritamente e o jogo termina quando o número de objetos calculado por zero é atingido, portanto, temos o direito de contar com sucesso no estudo desse jogo. Além disso, é óbvio que o jogo não pode durar mais que N movimentos, lembremo-nos desse fato.

O estudo do jogo consiste em determinar se, para um número inicial específico de objetos, o jogador que está fazendo o primeiro movimento está ganhando (já que este é um jogo com soma zero, caso contrário ele está perdendo) com um jogo ideal de ambos os lados e em qual número mínimo de movimentos o ganho é alcançado (ou por qual é o número máximo de movimentos que a perda se afasta).

Para alguns de H, a resposta é óbvia - com um objeto, o primeiro ganha um jogo direto em um turno e também perde um jogo inverso (P1 = 1, I1 = -1). Com dois objetos, o primeiro jogador perde em dois movimentos em um jogo direto e vence em dois movimentos em inverso (P2 = -2, I2 = 2), o que pode dar origem a uma hipótese sobre a simplicidade de avaliar esse jogo, confirmada pelo caso de três objetos (P2 = 3, I3 = -3). Felizmente (caso contrário, este post não teria sido publicado), um jogo com quatro objetos muda um pouco a imagem (P4 = -4, mas I4 = -3), portanto, é realmente necessário pesquisar o jogo.

Para alguns de H e para um certo tipo de jogo, existem algoritmos heurísticos que oferecem recompensa garantida. Por exemplo, para um jogo direto com um inicial H ímpar, você pode ganhar se remover o objeto central com o primeiro movimento e depois repetir os movimentos do oponente usando um local central como o eixo de simetria; então, garantimos que vamos pegar o último objeto e vencer. A mesma estratégia funcionaria com um número par de objetos, se não fosse pelas restrições na primeira jogada, o que torna o jogo não tão trivial. De um modo geral, o uso de estratégias simétricas é uma ocorrência bastante comum na contagem de jogos, mas não uma panacéia, porque, por exemplo, em nosso jogo inverso, essa estratégia falha. Deve-se notar que as heurísticas fornecem um algoritmo vencedor, mas não fornecem uma estimativa precisa da posição, pois pode haver estratégias que levam a ganhos mais rápidos (esse é o caso desse jogo em particular).

Como podemos fazer uma avaliação do jogo - exatamente como recebi as estimativas anteriores para 1 a 4 objetos - o método é chamado de pesquisa exaustiva de cima para baixo - devemos considerar a árvore completa do jogo, ou seja, todos os movimentos possíveis para ambos os lados e avaliar cada posição, incluindo fonte, de acordo com certas regras. Deve-se observar que a existência de heurísticas bem-sucedidas não nos garante uma avaliação precisa, pois responde apenas à primeira metade da pergunta - quem vence, mas não fornece o número mínimo necessário de jogadas.

Isso significa que devemos construir uma árvore de jogo completa, mas antes de prosseguir com a construção, devemos criar um modelo do objeto em estudo, no nosso caso, o jogo.

Por que me concentro nesse estágio - porque não podemos explorar o objeto em sua concretização material. Não, puramente teoricamente isso é possível (“pouco é possível no mundo em geral puramente teoricamente”) e posso imaginar uma imagem em que um número muito grande de robôs joga muitos jogos no mundo real, mas os custos de material para uma solução para o problema de avaliar o jogo excedem o quantidades, então somos forçados a embarcar no caminho de modelar objetos reais com suas contrapartes de software. E aqui é muito importante seguir uma linha fina, combinando um nível suficiente de adequação do modelo e a simplificação necessária.

Mas primeiro, um pouco de matemática para avaliar a complexidade da tarefa - precisamos classificar todos os movimentos possíveis no jogo (atenção não são todas as posições possíveis, este é o tópico de outro método, ou seja, os movimentos) e gostaríamos de avaliar a quantidade necessária de recursos antes de começar o trabalho - para determinar a ordem da tarefa. No primeiro movimento, temos a oportunidade de remover qualquer chip (continuarei chamando objetos) de H disponível, no próximo movimento - qualquer um dos restantes H-1 ou dois chips próximos (não haverá mais do que H-2), que fornece o número total de opções Hx (H-1 + H-2). É fácil ver que, após o terceiro movimento, temos Hx (H-1 + H-2) x (H-2 + H-3 + Δ) e assim por diante.

Se nos restringirmos em cada colchete apenas aos primeiros termos da soma, obteremos uma estimativa do número total de movimentos como H!, O que nos fornece uma estimativa nas quadraturas de H ^ H.

Esse é um resultado muito desagradável, que afirma que teremos problemas muito grandes com o H significativo, de modo que a modelagem "provável" implicará custos computacionais significativos. Por exemplo, para 16 fichas na posição inicial, precisaremos considerar aproximadamente 16! = 10 × 13 jogadas, e se uma jogada for 10E-9 segundos (estimativa bastante otimista), o tempo total será de 10E4 segundos ou quase 3 horas, o que é um pouco demais , mas aceitável, mas por apenas 20 chips, o tempo de cálculo esperado é de 77 anos, o que é claramente inaceitável. O fatorial está crescendo muito rápido e não há nada a ser feito sobre isso.

Chamamos atenção para o fato de que o número de movimentos excede significativamente o número de posições possíveis, que é de apenas 2 ^ N, e é óbvio que cairemos em uma posição separada por 16 fichas 10E (13-5) = 10E7 vezes, o que é uma ocorrência bastante comum para tarefas de pesquisa. Lembre-se deste fato, será útil para nós mais tarde.

No entanto, começaremos a escrever um programa, para o qual determinaremos o modelo. Primeiro, numeramos os chips de 1 a H, depois criamos uma matriz com o número de elementos H e determinamos que o número 1 no elemento da matriz com índice n significa a presença do número de chip n e o número 0 - sua ausência em uma posição específica. Esse modelo é adequado, simples, intuitivo e permite efetivar as operações de remoção de cavacos, além de determinar a condição de "proximidade".

Agora que temos um modelo (estrutura de dados), podemos começar a puxar (corujas do mundo) o algoritmo desse modelo. O algoritmo de enumeração completa com retorno é simples no diagrama de blocos e consiste em duas partes independentes - a enumeração e avaliação das posições, para começar, implementaremos a primeira parte. Observe que esse algoritmo não é melhor implementado dentro da estrutura do paradigma de programação estrutural e seria um pouco mais eficaz se nos permitirmos usar uma transição ou repetir o código, mas mesmo sem esses desvios do estilo, a implementação não é de forma pretensiosa (a complexidade ciclomática é bastante aceitável) . Como ainda não introduzimos uma avaliação e gostaríamos de obter o resultado do programa, simplesmente derivamos as posições em consideração e as examinamos com nossos olhos para avaliar a implementação correta e garantir que os resultados correspondam aos esperados.

Agora vamos adicionar uma estimativa de posição - é claro, o código bem escrito é auto-documentado (embora haja opiniões diferentes sobre essa afirmação), mas essa parte é melhor descrita em palavras. A idéia é que damos uma avaliação inequívoca das posições finais (no nosso caso, é única e consiste em zero fichas), com base nas regras do jogo, e para todas as outras posições, damos uma avaliação neutra preliminar e depois começamos a refiná-la, movendo a estimativa para a árvore . Ao retroceder, a estimativa da posição atual muda em um na direção de zero, depois é invertida e transferida para a posição anterior, onde é combinada com a estimativa anterior de acordo com as seguintes regras:

1. avaliação neutra muda para uma nova,
2. uma classificação positiva muda para uma menor positiva,
3. uma avaliação negativa muda para uma grande negativa ou positiva.

Depois de passarmos por todas as jogadas, a avaliação da posição inicial é final.

Adicionamos estimativas ao nosso procedimento para gerar todas as posições e podemos admirar os resultados da análise, exibidos em uma tabela, adicionar um contador de progresso e um contador de tempo para a análise. No compilador gcc (no modo de otimização -O2) em uma máquina com um processador, recebi uma tabela que confirma totalmente nossas suposições iniciais sobre a ordem fatorial de complexidade da tarefa. Da mesma tabela, vemos que parei de esperar resultados com H superior a 11, porque o tempo de cálculo se tornou inaceitável (para mim, talvez você esteja pronto para esperar meia hora) e nossa suposição sobre o curso e o nanossegundo não corresponde à realidade (tempo médio consideração da posição é de 100 segundos). Surge a pergunta - o que devemos fazer se quisermos ter uma estimativa para mais de 11 fichas na posição inicial.

Poderíamos pegar o caminho de pequenas otimizações, brincar com transições e sinalizadores, entrar em inserções de montador, aplicar operações vetoriais complicadas no sistema de instruções do nosso processador e, dessa maneira, você pode ganhar velocidade sem ambiguidade às vezes, por uma ordem de magnitude - talvez duas ordens de magnitude - é muito improvável, mas precisamos de um ganho de muitas ordens de magnitude, já que na ordem (e até mais) vamos aumentar um H em um em mais de 10. A propósito, se você apenas ativar a otimização do compilador, isso fará algo para nós e o tempo de execução diminuirá Eu tenho 4 vezes - não é mau em tudo e em linha com as nossas expectativas.

Portanto, devemos primeiro tentar melhorar os algoritmos aplicados, e o primeiro deles (e o principal) aprimoramento é o método de força bruta de corte ou o "procedimento alfa-beta". Sua idéia principal parece bastante robusta e consiste no fato de que se classificarmos uma determinada posição como vencedora, paramos de melhorar a classificação para essa e voltamos à árvore. Essa abordagem pode aumentar bastante a velocidade do algoritmo, especialmente se investigarmos movimentos bem-sucedidos (levando a uma vitória) em primeiro lugar. Mas também pode aumentar o tempo, uma vez que a verificação da avaliação atual é adicionada e o procedimento de escolha do curso é complicado, é muito difícil estimar a influência desse método com antecedência, é necessário realizar um experimento. E mais uma consideração - não devemos esquecer que, no caso de uma pesquisa com um ponto de corte, no caso de uma posição vencedora, fornecemos uma estimativa verdadeira, mas não precisa, uma vez que não consideramos parte das opções e elas poderiam obter uma vitória em menos movimentos. Se tal redução na precisão nos convém, por que não usar esse método, mas para uma avaliação precisa, nada além de pesquisa exaustiva não funciona.

Os resultados da enumeração de recorte são mostrados na tabela a seguir e vemos que há um ganho de desempenho e um aumento significativo, mas não o suficiente para estudar grandes valores de N. Em que direção continuaremos nossa pesquisa - primeiro, examinaremos outra estrutura de dados, bem, e então, você adivinhou (é bom lidar com um público astuto) é outro algoritmo.

Vamos prestar atenção ao fato de que a estrutura de dados adotada por nós torna os chips únicos e, por exemplo, um único chip (não tendo adjacente) na posição não é equivalente a um único chip na posição n + 2, o que está completamente errado. Selecionamos o elemento-chave da posição do jogo - o grupo de fichas localizado próximo a ele e determinamos sua principal característica - o número de fichas no grupo. São essas informações que determinam exclusivamente qualquer posição no jogo, e devemos apresentá-las de uma forma conveniente para a programação. Escolhemos a estrutura de dados mais simples e óbvia - iniciamos uma matriz de elementos H e armazenamos no elemento n da matriz o número de grupos com exatamente n chips. Então, por exemplo. Para a posição inicial com 3 fichas, teremos a representação {0,0,1}. O procedimento de execução para a apresentação dada ainda é simples e eficaz, embora, é claro, seja mais complicado do que na primeira versão. Após o primeiro movimento (dos quais havia dois em vez de três), obtemos as posições {0,1,0} e {2,0,0}.

Vamos tentar estimar o ganho esperado no número de movimentos para uma determinada estrutura de dados. Para o primeiro movimento, temos (H-1) / 2 + 1 opções, para o segundo (dividimos o grupo H em me N-m-1) (m-1) / 2 + (N-m-1-1) / 2 (pegue 1 chip) + (m-2) / 2 + (N-m-1-2) / 2 (pegue 2 chips) = (H-3) / 2 + (H-5) / 2 e por analogia , concluímos que a cada passo economizamos pelo menos metade dos movimentos. Então nosso ganho deve ser de pelo menos 2 ^ H, o que é muito, muito bom para H. grande De fato, o ganho será ainda maior, por exemplo, para a posição {8,0 ...} na primeira modalidade, você precisará ordenar 8 movimentos e no segundo apenas 1 e o ganho neste caso será 8 vezes. Portanto, podemos contar com 2 ^ H, mas esperamos muito mais, o que verificaremos. E com certeza, para o programa de acordo com essa representação, obtemos a Tabela 4, a última linha mostra o ganho de desempenho ao mudar para a segunda versão da estrutura de dados (calculada manualmente). O crescimento é simplesmente colossal e, com confiança (chegamos ao fundo), rompemos o limite da possibilidade de análise de até 20 chips na posição inicial, a um custo de tempo razoável.

Além disso, podemos nos engajar na otimização sutil do algoritmo para uma dada estrutura de dados e obter um ganho ainda maior no desempenho, mas não obteremos um crescimento tão dramático (por ordem de magnitude), o que mais uma vez indica que Wirth estava errado. Por exemplo, no programa acima, o procedimento para criar o próximo candidato para a mudança não foi deliberadamente ideal e sua correção óbvia (vamos deixar para o leitor curioso) aumentará a velocidade em 3 vezes, mas isso é um pouco, embora agradável.

Vamos prestar atenção aos resultados e ver algumas coisas não óbvias. Por exemplo, o programa afirma que uma vitória garantida em um jogo direto por 9 fichas é alcançada não em 9 jogadas, como segue o algoritmo simétrico heurístico, mas em apenas 7, e a primeira jogada coincide com a heurística (e, além disso, é a única posição vencedora ), mas o terceiro e os seguintes não devem repetir os movimentos do oponente, como segue o algoritmo ingênuo, e a chave aqui é {1,0,0,1}, que tem uma classificação de +4. Agora que fizemos uma avaliação precisa do jogo, podemos fazer perguntas interessantes sobre a presença de posições com uma avaliação estável (na qual podemos deixar o oponente ir por nós mesmos), a presença de posições-chave na árvore de enumeração, encontrar posições com o único movimento certo e assim por diante (e até obter respostas para essas perguntas e as corretas).

Aqui está a tabela de notas resumidas

Chips	Direto	Comentários	Posições / Tempo	Posições / Tempo
1	1	-1	1/0	1/0
2	-2	2	4/0	2/0
3	3	-3	17/0	7/0
4	-4	-3	82/0	20/0
5	5	4	463/0	71/0
6	5	-5	3032/0	263/0
7	7	6	22693/0	1107/0
8	-8	-7	191422/0	4945/0
9	7	-7	1798427 / 0.1	24.283 / 0
10	9	8	18634228 / 0.8	125419/0
11	11	-9	211177537 / 10.4	699165 / 0.1
12	-10	-9	*** / 127	4057686 / 0.6
13	11	10		25056975 / 3,84
14	-12	-11		160643971/28
15	13	12		1082854607/213
16	-14	-13		*** / 1698

No entanto, vemos que a estimativa do tempo de operação permaneceu fatorial, embora com uma queda significativa na taxa de crescimento. Vamos procurar outras maneiras de explorar a árvore do jogo.

Aperfeiçoamos o algoritmo de cima para baixo (bem, é claro, não o terminamos na forma feia que eu desenhei na parte de trás do envelope, você pode melhorar significativamente o desempenho reescrevendo cuidadosamente os procedimentos básicos, e isso certamente será feito, mas o problema não é fundamental decide), então vamos para o outro lado - de baixo para cima. A idéia desse método é intuitivamente simples e compreensível, mas muito difícil para o uso humano - partimos da posição final, que é estimada de acordo com as regras do jogo, e começamos a transferir a estimativa para a árvore de acordo com as mesmas regras da pesquisa de cima para baixo. É claro que, ao mesmo tempo, estamos considerando que não são possíveis movimentos para baixo da posição atual, mas estamos considerando todas as posições das quais poderíamos entrar na atual em um movimento. Transferimos a estimativa de acordo com as regras acima. Além disso, aplicamos esse procedimento iterativamente e quando ele deixa de produzir resultados, ou seja, na próxima rodada, nenhuma posição mudou a avaliação, a tarefa é concluída e a avaliação da posição inicial é correta e precisa. Essa abordagem permite reduzir bastante o tempo de pesquisa, especialmente se você fizer algumas melhorias, mas possui uma forte desvantagem (e isso é um clássico - alteramos o tempo da memória), limitando significativamente seu escopo - altos requisitos de memória, pois precisamos armazenar estimativas , ( ).No caso do jogo em questão, o método de representação de bits para a primeira estrutura de dados sugere a si próprio, existem outros métodos que podem reduzir a quantidade de memória necessária (armazenando apenas os três níveis de árvore considerados, com exceção da camada inferior), mas, é claro, degradando o desempenho, pois a pesquisa se torna muito trivial. No entanto, para H não superior a 20, o número total de posições não será superior a 2 ^ 20, e uma matriz desse tamanho na memória para elementos contendo um número de -20 a 20, ou seja, um número de 8 bits, sou capaz de imaginar e sua implementação não será difícil. Portanto, é possível escrever um programa para esse algoritmo e avaliar o desempenho resultante, mas não vamos nos apressar e fazer estimativas. Que tipo de memória teremos que alocar não é difícil de determinar, mas com parâmetros temporários é um pouco mais complicado.Suponha que criamos imediatamente todas as posições possíveis, elas serão M e, em seguida, o número médio de movimentos de uma posição pode ser estimado como não mais de 2 * N (uma estimativa muito aproximada). Então, a cada iteração, precisamos realizar não mais do que transferência M * 2 * H da estimativa e, como em cada ciclo melhoraremos a estimativa de pelo menos uma posição, o tempo total de trabalho será da ordem M * 2 * H * M.

Então, para a primeira maneira de apresentar os dados, obtemos 2 ^ H * M * 2 ^ H = 2 ^ (2 * H) * M (enfatizamos mais uma vez que esta estimativa é muito forte de cima) e, por exemplo, para H = 20, a estimativa do tempo de pesquisa de cima -down será 20! ~ 10E18, e para a pesquisa de baixo para cima, temos 2 ^ 40 * 20 = (2 ^ 10) ^ 4 * 40 = (10 ^ 3) ^ 4 * 40 ~ 10 ^ 14, ou seja, por 20 chips ganhamos no tempo pelo menos 10E6 vezes, o que é muito bom. Também contaremos para 9 fichas iniciais, obtendo 9! ~ 10E6 para a pesquisa superior e 2 ^ 9 * 2 ^ 9 * 18 ~ 10E6 para a triagem de baixo para cima, ou seja, a partir desse número, a pesquisa final ganha. A última afirmação é um tanto precipitada, uma vez que o procedimento para avaliar a próxima posição se tornou significativamente mais longo - teremos que procurá-la entre as já geradas, mas para essa representação específica na forma de uma matriz de bits, esse procedimento é realizado em O (1).

Para a segunda apresentação, é necessário avaliar o número de posições diferentes, tarefa do campo da combinatória. Como exemplo, considere um jogo com 9 fichas iniciais, para o qual o número total de posições diferentes será: 1+ (1 + 4) + (1 + 3 + 2) + (1 + 3 + 3 + 2) + (1 + 2 + 2 + 1 + 1) + (1 + 2 + 1 + 1) + (1 + 1 + 1) + (1 + 1) + 1 = 1 + 5 + 6 + 9 + 7 + 5 + 3 + 2 + 1 = 39
Então, uma estimativa pelo mesmo método levará ao valor H * M * M = 39 * 39 * 9 ~ 10E4, que é duas ordens de magnitude com melhor velocidade em comparação com a primeira representação e, à medida que H aumenta, o ganho aumentará apenas. Comparado a exagerar na segunda visualização, você também deve esperar uma melhoria significativa no desempenho, mas é mais difícil de avaliar, por isso é mais fácil tentar.

Portanto, se você fizer um programa de análise de baixo para cima, faça a segunda apresentação. Não vou dar o programa, preciso deixar algo para os leitores fazerem análises em casa. Devemos obter resultados para H significativo em um tempo bastante razoável. Outra vantagem de rebater a partir de baixo é que podemos economizar significativamente fixando a estimativa para a metade inferior das posições (que tem um número menor de fichas que N / 2), uma vez que a metade inferior estimada é transferida sem alterações para o próximo número de fichas, o que nos dará uma vitória adicional em 2 vezes.

— , , . , , ( ) .

Bem, em conclusão, a explicação necessária para aqueles que levaram meu post muito a sério e queimam com indignação (justa) - não tenho certeza absoluta de que especificar os algoritmos como o primeiro termo na fórmula de definição de programa confirme sua maior importância. Concordo plenamente que em algumas situações específicas, um algoritmo selecionado corretamente pode dar um aumento ordenado na produtividade, e eu não incriminaria Dijkstra (a quem respeito com respeito) por erros. Era tudo uma frase para atrair atenção, e o post é sobre outra coisa - que a estrutura de dados também é extremamente importante em termos de desempenho e eu queria não ser esquecido disso no processo de design.

PS.Eles me dizem aqui da platéia (oi Max) que existe outro método de pesquisar o jogo - matemático e, dada a hipótese de sobrenome duplo de que a maioria dos jogos contados se resume ao jogo de Nim, então só precisamos calculá-lo - a soma a posição inicial (na minha opinião, a afirmação é duvidosa) e você também pode converter o jogo original em jogos no gráfico (não há objeções), para os quais você pode esperar uma estimativa de 1.878 ^ N na hora do trabalho (embora o número específico tenha me intrigado). Provavelmente, essas considerações têm direito à vida, pelo menos os artigos deste conteúdo parecem convincentes, mas sou um praticante puro e deixo essas opções novamente para leitores curiosos (ars longa, vita brevis).