تخيل رحلة جماعية مع 10 أصدقاء. خلال أسبوع، تظهر 50 مصروفًا مشتركًا: Alice دفعت العشاء، Bob دفع Uber، Charlie دفع المشروبات. في النهاية، إذا سدد الجميع كل معاملة بدقة، ستحتاجون إلى عشرات التحويلات.
هذا غير فعال ومربك ويخلق رسومًا غير ضرورية. في Finovoo هدفنا تقليل هذا الفوضى إلى الحد الأدنى من التحويلات باستخدام نظرية الرسوم البيانية.
مشكلة N²
في طريقة تسوية بسيطة، ينمو عدد المعاملات المحتملة تربيعيًا مع عدد المشاركين. إذا كان كل شخص مدينًا لكل شخص، فقد تحتاج مجموعة من 10 أشخاص نظريًا إلى 90 معاملة.
تصور الدين كرسم بياني
نمثل مالية المجموعة كرسم بياني موجه، حيث المشاركون عقد والديون حواف موجهة. حافة من A إلى B بوزن 20 دولارًا تعني أن A مدين لـ B بـ 20 دولارًا.
الخطوة 1: حساب الأرصدة الصافية
الخطوة الأولى هي تجاهل المعاملات الفردية وحساب الرصيد الصافي لكل شخص. لا يهم أن Alice مدينة لـ Bob بـ 10 دولارات وأن Bob مدين لها بـ 5؛ المهم أن Alice مدينة صافيًا بـ 5 دولارات.
مثال: Alice (+50)، Bob (-20)، Charlie (-30). Alice يجب أن تحصل على 50 دولارًا، بينما Bob وCharlie مدينان. تاريخ من دفع ماذا لم يعد مهمًا؛ المهم تصفية الأرصدة.
الخطوة 2: خوارزمية المطابقة الجشعة
بعد معرفة الأرصدة الصافية، نعيد بناء رسم جديد بأقل عدد ممكن من الحواف. نستخدم خوارزمية جشعة لمطابقة المدينين والدائنين.
- رتب المشاركين في قائمتين: مدينون برصيد سلبي ودائنون برصيد إيجابي.
- خذ أكبر مدين وأكبر دائن.
- طابقهما. إذا كان المدين يدين بـ 100 دولار والدائن يستحق 80 دولارًا، يدفع المدين 80. يصبح الدائن مسوى، ويبقى المدين عند -20.
- كرر العملية مع الأرصدة المتبقية حتى يصبح الجميع عند صفر.
التعامل مع الدورات
من أجمل أجزاء تبسيط الرسم إزالة الدورات. تحدث الدورة عندما يكون A مدينًا لـ B وB لـ C وC لـ A.
إذا كان التدفق متساويًا، مثل 10 دولارات في دائرة، فالأثر الصافي صفر. حساب الرصيد الصافي يزيل هذه الدورات تلقائيًا قبل بدء التسوية.
قيود الواقع
الرياضيات أنيقة، لكن الواقع معقد. أحيانًا يطلب المستخدمون عدم تبسيط الديون بين أشخاص معينين. عندها نقسم الرسم إلى رسوم فرعية ونحسن محليًا ضمن القيود.
بتقليل عدد الحواف، نوفر للمستخدمين الوقت ورسوم التحويل وعناء متابعة عشرات الدفعات الصغيرة.