تحسين فلويد وارشال لمصفوفة متماغية متماثل

Question

هل هناك تحسين يؤدي إلى خفض العامل المستمر لوقت وقت تشغيل Floyd-Warshall، إذا مضمون أن يكون لديك مصفوفة مجاورة متماثلة؟

Answer 1

بعد بعض التفكير في أنني توصلت إلى:

for (int k = 0; k < N; ++k)
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

الآن بالطبع نحتاج كلاهما لإظهار أنها صحيحة وأسرع.

صحيحة يصعب إثباتها، لأنه يعتمد على إثبات فلويد وارشال وهو غير تافه. يتم إعطاء دليل جيد جدا هنا: برهان فلويد وارشال

مصفوفة الإدخال هو متماثل. وبعد الآن يستخدم بقية الإثبات دليلا عددا من Floyd-Warshall المعدل لإظهار أن ترتيب الحسابات في الحلقات الداخلية الثانية لا يهم وأن الرسم البياني يبقى متماثل بعد كل خطوة. إذا اعرضنا كل من هذه الشروط صحيحة، فإن كلا الخوارزميات تفعل الشيء نفسه.

دعنا نحدد dist[i][j][k] كما المسافة من i ل j باستخدام استخدام القمم فقط من المجموعة {0, ..., k} كما القمم الوسيطة على الطريق من i ل j.

dist[i][j][k-1] يتم تعريفه على أنه وزن الحافة من i ل j. وبعد إذا لم تكن هناك حافة بين هذا الوزن تؤخذ إلى أن تكون ما لا نهاية.

الآن باستخدام نفس المنطق كما هو مستخدم في الدليل المرتبط أعلاه:

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

الآن في حساب dist[i][k][k] (وبالمثل ل dist[k][i][k]):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1])

الآن منذ ذلك الحين dist[k][k][k-1] لا يمكن أن تكون سلبية (أو لدينا حلقة سلبية في الرسم البياني)، وهذا يعني ذلك dist[i][k][k] = dist[i][k][k-1]. وبعد منذ إذا dist[k][k][k-1] = 0 ثم كلا المعلمين هي نفسها، وإلا فإن المعلمة الأولى لل min() مختار.

حتى الآن، ل dist[i][k][k] = dist[i][k][k-1], ، عند حساب dist[i][j][k] لا يهم إذا dist[i][k] أو dist[k][j] السماح بالفعل k في مساراتهم. حيث dist[i][j][k-1] يستخدم فقط لحساب dist[i][j][k], dist[i][j] سيبقى dist[i][j][k-1] في المصفوفة حتى dist[i][j][k] تم حسابه. إذا i أو j تساوي k ثم تنطبق الحالة أعلاه.

لذلك، لا يهم ترتيب الحسابات.

الآن نحن بحاجة إلى إظهار ذلك dist[i][j] = dist[j][i] بعد كل خطوات الخوارزمية.

نبدأ مع شبكة متماثلة وهكذا dist[a][b] = dist[b][a], للجميع a و b.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
           = min(dist[j][i], dist[k][i] + dist[j][k])
           = min(dist[j][i], dist[j][k] + dist[k][i])
           = dist[j][i]

لذلك مهمتنا هي صحيحة وسوف تحافظ على الثبات dist[a][b] = dist[b][a]. وبعد لذلك dist[i][j] = dist[j][i] بعد كل خطوات الخوارزمية

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

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

إذا رأيت أي شيء خاطئ في إثباتي، فلا تتردد في توجيهه وسأحاول إصلاحه.

تعديل:

يمكنك السرعة وتوفير نصف الذاكرة عن طريق تغيير الحلقة على هذا النحو:

for (int k = 0; k < N; ++k) {
    for (int i = 0; i < k; ++i)
        for (int j = 0; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
    for (int i = k; i < N; ++i) {
        for (int j = 0; j < k; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]);
        for (int j = k; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]);
    }
}

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

بفضل كريس إليصل الفكرة.

Answer 2

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

على مستوى أقل، تحتاج فقط إلى تخزين نصف المصفوفة (نظرا لأن D (I، J) = D (J، I))، حتى تتمكن من تقليل كمية الذاكرة المستخدمة، ونأمل أن تقلل من عدد مخزول ذاكرة التخزين المؤقت منذ ذلك الحين ستحصل على نفس البيانات عدة مرات.