نموذج شجرة القرار

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

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

تُعدّ نماذج شجرة القرار أداةً أساسيةً في تحديد الحدود الدنيا لتعقيد فئات معينة من المسائل الحسابية والخوارزميات. وقد طُرحت عدة أنواع من نماذج شجرة القرار، وذلك تبعاً للنموذج الحسابي ونوع خوارزميات الاستعلام المسموح بتنفيذها.

على سبيل المثال، تُستخدم حجة شجرة القرار لإظهار أن نوع المقارنة هو${\displaystyle n}$يجب أن تكون العناصر${\displaystyle n\log(n)}$المقارنات. بالنسبة لفرز المقارنة، فإن الاستعلام هو مقارنة بين عنصرين.${\displaystyle a,b}$مع نتيجتين (بافتراض عدم تساوي أي من العناصر): إما${\displaystyle a<b}$أو${\displaystyle a>b}$يمكن التعبير عن عمليات الفرز المقارنة على شكل أشجار قرار في هذا النموذج، لأن خوارزميات الفرز هذه لا تقوم إلا بهذه الأنواع من الاستعلامات.

تُستخدم أشجار القرار غالبًا لفهم خوارزميات الفرز وغيرها من المشكلات المماثلة؛ وقد قام بذلك فورد وجونسون لأول مرة . ^{[ 1 ]}

على سبيل المثال، العديد من خوارزميات الفرز هي خوارزميات فرز مقارنة ، مما يعني أنها لا تحصل إلا على معلومات حول تسلسل الإدخال.${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$عبر المقارنات المحلية: اختبار ما إذا${\displaystyle x_{i}<x_{j}}$،${\displaystyle x_{i}=x_{j}}$، أو${\displaystyle x_{i}>x_{j}}$بافتراض أن العناصر المراد فرزها جميعها متميزة وقابلة للمقارنة، يمكن إعادة صياغة هذا السؤال كسؤال إجابته بنعم أو لا: هل${\displaystyle x_{i}>x_{j}}$؟

يمكن نمذجة هذه الخوارزميات على شكل أشجار قرار ثنائية، حيث تكون الاستعلامات عبارة عن مقارنات: تتوافق كل عقدة داخلية مع استعلام، وتتوافق العقد الفرعية للعقدة مع الاستعلام التالي عندما تكون الإجابة على السؤال بنعم أو لا. بالنسبة للعقد الطرفية، يتوافق الناتج مع تبديل .${\displaystyle \pi }$يصف ذلك كيفية إعادة ترتيب تسلسل الإدخال من قائمة العناصر المرتبة بالكامل. (عكس هذا التبديل،${\displaystyle \pi ^{-1}}$(يعيد ترتيب تسلسل الإدخال.)

يمكن إثبات أن عمليات فرز المقارنة يجب أن تستخدم${\displaystyle \Omega (n\log(n))}$المقارنات من خلال حجة بسيطة: لكي تكون الخوارزمية صحيحة، يجب أن تكون قادرة على إخراج كل تبديل ممكن لـ${\displaystyle n}$العناصر؛ وإلا، ستفشل الخوارزمية مع هذا التبديل المحدد كمدخل. لذا، يجب أن تحتوي شجرة القرار المقابلة لها على عدد من الأوراق يساوي على الأقل عدد التبديلات.${\displaystyle n!}$الأوراق. أي شجرة ثنائية تحتوي على الأقل${\displaystyle n!}$تتمتع الأوراق بعمق على الأقل${\displaystyle \log _{2}(n!)=\Omega (n\log _{2}(n))}$لذا، يُعدّ هذا حدًا أدنى لوقت تشغيل خوارزمية فرز المقارنة . في هذه الحالة، يُشير وجود العديد من خوارزميات فرز المقارنة التي تتمتع بهذا التعقيد الزمني، مثل فرز الدمج وفرز الكومة ، إلى أن هذا الحد دقيق. ^{[ 2 ] : 91}

لا تستخدم هذه الحجة أي معلومات حول نوع الاستعلام، لذا فهي في الواقع تُثبت حدًا أدنى لأي خوارزمية فرز يمكن نمذجتها كشجرة قرار ثنائية. وباختصار، هذه إعادة صياغة للحجة النظرية للمعلومات التي تنص على أن خوارزمية الفرز الصحيحة يجب أن تتعلم على الأقل${\displaystyle \log _{2}(n!)}$معلومات جزئية حول تسلسل الإدخال. ونتيجة لذلك، فإن هذا ينطبق أيضاً على أشجار القرار العشوائية.

تستخدم حدود دنيا أخرى لشجرة القرار أن الاستعلام عبارة عن مقارنة. على سبيل المثال، لنفترض مهمة استخدام المقارنات فقط لإيجاد أصغر عدد بين${\displaystyle n}$الأرقام. قبل تحديد أصغر عدد، يجب أن "يخسر" كل عدد باستثناء الأصغر (يُقارن بالأكبر) في مقارنة واحدة على الأقل. لذا، يتطلب الأمر على الأقل${\displaystyle n-1}$إجراء مقارنات لإيجاد الحد الأدنى. (لا تُعطي الحجة القائمة على نظرية المعلومات هنا سوى حد أدنى لـ${\displaystyle \log(n)}$.) وينطبق منطق مماثل على الحدود الدنيا العامة لحساب إحصاءات الترتيب . ^{[ 2 ] : 214}

تعمم أشجار القرار الخطية أشجار القرار المقارنة المذكورة أعلاه لتشمل دوال حسابية تأخذ متجهات حقيقية${\displaystyle x\in \mathbb {R} ^{n}}$كمدخلات. الاختبارات في أشجار القرار الخطية هي دوال خطية: لاختيار معين للأعداد الحقيقية${\displaystyle a_{0},\dots ,a_{n}}$، أخرج إشارة${\displaystyle a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}}$(لا يمكن للخوارزميات في هذا النموذج أن تعتمد إلا على إشارة المخرجات). أشجار المقارنة هي أشجار قرار خطية، لأن المقارنة بين${\displaystyle x_{i}}$و${\displaystyle x_{j}}$يتوافق مع الدالة الخطية${\displaystyle x_{i}-x_{j}}$بحسب تعريفها، لا يمكن لأشجار القرار الخطية إلا تحديد الدوال.${\displaystyle f}$والتي يمكن بناء أليافها عن طريق أخذ اتحادات وتقاطعات أنصاف الفضاءات .

تُعد أشجار القرار الجبرية تعميمًا لأشجار القرار الخطية التي تسمح بأن تكون دوال الاختبار متعددة الحدود من الدرجة${\displaystyle d}$. هندسياً، يتم تقسيم الفضاء إلى مجموعات شبه جبرية (تعميم للمستوى الفائق ).

تُستخدم نماذج شجرة القرار هذه، التي حددها رابين ^{[ 3 ]} ورينغولد [ ^{4 ]،} غالبًا لإثبات الحدود الدنيا في ^{الهندسة} الحسابية . ^{[ 5 ]} على سبيل المثال، أثبت بن أور أن تفرد العنصر (مهمة حساب${\displaystyle f:\mathbb {R} ^{n}\to \{0,1\}}$، أين${\displaystyle f(x)}$تكون القيمة صفرًا إذا وفقط إذا وُجدت إحداثيات مميزة${\displaystyle i,j}$بحيث${\displaystyle x_{i}=x_{j}}$يتطلب ) شجرة قرار جبرية ذات عمق${\displaystyle \Omega (n\log(n))}$[ ^{6 ] وقد تم إثبات ذلك لأول مرة} لنماذج القرار الخطية بواسطة دوبكين وليبتون. ^{[ 7 ]} كما أظهروا أيضًا${\displaystyle n^{2}}$الحد الأدنى لأشجار القرار الخطية في مسألة حقيبة الظهر ، تم تعميمه على أشجار القرار الجبرية بواسطة ستيل وياو. ^{[ 8 ]}

بالنسبة لأشجار القرار المنطقية، تتمثل المهمة في حساب قيمة دالة منطقية مكونة من n بت.${\displaystyle f:\{0,1\}^{n}\to \{0,1\}}$لإدخال${\displaystyle x\in \{0,1\}^{n}}$تتوافق الاستعلامات مع قراءة جزء من المدخلات.${\displaystyle x_{i}}$والناتج هو${\displaystyle f(x)}$قد يعتمد كل استعلام على الاستعلامات السابقة. هناك أنواع عديدة من النماذج الحسابية التي تستخدم أشجار القرار والتي يمكن أخذها في الاعتبار، والتي تقبل مفاهيم تعقيد متعددة، تُسمى مقاييس التعقيد .

ويترتب على التعريفات مباشرة أنه بالنسبة للجميع${\displaystyle n}$الدوال المنطقية ذات البتات${\displaystyle f}$،${\displaystyle Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n}$، و${\displaystyle Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n}$يُعد إيجاد أفضل الحدود العليا في الاتجاه المعاكس هدفًا رئيسيًا في مجال تعقيد الاستعلام.

ترتبط جميع أنواع تعقيد الاستعلام هذه بعلاقة متعددة الحدود. وقد اكتشف كل من بلوم وإمباغليازو ^{[ 10 ]} ، وهارتمانيس وهيماشاندرا ^{[ 11 ]} ، وتاردوس ^{[ 12 ]} بشكل مستقل أن${\displaystyle D(f)\leq R_{0}(f)^{2}}$وجد نعوم نيسان أن تعقيد شجرة القرار العشوائية مونت كارلو يرتبط أيضًا بشكل متعدد الحدود بتعقيد شجرة القرار الحتمية :${\displaystyle D(f)=O(R_{2}(f)^{3})}$[ ^{13 ] (} أظهرت نيسان أيضًا أن${\displaystyle D(f)=O(R_{1}(f)^{2})}$.) من المعروف وجود علاقة أوثق بين نموذجي مونت كارلو ولاس فيغاس:${\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}$[ ^{14 ]} هذه العلاقة مثالية حتى عوامل متعددة اللوغاريتمات. ^{[ 15 ]} أما بالنسبة لتعقيدات شجرة القرار الكمومية ^،${\displaystyle D(f)=O(Q_{2}(f)^{4})}$وهذا الحدّ محكم. ^{[ 16 ] [ 15 ]} وقد بيّن ميدريجانيس ذلك.${\displaystyle D(f)=O(Q_{0}(f)^{3})}$[ ^{17 ] [ 18 ]} تحسين الحد الرباعي بسبب Beals et al ^{. [ 9 ]}

تكون هذه العلاقات متعددة الحدود صالحة فقط للدوال المنطقية الكلية . أما بالنسبة للدوال المنطقية الجزئية ، التي يكون مجالها مجموعة جزئية من${\displaystyle \{0,1\}^{n}}$، فصل أُسّي بين${\displaystyle Q_{0}(f)}$و${\displaystyle D(f)}$من الممكن ذلك؛ تم اكتشاف أول مثال على هذه المشكلة بواسطة دويتش وجوزا .

• فرز المقارنة
• شجرة القرار
• حدسية أنديرا-كارب-روزنبرغ
• الشجرة الممتدة الدنيا §  أشجار القرار