وظيفة الحفاظ على الاتجاه

📅 آخر تحديث: ١٩ يوليو ٢٠٢٦
✍️ نُشر في: ١٩ يوليو ٢٠٢٦
📷 يحتوي على 13 صور
الموسوعة الحرة

في الرياضيات المتقطعة ، الدالة الحافظة للاتجاه (أو التطبيق) هي دالة على فضاء متقطع ، مثل شبكة الأعداد الصحيحة، لا تتغير بشكل جذري بين نقطتين متجاورتين. ويمكن اعتبارها نظيراً متقطعاً للدالة المتصلة .

تم تعريف هذا المفهوم لأول مرة من قبل إيمورا. [ 1 ] [ 2 ] وقد تم تعريف بعض المتغيرات منه لاحقًا من قبل يانغ، [ 3 ] وتشن ودينغ، [ 4 ] وهيرينغز، وفان دير لان، وتالمان ويانغ، [ 5 ] وآخرين.

المفاهيم الأساسية

نحن نركز على الوظائف و:X→Rن{\displaystyle f:X\to \mathbb {R} ^{n}}، حيث أن المجال X هو مجموعة جزئية منتهية من الفضاء الإقليديRن{\displaystyle \mathbb {R} ^{n}}. ch( X ) يرمز إلى الغلاف المحدب لـ X.

توجد العديد من الصيغ لخصائص الحفاظ على الاتجاه، وذلك بحسب كيفية تعريف "التغيير الجذري" و"النقاط المجاورة" بدقة. وفيما يتعلق بـ"التغيير الجذري"، توجد صيغتان رئيسيتان:

  • يعني الحفاظ على الاتجاه (DP) أنه إذا كان x و y متجاورين، فإن لكلأنا∈[ن]{\displaystyle i\in [n]}:وأنا(x)⋅وأنا(y)≥0{\displaystyle f_{i}(x)\cdot f_{i}(y)\geq 0}بعبارة أخرى: يجب ألا يغير أي مكون من مكونات الدالة f إشاراته بين النقاط المتجاورة.
  • يعني الحفاظ على الاتجاه الإجمالي (GDP) أنه إذا كان x و y متجاورين، فإنو(x)⋅و(y)≥0{\displaystyle f(x)\cdot f(y)\geq 0}بعبارة أخرى: لا يتغير اتجاه الدالة f (كمتجه) بأكثر من 90 درجة بين النقاط المتجاورة. لاحظ أن DP يستلزم GDP، ولكن ليس العكس.

فيما يتعلق بـ "النقاط المجاورة"، هناك عدة صيغ:

  • المكعب الفائق يعني أن x و y متجاوران إذا وفقط إذا كانا موجودين في مكعب فائق متوازي المحاور طول ضلعه 1.
  • تعني كلمة "تبسيطي" أن x و y متجاوران إذا وفقط إذا كانا رأسين لنفس المُبسط، في تثليث ما للمجال. عادةً، يكون التجاور التبسيطي أقوى بكثير من التجاور المكعبي الفائق؛ وبناءً على ذلك، فإن البرمجة الديناميكية المكعبية الفائقة أقوى بكثير من البرمجة الديناميكية التبسيطية.

ترد أدناه تعريفات محددة. جميع الأمثلة أدناه خاصة بـن=2{\displaystyle n=2}الأبعاد و لـ X = { (2,6), (2,7), (3, 6), (3, 7) }.

الخصائص والأمثلة

الحفاظ على اتجاه المكعب الفائق

الخلية هي مجموعة فرعية منRن{\displaystyle \mathbb {R} ^{n}}يمكن التعبير عن ذلك بواسطةك+[0،1]ن{\displaystyle k+[0,1]^{n}}بالنسبة للبعضك∈Zن{\displaystyle k\in \mathbb {Z} ^{n}}على سبيل المثال، المربع[2،3]×[6،7]{\displaystyle [2,3]\times [6,7]}هي خلية.

نقطتانRن{\displaystyle \mathbb {R} ^{n}}تُسمى الخلايا متصلة إذا كانت هناك خلية تحتوي على كليهما.

تتطلب خصائص الحفاظ على الاتجاه في المكعب الفائق ألا تتغير الوظيفة بشكل جذري في النقاط المتصلة بالخلية (النقاط الموجودة في نفس الخلية المكعبة الفائقة).

فا أ67
2(2,1)(1,1)
3(0,1)(0,0)

يُطلق على الدالة f اسم دالة الحفاظ على الاتجاه في الفضاء المكعب الفائق (HDP) إذا كان، لأي زوج من النقاط المتصلة بالخلية x و y في X، لكلأنا∈[ن]{\displaystyle i\in [n]}:وأنا(x)⋅وأنا(y)≥0{\displaystyle f_{i}(x)\cdot f_{i}(y)\geq 0}يُستخدم مصطلح "الحفاظ على الاتجاه المحلي" (LDP) غالبًا بدلاً من ذلك. [ 1 ] الدالة f a على اليمين هي دالة DP.

  • يستخدم بعض المؤلفين [ 4 ] : ​​التعريف 1 صيغةً تتطلب أنه لأي زوج من النقاط المتصلة بالخلية x و y في X، لكلأنا∈[ن]{\displaystyle i\in [n]}:(وأنا(x)-xأنا)⋅(وأنا(y)-yأنا)≥0{\displaystyle (f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0}. الدالة f ( x ) هي HDP حسب الصيغة الثانية، إذا وفقط إذا كانت الدالة g ( x ):= f ( x )- x هي HDP حسب الصيغة الأولى.
f b67
2(2,1)(1,1)
3(1,-1)(0,0)

يُطلق على f اسم الحفاظ على الاتجاه الإجمالي المكعب الفائق (HGDP) ، أو الحفاظ على الاتجاه الإجمالي محليًا (LGDP) ، إذا كان لأي زوج من النقاط المتصلة بالخلية x و y في X،و(x)⋅و(y)≥0{\displaystyle f(x)\cdot f(y)\geq 0}[ 3 ] : تعريف 2.2: كل دالة HDP هي دالة HGDP، ولكن العكس غير صحيح. الدالة f b هي دالة HGDP، لأن حاصل الضرب القياسي لكل متجهين في الجدول غير سالب. لكنها ليست دالة HDP، لأن المكون الثاني يغير إشارته بين (2,6) و(3,6).و2ب(2،6)⋅و2ب(3،6)=-1<0{\displaystyle f_{2}^{b}(2,6)\cdot f_{2}^{b}(3,6)=-1<0}.

  • يستخدم بعض المؤلفين [ 5 ] صيغةً تتطلب أنه بالنسبة لأي زوج من النقاط المتصلة بالخلايا x و y في X،(و(x)-x)⋅(و(y)-y)≥0{\displaystyle (f(x)-x)\cdot (f(y)-y)\geq 0}. الدالة f ( x ) هي HGDP وفقًا للمتغير الثاني، إذا وفقط إذا كانت الدالة g ( x ):= f ( x )- x هي HGDP وفقًا للمتغير الأول.

الحفاظ على الاتجاه بشكل مبسط

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

تثليث مجموعة فرعية منRن{\displaystyle \mathbb {R} ^{n}}يُطلق عليه اسم صحيح إذا كانت جميع عناصره البسيطة صحيحة.

بالنظر إلى عملية التثليث، يُطلق على نقطتين اسم متصلتين بشكل بسيط إذا كان هناك مُركب بسيط من عملية التثليث يحتوي على كليهما.

لاحظ أنه في التثليث التكاملي، تكون كل نقطة متصلة بشكل تبسيطي متصلة أيضًا بالخلية، ولكن العكس ليس صحيحًا. على سبيل المثال، ضع في اعتبارك الخلية [2،3]×[6،7]{\displaystyle [2,3]\times [6,7]}لنفترض التثليث التكاملي الذي يقسمها إلى مثلثين: {(2,6),(2,7),(3,7)} و {(2,6),(3,6),(3,7)}. النقطتان (2,7) و (3,6) متصلتان بالخلية ولكنهما ليستا متصلتين بشكل تبسيطي.

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

يُطلق على الدالة f اسم دالة الحفاظ على الاتجاه التبسيطي (SDP) إذا كان، بالنسبة لبعض التثليثات التكاملية لـ X ، لأي زوج من النقاط المتصلة تبسيطيًا x و y في X، لكلأنا∈[ن]{\displaystyle i\in [n]}:(وأنا(x)-xأنا)⋅(وأنا(y)-yأنا)≥0{\displaystyle (f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0}[ 4 ] : التعريف 4

f c67
2(2,1)(1,1)
3(1،-2)(0,0)

يُطلق على f اسم الحفاظ على الاتجاه الإجمالي البسيط (SGDP) أو الحفاظ على الاتجاه الإجمالي المحلي البسيط (SLGDP) إذا وُجد تثليث متكامل لـ ch( X ) بحيث، لأي زوج من النقاط المتصلة بشكل بسيط x و y في X،و(x)⋅و(y)≥0{\displaystyle f(x)\cdot f(y)\geq 0}[ 6 ] [ 7 ] [ 8 ]​

كل دالة HGDP هي دالة SGDP، لكن HGDP أقوى بكثير: فهي مكافئة لـ SGDP بالنسبة لجميع التثليثات التكاملية الممكنة لـ ch( X )، بينما ترتبط SGDP بتثليث واحد . [ 3 ] : تعريف 2.3. على سبيل المثال، الدالة f c على اليمين هي SGDP بالتثليث الذي يقسم الخلية إلى المثلثين {(2,6),(2,7),(3,7)} و{(2,6),(3,6),(3,7)}، لأن حاصل الضرب القياسي لكل متجهين في كل مثلث غير سالب. لكنها ليست HGDP، لأنوج(3،6)⋅وج(2،7)=-1<0{\displaystyle f^{c}(3,6)\cdot f^{c}(2,7)=-1<0}.

مراجع

  1. 1 2 إيمورا، تاكويا (2003-09-01). "نظرية النقطة الثابتة المنفصلة وتطبيقاتها" . مجلة الاقتصاد الرياضي . 39 (7): 725-742 . doi : 10.1016/S0304-4068(03)00007-7 . ISSN 0304-4068 . 
  2. ^ إيمورا، تاكويا. موروتا، كازو؛ تامورا ، أكيهيسا (2005/12/01). "إعادة النظر في نظرية النقطة الثابتة المنفصلة" . مجلة الاقتصاد الرياضي . 41 (8): 1030-1036 . دوى : 10.1016/j.jmateco.2005.03.001 . ISSN 0304-4068 . 
  3. 1 2 3 يانغ، زايفو (2009-12-01) [2004 (ورقة عمل FBA رقم 210، جامعة يوكوهاما الوطنية)]. "تحليل النقطة الثابتة المنفصلة وتطبيقاته". مجلة نظرية النقطة الثابتة وتطبيقاتها . 6 (2): 351-371 . doi : 10.1007/s11784-009-0130-9 . ISSN 1661-7746 . S2CID 122640338 .  
  4. 1 2 3 تشين، شي ؛ دينغ، شياوتي (2006). "نهج تبسيطي لنظريات النقطة الثابتة المنفصلة". في تشين، داني زد؛ لي، دي تي (محرران). الحوسبة والتوافقية . سلسلة محاضرات في علوم الحاسوب. المجلد 4112. برلين، هايدلبرغ: سبرينغر. الصفحات 3-12 . doi : 10.1007/11809678_3 . ISBN   978-3-540-36926-4.
  5. 1 2 جان جاك هيرينجس، ب.؛ فان دير لان، جيرارد؛ تالمان، دولف. يانغ ، زايفو (2008-01-01). "نظرية النقطة الثابتة للدوال المتقطعة" . رسائل بحوث العمليات . 36 (1): 89-93 . دوى : 10.1016/j.orl.2007.03.008 . اتش دي ال : 10419/86189 . ردمك 0167-6377 . S2CID 14117444 .  
  6. ↑ إيمورا، تاكويا؛ يانغ، زايفو (1 ديسمبر 2009). "دراسة حول توافق الطلب والاستجابة في ظل عدم قابلية التجزئة". مجلة نظرية النقطة الثابتة وتطبيقاتها . 6 (2): 333-349 . doi : 10.1007/s11784-009-0131-8 . ISSN 1661-7746 . S2CID 121519442 .  
  7. ↑ فان دير لان، جيرارد؛ تالمان، دولف؛ يانغ، زايفو (1 يناير 2007). "طريقة تصنيف المتجهات لحل مسائل النقطة الصفرية المنفصلة ومسائل التكاملية" (ملف PDF) . مجلة SIAM للتحسين . 18 (1): 290-308 . doi : 10.1137/050646378 . ISSN 1052-6234 . 
  8. ↑ يانغ، زايفو (2008-11-01). "حول حلول مسائل التكاملية غير الخطية المنفصلة والمسائل ذات الصلة". رياضيات بحوث العمليات . 33 (4): 976-990 . doi : 10.1287/moor.1080.0343 . ISSN 0364-765X .