Parte três, na qual Athos precipitou, e o Conde de la Fer é sábio em algoritmos.
UPD Part One está aqui
UPD parte dois aqui
AntipovSN e MihhaCF
Introdução dos autores:
Boa tarde Hoje continuamos a série de artigos dedicados à pontuação e ao uso da teoria dos grafos . Você pode se familiarizar com o primeiro e o segundo artigos aqui e aqui, respectivamente. É altamente recomendável, caso contrário, este artigo pode parecer um experimento sem sentido com algoritmos.
Todas as alegorias, inserções etc. de quadrinhos são projetadas para aliviar um pouco a narrativa e não permitir que ela caia em uma palestra chata. Pedimos desculpas a todos que não entendem nosso humor
O objetivo deste artigo: em não mais de 30 minutos, para descrever o algoritmo de construção de gráfico e calcular a pontuação da NPO "One for All".
Termos e definições:
- Algoritmo de busca em profundidade - a estratégia de busca em profundidade , como o nome indica, é “aprofundar” o gráfico o máximo possível. O algoritmo de busca é descrito recursivamente: classificamos todas as arestas provenientes do vértice em questão. Se a aresta leva a um vértice que não foi considerado anteriormente, executamos o algoritmo a partir desse vértice não examinado e, depois disso, retornamos e continuamos a classificar as arestas. O retorno ocorre se não houver arestas no vértice em consideração que levam ao vértice não examinado. Se após a conclusão do algoritmo nem todos os vértices foram considerados, é necessário executar o algoritmo a partir de um dos vértices não examinados
- Recursão - chamando uma função (procedimento) dela, diretamente (recursão simples) ou através de outras funções (recursão complexa ou indireta)
Em nosso primeiro artigo ( aqui ), determinamos o modelo gráfico com o qual experimentaremos e fizemos uma breve descrição.
Em nosso segundo artigo ( aqui ), descrevemos as estruturas básicas de dados que podem ser usadas para armazenar um gráfico e descrevemos com mais detalhes o modelo de gráfico e como trabalhar com ele.
É hora de tirar a espada da bainha e começar a esfaquear todo mundo, ou melhor, criar um algoritmo para calcular a pontuação da NPO "One for All".
Vamos lá!
O algoritmo será executado em Python . Como se costuma dizer, puxe a cobra pela espada!
O gráfico será armazenado no dicionário, da seguinte maneira:
graph = { 'Odin_za_vseh' : {'goody': 10, 'rank': 4, 'fund':4, 'relations':{'Bonasye':3, 'Trevi': 1, 'Gusak':2,'Suchka':5, 'Roshfor':1, 'Cardi':1}}, 'Cardi' : {'goody': -8, 'rank': 9, 'fund':8, 'relations':{'Korol':2,'Odin_za_vseh':3,'Gvardia':5, 'Roshfor':5 }}, 'Roshfor' : {'goody': -7, 'rank': 7, 'fund':5,'relations':{'Cardi':1, 'Suchka': 3,'Odin_za_vseh':2, 'Bonasye':5 }}, 'Suchka' : {'goody': -10, 'rank': 4, 'fund':4, 'relations':{'Odin_za_vseh':5,'Roshfor':3 }}, 'Gvardia' : {'goody': -5, 'rank': 3, 'fund':4, 'relations':{'Cardi':1,'Gusak':1 }}, 'Gusak' : {'goody': -7, 'rank': 4, 'fund':4, 'relations':{'Gvardia':5,'Odin_za_vseh':2 }}, 'Trevi' : {'goody': 7, 'rank': 5, 'fund':5, 'relations':{'Odin_za_vseh':4,'Mushketery':5 }}, 'Bonasye': {'goody': -2, 'rank': 2, 'fund':3, 'relations':{'Odin_za_vseh':1,'Roshfor':1,'Konsta':2 }}, 'Konsta' : {'goody': 10, 'rank': 5, 'fund':3, 'relations':{'Koroleva':2,'Bonasye':1 }}, 'Mushketery' : {'goody': 7, 'rank': 5, 'fund':4, 'relations':{'Korol':1, 'Trevi':1}}, 'Koroleva' : {'goody': 6, 'rank': 8, 'fund':7, 'relations':{'Korol':2,'Konsta':5, 'EnglishMan':3 }}, 'Korol' : {'goody': 5, 'rank': 10, 'fund':10, 'relations':{'Cardi':3, 'Koroleva':5,'Mushketery':5 }}, 'EnglishMan' : {'goody': 5, 'rank': 8, 'fund':10, 'relations':{'Koroleva':2}} }
'goody' - classificação do nó - bom ou ruim e o grau de "prioridade" do nó. Por exemplo, o Cardeal é um herói negativo do filme, então sua classificação é negativa. O cardeal é um dos principais inimigos de nossos heróis, mas não o mais importante (decidimos isso)
'rank' - pontuação do nó na tabela de classificação
'fundo' - viabilidade do nó
'relações' - com quem está conectado e quanto pode influenciar o nó conectado a ele
Até agora, tudo é simples, mas um leitor atento já pode perceber alguns dos recursos, sim, questões de conteúdo já surgem. Vamos tentar prever e responder a eles. O direito da primeira injeção é nosso!
Acho que não vale a pena explicar o que usamos para o nome da chave do dicionário de primeiro nível. Você já adivinhou perfeitamente, porém, alguns nomes sofreram alterações devido à nossa percepção do trabalho.
De onde vieram esses parâmetros ('goody', 'rank' etc.), por que eles são e de onde vêm suas classificações?
Em ordem:
- Na vida real, esses parâmetros caracterizarão uma empresa-nó específica. Para todos que conduzirão a avaliação e, dependendo do tipo dessa avaliação, esses parâmetros serão diferentes. Por exemplo, esses parâmetros para avaliar a pontuação de um mutuário podem ser - rotatividade, quantidade de contas a pagar / receber, mandado de execução etc.
- Por que exatamente eles - o autor vê desta maneira))) esses parâmetros refletem a essência do que o Conde descreve, em nossa opinião
- A avaliação é, como dizem agora, especialista. Na vida real, essa estimativa será obtida através da mineração. Escreveremos mais sobre isso no próximo artigo.
Por que alguns nós têm links recíprocos diferentes (por exemplo, Odin_za_vseh - Bonasye = 3 e Bonasye - Odin_za_vseh = 1)? Isso ocorre porque Odin_za_vseh tem um efeito muito maior sobre Bonasye do que vice-versa. E isso é importante para entender. Ao pontuar Odin_za_vseh, precisaremos considerar o efeito de Bonasye em Odin_za_vseh.
O que é uma pontuação de títulos e como é calculada?
- A avaliação da comunicação é uma medida da influência de um nó em outro
- Cada conexão em nosso gráfico é bidirecional, mas, ao mesmo tempo, a avaliação da comunicação em diferentes direções pode variar
- A pontuação da comunicação é um valor de 1 a 5 (de 1 a 5 apenas por exemplo). Não pode haver conexão negativa, porque o nó está conectado a outro e avaliamos o quanto ele afeta esse nó ou não está conectado. Nesse caso, é claro, a conexão com um nó não confiável acabará sendo negativa para o nó que estamos avaliando, porque esse nó não confiável terá uma classificação interna negativa.
- Uma avaliação interna de um nó é um valor agregado que consiste nos parâmetros internos de um nó. No nosso exemplo, isso é 'goody', 'rank', 'fund'. A classificação interna pode ser negativa.
Como uma bola de pontuação será considerada?
- Cada empresa que usar essa abordagem pode estabelecer seu cálculo de pontuação com base em seus requisitos e experiência de negócios.
- No nosso caso, escolhemos uma maneira simples e intrincada:
- Pontuação de pontuação = pontuação interna do nó que estamos avaliando + Soma (avaliação interna de um nó filho de nível 1 que avalia o impacto desse nó no nó que está sendo avaliado) + (Soma (classificação interna de um nó filho de nível 2 que avalia o efeito desse nó em um nó pai de nível 1) / 2)
- Se você obtiver uma pontuação negativa, não concedemos um empréstimo
- O algoritmo apresentado abaixo é básico e pode ser facilmente modificado para se ajustar a qualquer técnica de cálculo de pontuação.
- Toda a dificuldade estará na mineração "certa", mas será descrita no próximo artigo
E aqui está o próprio algoritmo:
searched=[]
Para resumir:
- Estou certo de que a leitura do artigo não levou mais de 30 minutos
- Calculamos a pontuação do NPO One for All. Nós não damos crédito, o NPO "One for All" acabou sendo aqueles aventureiros com um monte de inimigos. Podemos dar crédito a funcionários do estado, por exemplo, 'Cogumelos'
- O algoritmo acabou sendo simples e bastante eficaz.
- A complexidade computacional é O (N ** d + 1), onde d é o número de níveis. Visualmente, o algoritmo é mostrado na figura abaixo.
Graças a sobolevn e seu artigo
Você pode passar para o mais interessante e difícil - mineração de dados!
PS Com relação aos links para outros artigos com teoria (em um artigo anterior, fizemos uma observação):