Troisième partie, dans laquelle Athos a précipité, et le comte de la Fer est sage avec les algorithmes.
UPD Part One est ici
UPD deuxième partie ici
AntipovSN et MihhaCF
Introduction des auteurs:
Bon après-midi Aujourd'hui, nous continuons la série d'articles consacrés à la notation et à l'utilisation de la théorie des graphes . Vous pouvez vous familiariser avec les premier et deuxième articles ici et ici, respectivement. Nous recommandons fortement, sinon, cet article peut sembler une expérience dénuée de sens avec des algorithmes.
Toutes les allégories comiques, les encarts, etc., sont conçus pour soulager légèrement le récit et ne pas le laisser tomber dans une conférence ennuyeuse. Nous nous excusons auprès de tous ceux qui ne rentrent pas dans notre humour
Le but de cet article: en moins de 30 minutes, décrivez l'algorithme de construction graphique et calculez le score de score pour NPO «One for All».
Termes et définitions:
- Algorithme de recherche en profondeur d'abord - Stratégie de recherche en profondeur d'abord - comme son nom l'indique, consiste à aller le plus profondément possible dans le graphique. L'algorithme de recherche est décrit récursivement: on trie toutes les arêtes provenant du sommet en question. Si l'arête mène à un sommet qui n'a pas été pris en compte précédemment, nous exécutons l'algorithme à partir de ce sommet non examiné, puis nous revenons et continuons de trier les arêtes. Le retour se produit s'il n'y a pas d'arêtes dans le sommet considéré qui conduisent au sommet non examiné. Si, après la fin de l'algorithme, tous les sommets n'ont pas été pris en compte, il est nécessaire d'exécuter l'algorithme à partir de l'un des sommets non examinés
- Récursion - appeler une fonction (procédure) depuis elle-même, directement (récursivité simple) ou via d'autres fonctions (récursion complexe ou indirecte)
Dans notre premier article ( ici ), nous avons déterminé le modèle graphique avec lequel nous allons expérimenter et lui avons donné une brève description.
Dans notre deuxième article ( ici ), nous avons décrit les structures de données de base qui peuvent être utilisées pour stocker un graphe et décrit plus en détail le modèle de graphe et comment travailler avec.
Il est temps de sortir l'épée de son fourreau et de commencer à poignarder tout le monde, ou plutôt, de créer un algorithme pour calculer le score de score pour NPO One for All.
C'est parti!
L'algorithme sera exécuté en Python . Comme on dit, tirez le serpent sur l'épée!
Le graphique sera stocké dans le dictionnaire, comme suit:
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» - évaluation du nœud - bonne ou mauvaise et le degré de «priorité» du nœud. Par exemple, le Cardinal est un héros négatif du film, donc sa note est négative. Le Cardinal est l'un des principaux ennemis de nos héros, mais pas le plus important (nous l'avons décidé)
'rang' - score du nœud dans le tableau de classement
«fonds» - viabilité du nœud
«relations» - avec qui est connecté et dans quelle mesure peut-il influencer le nœud qui lui est connecté
Jusqu'à présent, tout est simple, mais un lecteur attentif pourrait déjà remarquer certaines des fonctionnalités, oui, des questions de contenu se posent déjà. Essayons de les prédire et d'y répondre. Le droit de la première injection est à nous!
Je pense que cela ne vaut pas la peine d'expliquer ce que nous avons utilisé pour le nom de la clé du dictionnaire de premier niveau. Vous l'avez déjà parfaitement deviné, cependant, certains noms ont subi des changements en raison de notre perception de l'œuvre.
D'où viennent ces paramètres («goody», «rank», etc.), pourquoi sont-ils et d'où vient leur notation?
Pour:
- Dans la vraie vie, ces paramètres caractériseront une entreprise de nœuds particulière. Pour tous ceux qui réaliseront l'évaluation et selon le type de cette évaluation, ces paramètres seront différents. Par exemple, ces paramètres pour évaluer le score d'un emprunteur peuvent être - le chiffre d'affaires, le montant des dettes / créances, le bref d'exécution, etc.
- Pourquoi exactement ils - l'auteur le voit ainsi))) ces paramètres reflètent l'essence de ce que le comte décrit, à notre avis
- L'évaluation est, comme on dit maintenant, experte. Dans la vraie vie, cette estimation sera obtenue par l'exploitation minière. Nous écrirons plus à ce sujet dans le prochain article.
Pourquoi certains nœuds ont-ils des liens réciproques différents (par exemple, Odin_za_vseh - Bonasye = 3 et Bonasye - Odin_za_vseh = 1)? En effet, Odin_za_vseh a un effet beaucoup plus important sur Bonasye que vice versa. Et c'est important à comprendre. Lors de la notation d'Odin_za_vseh, nous devrons tenir compte de l'effet de Bonasye sur Odin_za_vseh.
Qu'est-ce qu'un score obligataire et comment est-il calculé?
- L'évaluation de la communication est une mesure de l'influence d'un nœud sur un autre
- Chaque connexion dans notre graphique est bidirectionnelle, mais en même temps, l'évaluation de la communication dans différentes directions peut varier
- Le score de communication est une valeur de 1 à 5 (de 1 à 5 juste par exemple). Il ne peut y avoir de connexion négative, car le nœud est soit connecté à un autre, et nous évaluons dans quelle mesure il affecte ce nœud, ou n'est pas connecté. Dans ce cas, bien sûr, la connexion avec un nœud non fiable sera finalement négative pour le nœud que nous évaluons, car ce nœud non fiable aura une note interne négative.
- Une évaluation interne d'un nœud est une valeur agrégée constituée des paramètres internes d'un nœud. Dans notre exemple, il s'agit de «goody», «rank», «fund». La note interne peut être négative.
Comment un ballon marquant sera-t-il considéré?
- Chaque entreprise qui utilisera cette approche peut établir son calcul de score en fonction de ses besoins et de son expérience commerciale.
- Dans notre cas, nous avons choisi une manière simple et complexe:
- Score de score = score interne du nœud que nous évaluons + Sum (évaluation interne d'un nœud enfant de niveau 1 évaluant l'impact de ce nœud sur le nœud en cours d'évaluation) + (Sum (évaluation interne d'un nœud enfant de niveau 2 évaluant l'effet de ce nœud sur un nœud parent de niveau 1) / 2)
- Si vous obtenez un score négatif, nous n'accordons pas de prêt
- L'algorithme présenté ci-dessous est basique et peut être facilement modifié pour s'adapter à toute technique de calcul de score de notation.
- Toute la difficulté sera dans la «bonne» exploitation, mais elle sera décrite dans le prochain article
Et voici l'algorithme lui-même:
searched=[]
Pour résumer:
- Je suis sûr que la lecture de l'article n'a pas pris plus de 30 minutes
- Nous avons calculé le score pour NPO One for All. Nous ne donnons pas de crédit, NPO "One for All" s'est avéré être ces aventuriers avec un tas d'ennemis. Nous pouvons donner du crédit aux employés de l'État, par exemple, «Mushketery»
- L'algorithme s'est avéré simple et assez efficace.
- La complexité de calcul est O (N ** d + 1), où d est le nombre de niveaux. Visuellement, l'algorithme est illustré dans la figure ci-dessous.
Merci à sobolevn et à son article
Vous pouvez passer à l'extraction de données la plus intéressante et la plus difficile!
PS Concernant les liens vers d'autres articles avec la théorie (dans un article précédent, nous avons fait une remarque):