Count Scoring de la Fer أو دراسة حول تسجيل الائتمان كجزء من توسيع آفاق الفرد. الجزء 3

الجزء الثالث ، الذي عجلت فيه آثوس ، والكونت دي لا فير من الحكمة مع الخوارزميات.

UPD الجزء الأول هنا
تحديث الجزء الثاني هنا

AntipovSN و MihhaCF

مقدمة من المؤلفين:

مساء الخير نواصل اليوم سلسلة المقالات المكرّسة لتسجيل النقاط واستخدام نظرية الرسم البياني فيها. يمكنك التعرف على المقالات الأولى والثانية هنا وهنا ، على التوالي. نوصي بشدة ، وإلا ، قد تبدو هذه المقالة بمثابة تجربة لا معنى لها مع الخوارزميات.

تم تصميم كل الرموز الهزلية ، والمدخلات ، وما إلى ذلك ، لتخفيف السرد قليلاً وعدم السماح له بالسقوط في محاضرة مملة. نعتذر لكل من لا يشارك في روح الدعابة لدينا

الغرض من هذه المقالة: في مدة لا تزيد عن 30 دقيقة ، قم بوصف خوارزمية إنشاء الرسم البياني وحساب درجة التسجيل لـ NPO "One for All".

المصطلحات والتعاريف:

• خوارزمية البحث في العمق الأول - استراتيجية البحث في العمق الأول ، كما يوحي الاسم ، هي الانتقال "أعمق" في الرسم البياني إلى أقصى حد ممكن. يتم وصف خوارزمية البحث بشكل متكرر: نقوم بالفرز بين جميع الحواف القادمة من قمة الرأس المعنية. إذا كانت الحافة تؤدي إلى قمة غير مذكورة سابقًا ، فسنقوم بتشغيل الخوارزمية من هذه القمة غير المربحة ، وبعد ذلك نعود ونواصل الفرز بين الحواف. يحدث العائد في حالة عدم وجود حواف في الرأس قيد النظر تؤدي إلى قمة الرأس غير المربحة. إذا ، بعد الانتهاء من الخوارزمية ، لم يتم النظر في جميع القمم ، فمن الضروري تشغيل الخوارزمية من أحد القمم غير المربحة
• الإعادة - استدعاء دالة (إجراء) منه ، مباشرة (الإعادة البسيطة) أو من خلال وظائف أخرى (الإعادة المعقدة أو غير المباشرة)

في مقالتنا الأولى ( هنا ) ، حددنا نموذج الرسم البياني الذي سنختبره ، وقدمناه وصفًا موجزًا.

في مقالتنا الثانية ( هنا ) ، وصفنا هياكل البيانات الأساسية التي يمكن استخدامها لتخزين رسم بياني ووصفنا بمزيد من التفصيل نموذج الرسم البياني وكيفية التعامل معه.

لقد حان الوقت لسحب السيف من غمده والبدء في طعن الجميع ، وبشكل أكثر دقة ، إنشاء خوارزمية لحساب نقاط التسجيل في NPO "One for All".

دعنا نذهب!

سيتم تنفيذ الخوارزمية في بايثون . كما يقولون ، اسحب الأفعى على السيف!

سيتم تخزين الرسم البياني في القاموس ، على النحو التالي:

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" - تصنيف العقدة - جيد أو سيئ ودرجة "أولوية" العقدة. على سبيل المثال ، الكاردينال هو بطل سلبي للفيلم ، لذلك تصنيفه سلبي. الكاردينال هو أحد الأعداء الرئيسيين لأبطالنا ، ولكن ليس الأهم (قررنا ذلك)
"رتبة" - درجة العقدة في جدول الترتيب
"الصندوق" - صلاحية العقدة
"العلاقات" - مع من هو المتصل ومقدار التأثير على العقدة المرتبطة به

حتى الآن ، كل شيء بسيط ، ولكن يمكن للقارئ اليقظ أن يلاحظ بالفعل بعض الميزات ، نعم ، لقد نشأت بالفعل أسئلة عن المحتوى. دعونا نحاول التنبؤ والإجابة عليها. الحق في الحقن الأول هو لنا!

1. أعتقد أنه لا يستحق شرح ما استخدمناه لاسم مفتاح قاموس المستوى الأول. أنت بالفعل خمنت تمامًا ، على الرغم من أن بعض الأسماء قد خضعت لتغييرات نظرًا لتصورنا للعمل.

   
   

2. من أين أتت هذه المعلمات ("goody" ، "رتبة" ، وما إلى ذلك) ، لماذا هي ومن أين جاء تصنيفهم؟
   بالترتيب:

   
   
   • في الحياة الحقيقية ، سوف تميز هذه المعلمات شركة عقدة معينة. لكل من سيجري التقييم واعتمادًا على نوع هذا التقييم ، ستكون هذه المعلمات مختلفة. على سبيل المثال ، قد تكون هذه المعلمات لتقييم تسجيل المقترض هي - حجم الأعمال ، ومبلغ الذمم الدائنة / المستحقة القبض ، ومذكرة التنفيذ ، إلخ.
   • لماذا بالضبط - يرى المؤلف ذلك بهذه الطريقة))) تعكس هذه المعلمات جوهر ما يصفه الكونت ، في رأينا
   • التقييم ، كما يقولون الآن ، خبير. في الحياة الحقيقية ، سيتم الحصول على هذا التقدير من خلال التعدين. سنكتب المزيد حول هذا الموضوع في المقالة التالية.
   
   

3. لماذا يكون لبعض العقد روابط متبادلة مختلفة (على سبيل المثال ، Odin_za_vseh - Bonasye = 3 و Bonasye - Odin_za_vseh = 1)؟ هذا لأن Odin_za_vseh له تأثير أكبر بكثير على Bonasye من العكس. وهذا هو المهم أن نفهم. عند تسجيل Odin_za_vseh ، سنحتاج إلى النظر في تأثير Bonasye على Odin_za_vseh.

   
   

4. ما هي درجة السندات وكيف يتم حسابها؟

   
   
   • تقييم الاتصالات هو مقياس لتأثير عقدة على أخرى
   • كل اتصال في الرسم البياني الخاص بنا ذو اتجاهين ، ولكن في الوقت نفسه ، قد يختلف تقييم الاتصال في اتجاهات مختلفة
   • درجة التواصل هي قيمة من 1 إلى 5 (من 1 إلى 5 على سبيل المثال فقط). لا يمكن أن يكون هناك اتصال سلبي ، لأنه العقدة إما متصلة بأخرى ، ونقيم مدى تأثيرها على هذه العقدة ، أو غير متصل. في هذه الحالة ، بطبيعة الحال ، فإن الاتصال مع عقدة غير موثوق بها سيكون في نهاية المطاف سلبيًا للعقدة التي نقوم بتقييمها ، لأن سيكون لهذه العقدة غير الموثوق بها تصنيف داخلي سلبي.
   • التقييم الداخلي للعقدة هو قيمة مجمعة تتكون من المعلمات الداخلية للعقدة. في مثالنا ، هذا هو "goody" و "Rank" و "fund". التصنيف الداخلي قد يكون سلبيا.
   
   

5. كيف سيتم النظر في كرة التهديف؟

   
   
   • يمكن لكل شركة ستستخدم هذا النهج أن تضع حسابها الخاص بنتيجة التسجيل بناءً على متطلباتها وخبرتها التجارية.
   • في حالتنا ، اخترنا طريقة بسيطة ومعقدة:
     
     • درجة التقييم = النتيجة الداخلية للعقدة التي نقوم بتقييمها + مجموع (التقييم الداخلي لعقدة فرعية من المستوى 1 لتقييم تأثير هذه العقدة على العقدة التي يجري تقييمها) + (مجموع (التصنيف الداخلي للعقدة الفرعية من المستوى 2 لتقييم تأثير هذه العقدة على عقدة الوالدين من المستوى 1) / 2)
     • إذا حصلت على درجة تسجيل سلبية ، فإننا لا نقدم قرضًا
   • تعتبر الخوارزمية الموضحة أدناه أساسية ويمكن تعديلها بسهولة لتناسب أي طريقة لحساب نقاط التسجيل.
   • ستكون كل الصعوبة في التعدين "الصحيح" ، لكن سيتم وصفه في المقال التالي
   
   

وهنا الخوارزمية نفسها:

 searched=[] #   def search_outer(name,n): return graph[name]['goody']*graph[name]['rank']*graph[name]['fund']+search(name,n) # search_outer()    ,       #,       search() #name –   ,     #n –   –       def search(name, n, z=1): ball=0 #,      global searched #    if z <= n and name not in searched: #        searched.append(name) for x in graph[name]['relations']: #   ball += graph[x]['goody'] * graph[x]['rank'] * graph[x]['fund'] * graph[x]['relations'][name] / z + search(x,n,z+1) #      #   ,     return ball #, ,     def main(): ball = search_outer ('Odin_za_vseh', 2) print(ball) if __name__ == '__main__': main() 

لتلخيص:

• أنا متأكد من أن قراءة المقال لم تستغرق أكثر من 30 دقيقة
• حسبنا النتيجة التهديف ل NPO واحد للجميع. لم نمنح الفضل في ذلك ، فقد تبين أن "NPO for One" من قبل NPO هم أولئك المغامرين مع مجموعة من الأعداء. يمكننا تقديم ائتمان لموظفي الدولة ، على سبيل المثال ، "Mushketery"
• تحولت الخوارزمية إلى أن تكون بسيطة وفعالة للغاية.
• التعقيد الحسابي هو O (N ** d + 1) ، حيث d هو عدد المستويات. بصريا ، يتم عرض الخوارزمية في الشكل أدناه.

بفضل sobolevn ومقاله

يمكنك الانتقال إلى التنقيب عن البيانات الأكثر إثارة وصعوبة!

ملاحظة: فيما يتعلق بروابط لمقالات أخرى مع النظرية (في مقال سابق ، قدمنا ​​ملاحظة):

• خوارزمية تقدير
• تقدير آخر لتعقيد الخوارزمية
• نظرية الرسم البياني