مصفوفة مونجي

في الرياضيات التطبيقية لعلوم الحاسوب ، تعتبر مصفوفات مونج ، أو مصفوفات مونج ، كائنات رياضية سميت على اسم مكتشفها، عالم الرياضيات الفرنسي غاسبار مونج .

يُقال إن المصفوفة m × n هي مصفوفة مونج إذا كان، لكل $i,j,k,\ell$ بحيث $1\leq i<k\leq m{\text{ و }}1\leq j<\ell \leq n,$ يحصل المرء على ^{[ 1 ]} $A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].$ بمعنى آخر، بالنسبة لأي صفين وعمودين من مصفوفة مونج، فإن العناصر الأربعة عند نقاط التقاطع (مصفوفة فرعية 2 × 2) لها الخاصية التي يكون فيها مجموع العنصرين العلوي الأيسر والسفلي الأيمن (على القطر الرئيسي ) أقل من أو يساوي مجموع العنصرين السفلي الأيسر والعلوي الأيمن (على القطر المضاد ).

هذه المصفوفة هي مصفوفة مونجي:

{\begin{bmatrix}10&17&13&28&23\\17&22&16&29&23\\24&28&22&34&24\\11&13&6&17&7\\45&44&32&37&23\\36&33&19&21&6\\75&66&51&53&34\end{bmatrix}}

على سبيل المثال، خذ تقاطع الصفين 2 و4 مع العمودين 1 و5. العناصر الأربعة هي ${\begin{bmatrix}17&23\\11&7\end{bmatrix}}.$ إن مجموع العناصر العلوية اليسرى والسفلية اليمنى (17 + 7 = 24) ليس أكبر من مجموع العناصر السفلية اليسرى والعلوية اليمنى (23 + 11 = 34).

ملكيات

التعريف أعلاه يعادل العبارة

تكون المصفوفة مصفوفة مونجي إذا وفقط إذا

A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]

للجميع

1\leq i<m

و

1\leq j<n

[ ¹^]

أي مصفوفة فرعية يتم إنتاجها عن طريق تحديد صفوف وأعمدة معينة من مصفوفة Monge الأصلية ستكون هي نفسها مصفوفة Monge.
أي تركيبة خطية ذات معاملات غير سالبة لمصفوفات مونج هي في حد ذاتها مصفوفة مونج.
كل مصفوفة من نوع Mong رتيبة تمامًا، أي أن قيمها الدنيا في الصفوف تقع في تسلسل غير متناقص من الأعمدة، وأن هذه الخاصية نفسها تنطبق على كل مصفوفة فرعية. تسمح هذه الخاصية بإيجاد القيم الدنيا في الصفوف بسرعة باستخدام خوارزمية SMAWK . إذا حددتَ بدائرة القيمة الدنيا في أقصى يسار كل صف، فستلاحظ أن دوائرك تتحرك لأسفل نحو اليمين؛ أي إذا $f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]$ ، ثم $f(j)\leq f(j+1)$ للجميع $1\leq j<n$ وبالمثل، إذا حددتَ الحد الأدنى الأعلى لكل عمود، ستتحرك الدوائر نحو اليمين والأسفل. أما الحد الأقصى للصفوف والأعمدة فيتحرك في الاتجاه المعاكس: لأعلى نحو اليمين ولأسفل نحو اليسار.
تم اقتراح مفهوم مصفوفات مونج الضعيفة ؛ وهي عبارة عن مصفوفة مربعة من الرتبة n × n تحقق خاصية مونج. $A[i,i]+A[r,s]\leq A[i,s]+A[r,i]$ للجميع فقط $1\leq i<r,s\leq n$ .
مصفوفة مونج هي اسم آخر للدالة شبه المعيارية لمتغيرين منفصلين. تحديدًا، تكون A مصفوفة مونج إذا وفقط إذا كانت A [ i , j ] دالة شبه معيارية للمتغيرين i و j .

التطبيقات

تُستخدم مصفوفات مونج في مسائل التحسين التوافقي :

عندما تكون مصفوفة تكلفة مسألة البائع المتجول من نوع مونج، يمكن حلها في زمن تربيعي. ^{[ 1 ]}^{[ 2 ]}
تُسمى مصفوفة مونج المربعة المتناظرة حول قطرها الرئيسي مصفوفة سوبنيك (نسبةً إلى فريد سوبنيك ). أي توليفة خطية من مصفوفات سوبنيك هي في حد ذاتها مصفوفة سوبنيك، ^{[ 1 ]} وعندما تكون مصفوفة التكلفة في مسألة البائع المتجول من نوع سوبنيك، يكون الحل الأمثل مسارًا محددًا مسبقًا، لا يتأثر بالقيم المحددة داخل المصفوفة. ^{[ 2 ]}

مراجع

1 2 3 4 بوركارد، راينر إي.؛ كلينز، بيتينا؛ رودولف، روديجر (1996). "وجهات نظر حول خصائص مونج في التحسين". الرياضيات التطبيقية المنفصلة . 70 (2). إلسيفير: 95-96 . doi : 10.1016/0166-218x(95)00103-x .
1 2 بوركارد، راينر إي.؛ دينيكو، فلاديمير جي.؛ فان دال، رينيه؛ فان دير فين، جاك إيه إيه؛ ووجينجر، جيرهارد جيه. (1998). "حالات خاصة قابلة للحل لمسألة البائع المتجول: دراسة استقصائية" . مجلة SIAM . 40 (3): 496-546 . Bibcode : 1998SIAMR..40..496B . doi : 10.1137/S0036144596297514 . ISSN 0036-1445 .

دينيكو، فلاديمير ج .؛ ووجينجر، جيرهارد ج. (أكتوبر 2006). "بعض المشكلات المتعلقة بالباعة المتجولين، ولوحات رمي السهام، وعملات اليورو" (ملف PDF) . نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية . 90. EATCS : 43-52 . ISSN 0252-9742 .

[Burkard1996-1] 1 2 3 4 بوركارد، راينر إي.؛ كلينز، بيتينا؛ رودولف، روديجر (1996). "وجهات نظر حول خصائص مونج في التحسين". الرياضيات التطبيقية المنفصلة . 70 (2). إلسيفير: 95-96 . doi : 10.1016/0166-218x(95)00103-x .

[:0-2] 1 2 بوركارد، راينر إي.؛ دينيكو، فلاديمير جي.؛ فان دال، رينيه؛ فان دير فين، جاك إيه إيه؛ ووجينجر، جيرهارد جيه. (1998). "حالات خاصة قابلة للحل لمسألة البائع المتجول: دراسة استقصائية" . مجلة SIAM . 40 (3): 496-546 . Bibcode : 1998SIAMR..40..496B . doi : 10.1137/S0036144596297514 . ISSN 0036-1445 .

[ 1 ]