خوارزمية التعلم المعزز

خوارزمية البحث الثنائي هي خوارزمية لإيجاد عناصر قائمة مرتبة${\displaystyle x_{1},\ldots ,x_{n}}$يحتاج الأمر${\displaystyle O(\log(n))}$خطوات لإيجاد عنصر ذي قيمة معروفة${\displaystyle y}$في قائمة طويلة${\displaystyle n}$مع توقع${\displaystyle i}$لشغل منصب${\displaystyle y}$يمكن استخدام خوارزمية التعلم المعزز التالية. ^{[ 1 ]}

• أولاً، انظر إلى الموقع${\displaystyle i}$في القائمة. إذا${\displaystyle x_{i}=y}$تم العثور على العنصر.
• لو${\displaystyle x_{i}<y}$انظر إلى المواقع${\displaystyle i+1,i+2,i+4,\ldots }$حتى يتم إنشاء فهرس${\displaystyle j}$مع${\displaystyle x_{j}\geq y}$تم العثور عليه.
  • قم الآن بإجراء بحث ثنائي على${\displaystyle x_{i},\ldots ,x_{j}}$.
• لو${\displaystyle x_{i}>y}$، افعل نفس الشيء كما في الحالة السابقة، ولكن بدلاً من ذلك ضع في اعتبارك${\displaystyle i-1,i-2,i-4,\ldots }$.

يُعرَّف الخطأ على أنه${\displaystyle \eta =|ii^{*}|}$، أين${\displaystyle i^{*}}$هو المؤشر الحقيقي لـ${\displaystyle y}$في خوارزمية التعلم المعزز، يتم فحص المواضع${\displaystyle i+1,i+2,i+4,\ldots }$يأخذ${\displaystyle \log _{2}(\eta )}$خطوات. ثم يتم إجراء بحث ثنائي على قائمة لا يتجاوز حجمها${\displaystyle 2\eta }$، الأمر الذي يستغرق${\displaystyle \log _{2}(\eta )}$خطوات. وهذا يجعل إجمالي وقت تشغيل الخوارزمية${\displaystyle 2\log _{2}(\eta )}$لذا، عندما يكون الخطأ صغيرًا، تكون الخوارزمية أسرع من البحث الثنائي العادي. وهذا يدل على اتساق الخوارزمية. حتى في أسوأ الحالات، سيكون الخطأ في حد أقصى${\displaystyle n}$ثم تستغرق الخوارزمية على الأكثر${\displaystyle O(\log(n))}$خطوات، لذا فإن الخوارزمية قوية.

• مشكلة مطابقة الوزن الأقصى ^{[ 9 ]}