خوارزمية التحقق للأفعال تعدى من علاقة ؟

Question

أنا بحاجة للتحقق مما إذا كانت العلاقة متعدية أو لا ؟

هلا تشير بعض خوارزمية التحقق من للأفعال تعدى من العلاقات ؟

انا تخزين العلاقة منطقية مصفوفة هناك 1 إذا العناصر ذات الصلة وغيرها من الحكمة 0 مثل الرسوم البيانية.

شكرا

Answer 1

أبسط من ذلك بكثير خوارزمية بلدي خريطة/تعيين الإصدار (حذف), الآن مع منطقية مصفوفة.وربما هذا هو أسهل للفهم ، حتى إذا كنت لا تعرف جافا ؟

public class Trans
{

  final static int SIZE = 4;

  static boolean isTransitive(boolean[][] function)
  {
    for (int i = 0; i < SIZE; i++)
    {
      for (int j = 0; j < SIZE; j++)
      {
        if (function[i][j])
        {
          for (int k = 0; k < SIZE; k++)
          {
            if (function[j][k] && !function[i][k])
            {
              return false;
            }
          }
        }
      }
    }
    return true;
  }

  public static void main(String[] args)
  {
    boolean[][] function = new boolean[SIZE][SIZE];
    for (int i = 0; i < SIZE; i++)
    {
      function[i] = new boolean[SIZE];
    }
    function[0][1] = true;
    function[1][2] = true;
    function[0][2] = true;
    function[0][3] = true;
    function[1][3] = true;   
    System.out.println(isTransitive(function));
  }
}

Answer 2

على الرغم من هذا يبدو تماما مثل الواجبات المنزلية...

كنت بحاجة لتخزين العلاقات الخاصة بك بحيث يمكنك البحث عنها عن طريق السالفة بسرعة جدا.ثم يمكنك اكتشاف متعدية علاقات من نوع A->B>C, وإضافتها إلى نفسه تخزين والحفاظ على الذهاب للبحث A->B>C>D, الخ الخ...

Answer 3

الطوبوغرافية الفرز قد يكون الاتجاه الصحيح.العلاقة متعدية إذا لم تكن هناك حلقات في توجيه الرسم البياني التمثيل.إذا كنت الرعاية حول سرعة الرسم البياني الخوارزميات ربما هي وسيلة للذهاب.