第三部分，Athos诞生了，Count de la Fer的算法是明智的。
UPD第一部分在这里
UPD第二部分
AntipovSN和MihhaCF
作者简介：
下午好 今天，我们继续讨论有关评分和在其中使用图论的系列文章。 您可以分别在这里和这里熟悉第一篇和第二篇文章。 我们强烈建议您这样做，否则，本文可能看起来像是对算法的毫无意义的实验。
所有漫画寓言，插入内容等都旨在略微减轻叙事的影响，并且不允许其陷入无聊的演讲中。 我们向所有不喜欢我们幽默的人致歉
本文的目的：在不超过30分钟的时间内，描述图构建算法并计算NPO“一个为所有人”的得分。
术语和定义：
- 顾名思义， 深度优先搜索算法-深度优先搜索策略是尽可能深入图。 递归地描述搜索算法：我们对来自所讨论顶点的所有边进行排序。 如果边缘导致未曾考虑过的顶点，则我们从该未经检查的顶点运行算法，然后返回并继续对边缘进行排序。 如果考虑的顶点中没有导致未检查顶点的边，则会发生返回。 如果在算法完成后未考虑所有顶点，则有必要从未检查的顶点之一运行算法
- 递归 -直接（简单递归）或通过其他函数（复杂或间接递归）从函数本身调用函数（过程）
在我们的第一篇文章（ 此处 ）中，我们确定了将要进行实验的图形模型，并对其进行了简要描述。
在我们的第二篇文章（ 此处 ）中，我们描述了可用于存储图形的基本数据结构 ，并更详细地描述了图形模型以及如何使用它。
现在是时候将剑拔出刀鞘，开始刺伤所有人，或者是创建一种算法来计算NPO“所有人”的得分。
走吧
该算法将在Python中执行。 正如他们所说，将蛇拉在剑上！
该图将存储在字典中，如下所示：
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” -节点评级-优劣以及节点的“优先级”程度。 例如，红衣主教是电影的负面英雄，因此他的评分是负面。 红衣主教是我们英雄的主要敌人之一，但不是最重要的（我们决定如此）
'排名' -节点在排名表中的得分
'资金' -节点生存能力
“关系” -与谁连接以及多少会影响与其连接的节点
到目前为止，一切都很简单，但是细心的读者可能已经注意到了其中的一些功能，是的，内容问题已经出现。 让我们尝试预测并回答它们。 第一次注射的权利是我们的！
我认为没有必要解释一下我们用于第一级字典键名的内容。 您已经完全猜到了，但是由于我们对作品的理解，有些名称已经发生了变化。
这些参数从何而来（“好”，“等级”等），为什么从何而来？它们的评级从何而来？
为了：
- 在现实生活中，这些参数将表征特定的节点公司。 对于将进行评估的每个人，并且根据评估的类型，这些参数将有所不同。 例如，用于评估借款人评分的此类参数可以是-营业额，应付账款/应收款额，执行令状等。
- 为什么要准确说明它们-作者这样看）））我们认为这些参数反映了Count描述的实质
- 正如他们现在所说，评估是专家。 在现实生活中，此估计将通过采矿获得。 我们将在下一篇文章中写更多有关此的内容。
为什么某些节点具有不同的互惠链接（例如，Odin_za_vseh-Bonasye = 3，而Bonasye-Odin_za_vseh = 1）？ 这是因为Odin_za_vseh对Bonasye的影响要大得多，反之亦然。 这一点很重要。 在为Odin_za_vseh评分时，我们需要考虑Bonasye对Odin_za_vseh的影响。
什么是债券分数，如何计算？
- 通信评估是一个节点对另一节点的影响的度量
- 我们图表中的每个连接都是双向的，但同时，不同方向上的交流评估可能会有所不同
- 沟通得分是1到5（例如，从1到5）的值。 不可能有负面联系，因为 该节点已连接到另一个节点，我们评估它对该节点有多大影响或未连接。 当然，在这种情况下，与不可靠节点的连接最终将对我们正在评估的节点为负，因为 该不可靠节点的内部评级为负。
- 节点的内部评估是由节点的内部参数组成的聚合值。 在我们的示例中，这是“好”，“排名”，“资金”。 内部评级可能为负。
如何计分球？
- 每个将使用这种方法的公司都可以根据其要求和业务经验来确定其得分分数。
- 在我们的案例中，我们选择了一种简单而复杂的方式：
- 评分分数=我们正在评估的节点的内部分数+总和（1级子节点的内部评估， 评估该节点对被评估节点的影响）+（总和（2级子节点的内部评估，评估该节点对1级父节点的影响）/ 2）
- 如果您的得分得分为负，那么我们就不给您贷款
- 下面介绍的算法是基本算法，可以轻松修改以适合任何得分分数计算技术。
- 所有的困难都将在“正确的”挖掘中进行，但将在下一篇文章中进行描述。
这是算法本身：
searched=[]
总结一下：
- 我相信阅读本文的时间不会超过30分钟
- 我们计算了NPO One for All的得分。 我们不值得称赞，NPO“所有人”是那些有很多敌人的冒险家。 我们可以归功于国家雇员，例如“ Mushketery”
- 事实证明该算法很简单并且非常有效。
- 计算复杂度为O（N ** d +1），其中d是级别数。 在视觉上，该算法如下图所示。
感谢sobolevn和他的文章
您可以继续进行最有趣和最困难的工作-数据挖掘！
PS关于与理论上其他文章的链接（在上一篇文章中，我们做了评论）：