البحث العميق التكراري أولاً

في علوم الحاسوب ، يُعدّ البحث التكراري المُعمّق ، أو تحديدًا البحث التكراري المُعمّق في العمق أولًا ^{[ 1 ]} (IDS أو IDDFS)، استراتيجية بحث في فضاء الحالة /الرسم البياني، حيث تُنفّذ نسخة محدودة العمق من البحث في العمق أولًا بشكل متكرر مع زيادة حدود العمق حتى يتم العثور على الهدف. يُعتبر IDDFS مثاليًا، أي أنه يجد الهدف بأقل عمق ممكن. ^{[ 2 ]} نظرًا لأنه يزور جميع العقد في شجرة البحث وصولًا إلى العمق المطلوب. $d$ قبل زيارة أي عقدة في العمق $d+1$ إن الترتيب التراكمي الذي تتم به زيارة العقد أولاً هو نفسه فعلياً كما هو الحال في البحث بالعرض أولاً . ومع ذلك، فإن IDDFS يستخدم ذاكرة أقل بكثير. ^{[ 1 ]}

خوارزمية للرسوم البيانية الموجهة

يوضح الكود الزائف التالي تطبيق خوارزمية البحث العمقي المحدود العمق (IDDFS) باستخدام خوارزمية البحث العمقي المحدود العمق المتكررة (DLS) للرسوم البيانية الموجهة . ولا يأخذ هذا التطبيق لخوارزمية IDDFS في الاعتبار العقد التي تمت زيارتها مسبقًا.

الدالة IDDFS ( root) مخصصة للعمق من 0 إلى ∞ . تم العثور على، المتبقي ← DLS(الجذر، العمق) إذا كانت النتيجة ≠ null ، فأرجع " تم العثور عليه"، وإلا إذا لم تكن هناك نتائج متبقية، فأرجع "null" .دالة DLS(node, depth) هي: إذا كان العمق = 0 ، فإذا كانت العقدة هدفًا ، فأرجع (node, true )، وإلا فأرجع ( null , true ) (لم يتم العثور عليها، ولكن قد يكون لها أبناء).وإلا إذا كان العمق > 0 فإن أي_متبقي ← خطأ لكل ابن من أبناء العقدة نفّذ تم العثور على، المتبقي ← DLS(child, depth−1) إذا تم العثور على عقدة واحدة على الأقل، فسيتم إرجاع (تم العثور على عقدة، صحيح ). إذا كان هناك عقدة متبقية ، فسيتم إرجاع (تم العثور على عقدة واحدة على الأقل في العمق، دع IDDFS يتعمق). سيتم إرجاع ( لا شيء ، أي عقدة متبقية).

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

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

ملكيات

تحقق خوارزمية البحث العميق أولاً (IDDFS) اكتمال البحث العرضي (عندما يكون عامل التفرع محدودًا) باستخدام كفاءة المساحة للبحث العميق أولاً. إذا وُجد حل، فستجد مسار الحل بأقل عدد من الأقواس. ^{[ 2 ]}

قد يبدو التعميق التكراري للحالات عدة مرات مضيعة للموارد. ومع ذلك، إذا استكشف نظام IDDFS شجرة بحث بعمق $d$ معظم الجهد الإجمالي ينصب على استكشاف الولايات بعمق $d$ نسبةً إلى عدد الحالات في العمق $d$ ^[³^] إن تكلفة زيارة الولايات الواقعة فوق هذا العمق بشكل متكرر تكون ضئيلة دائماً.

تتمثل الميزة الرئيسية لخوارزمية البحث المتكامل أولاً (IDDFS) في البحث عن شجرة اللعبة في أن عمليات البحث المبكرة تُحسّن من فعالية الطرق الاستدلالية الشائعة الاستخدام، مثل طريقة "القاتل" الاستدلالية وتقنية تقليم ألفا-بيتا ، مما يُتيح تقديرًا أدق لقيمة مختلف العقد في البحث النهائي، ويُسرّع من إتمام البحث نظرًا لترتيبه الأمثل. على سبيل المثال، تكون تقنية تقليم ألفا-بيتا أكثر كفاءة عند البحث عن أفضل الحركات أولاً. ^{[ 3 ]}

تتمثل الميزة الثانية في سرعة استجابة الخوارزمية. لأن التكرارات المبكرة تستخدم قيمًا صغيرة لـ $d$ فهي تُنفذ بسرعة فائقة. وهذا يسمح للخوارزمية بتقديم مؤشرات مبكرة للنتيجة على الفور تقريبًا، تليها تحسينات مع مرور الوقت. $d$ تزداد هذه الميزة. عند استخدامها في بيئة تفاعلية، كبرنامج لعب الشطرنج مثلاً ، تُمكّن البرنامج من اللعب في أي وقت باستخدام أفضل نقلة تم التوصل إليها في البحث الذي أنجزه حتى الآن. يمكن صياغة ذلك على أنه مع كل عمق للبحث، يتم إنتاج تقريب أفضل للحل بشكل متكرر ، على الرغم من أن العمل المنجز في كل خطوة هو عملية تكرارية. هذا غير ممكن مع البحث التقليدي في العمق أولاً، الذي لا يُنتج نتائج وسيطة.

التحليل التقاربي

تعقيد الخطة

يُصبح التعقيد الزمني لخوارزمية البحث المتكامل أولاً (IDDFS) في شجرة (متوازنة جيدًا) مماثلاً للبحث بالعرض أولاً، أي $O(b^{d})$ ، ^{[ 1 ]}^{: 5} حيث $b$ هو عامل التفرع و $d$ هو عمق الهدف.

دليل

في عملية بحث التعمق التكرارية، تكون العقد الموجودة في العمق $d$ يتم توسيعها مرة واحدة، تلك الموجودة في العمق $d-1$ يتم توسيعها مرتين، وهكذا حتى جذر شجرة البحث، الذي يتم توسيعه $d+1$ مرات. ^{[ 1 ]}^{: 5} لذا فإن العدد الإجمالي للتوسعات في بحث التعمق التكراري هو

b^{d}+2b^{d-1}+3b^{d-2}+\cdots +(d-1)b^{2}+db+(d+1)=\sum _{i=0}^{d}(d+1-i)b^{i}

أين $b^{d}$ هو عدد التوسعات في العمق $d$ ، $2b^{d-1}$ هو عدد التوسعات في العمق $d-1$ وهكذا. الاستبعاد $b^{d}$ أعطِ

b^{d}(1+2b^{-1}+3b^{-2}+\cdots +(d-1)b^{2-d}+db^{1-d}+(d+1)b^{-d})

والآن لنبدأ $x={\frac {1}{b}}=b^{-1}$ ثم لدينا

b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})

هذا أقل من المتسلسلة اللانهائية

b^{d}(1+2x+3x^{2}+4x^{3}+\cdots )=b^{d}\left(\sum _{n=1}^{\infty }nx^{n-1}\right)

والتي تتقارب إلى

b^{d}(1-x)^{-2}=b^{d}{\frac {1}{(1-x)^{2}}}

، ل

abs(x)<1

أي أننا نمتلك

$b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})\leq b^{d}(1-x)^{-2}$ ، ل $abs(x)<1$

منذ $(1-x)^{-2}$ أو $\left(1-{\frac {1}{b}}\right)^{-2}$ ثابت مستقل عن $d$ (العمق)، إذا $b>1$ (أي، إذا كان عامل التفرع أكبر من 1)، فإن وقت تشغيل البحث التكراري العميق أولاً هو $O(b^{d})$ .

مثال

ل $b=10$ و $d=5$ الرقم هو

\sum _{i=0}^{5}(5+1-i)10^{i}=6+50+400+3000+20000+100000=123456

بشكل عام، بحث متكرر ومتعمق من العمق $1$ وصولاً إلى العمق $d$ يتوسع فقط حول $11\%$ عدد أكبر من العقد مقارنةً بعملية بحث واحدة بالعرض أولاً أو البحث المحدود بالعمق إلى العمق $d$ ، متى $b=10$ [ ⁴^]

كلما زاد عامل التفرع، انخفضت تكلفة توسيع الحالات بشكل متكرر، ^{[ 1 ]}^{: 6} ولكن حتى عندما يكون عامل التفرع 2، فإن البحث التعميقي التكراري يستغرق ضعف الوقت تقريبًا الذي يستغرقه البحث الكامل بالعرض أولاً. هذا يعني أن التعقيد الزمني للبحث التعميقي التكراري لا يزال $O(b^{d})$ .

تعقيد المساحة

التعقيد المكاني لخوارزمية IDDFS هو $O(d)$ ، ^{[ 1 ]}^{: 5} حيث $d$ هو عمق الهدف.

دليل

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

بشكل عام، يُعد التعميق التكراري هو أسلوب البحث المفضل عندما تكون مساحة البحث كبيرة وعمق الحل غير معروف. ^{[ 3 ]}

مثال

بالنسبة للرسم البياني التالي:

سيبدأ البحث العميق أولاً من النقطة A، بافتراض أن الحواف اليسرى في الرسم البياني الموضح يتم اختيارها قبل الحواف اليمنى، وبافتراض أن البحث يتذكر العقد التي تمت زيارتها سابقًا ولن يكررها (نظرًا لأن هذا رسم بياني صغير)، وسيزور العقد بالترتيب التالي: A، B، D، F، E، C، G. تشكل الحواف التي تم اجتيازها في هذا البحث شجرة Trémaux ، وهي بنية لها تطبيقات مهمة في نظرية الرسم البياني .

إن إجراء نفس البحث دون تذكر العقد التي تمت زيارتها سابقًا يؤدي إلى زيارة العقد بالترتيب A، B، D، F، E، A، B، D، F، E، إلخ إلى الأبد، عالقًا في دورة A، B، D، F، E ولا يصل أبدًا إلى C أو G.

يمنع التعميق التكراري هذه الحلقة وسيصل إلى العقد التالية على الأعماق التالية، بافتراض أنه يسير من اليسار إلى اليمين كما هو موضح أعلاه:

العمق 0: أ
العمق 1: أ، ب، ج، هـ

(لقد تمكن التعميق التكراري الآن من رؤية C، في حين أن البحث التقليدي في العمق أولاً لم يتمكن من ذلك.)

العمق 2: أ، ب، د، و، ج، ز، هـ، و

(لا يزال يرى C، لكنه جاء لاحقًا. كما أنه يرى E عبر مسار مختلف، ويعود إلى F مرتين.)

العمق 3: أ، ب، د، و، هـ، ج، ز، هـ، و، ب

بالنسبة لهذا الرسم البياني، مع إضافة المزيد من العمق، ستصبح الدورتان "ABFE" و "AEFB" أطول ببساطة قبل أن تتخلى الخوارزمية عن المحاولة وتجرب فرعًا آخر.

الخوارزميات ذات الصلة

على غرار التعميق التكراري، توجد استراتيجية بحث تُسمى البحث التطويلي التكراري ، تعمل بحدود متزايدة لتكلفة المسار بدلاً من حدود العمق. تُوسّع هذه الاستراتيجية العُقد بترتيب تصاعدي لتكلفة المسار؛ لذا فإن أول هدف تصادفه هو الهدف ذو أقل تكلفة مسار. إلا أن البحث التطويلي التكراري يُكبّد تكلفة إضافية كبيرة تجعله أقل فائدة من التعميق التكراري. ^{[ 3 ]}

التعمق التكراري A* هو بحث أفضل أولاً يقوم بالتعمق التكراري بناءً على قيم " $f$ " المشابهة لتلك المحسوبة في خوارزمية A* .

IDFS ثنائي الاتجاه

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

من عيوب هذه الخوارزمية أنها لا تكتشف أقصر مسار يتكون من عدد فردي من الأقواس. لنفترض أن لدينا أقصر مسار $\langle s,u,v,t\rangle .$ عندما يصل العمق إلى قفزتين على طول الأقواس، سيبدأ البحث الأمامي من $u$ ل $v$ وسيبدأ البحث العكسي من $v$ ل $u$ . من الناحية التصويرية، ستتقاطع حدود البحث، وسيتم إرجاع مسار غير مثالي يتكون من عدد زوجي من الأقواس. يوضح ذلك المخططات أدناه:

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

تكمن الصعوبة الإضافية لتطبيق خوارزمية IDDFS ثنائية الاتجاه في أنه إذا كانت عقد المصدر والهدف في مكونات مختلفة ذات اتصال قوي، على سبيل المثال، $s\in S,t\in T$ ، إذا لم يكن هناك قوس ناشئ $S$ والدخول $T$ لن ينتهي البحث أبداً.

تعقيدات الزمان والمكان

يُعطى زمن تشغيل IDDFS ثنائي الاتجاه بواسطة

2\sum _{k=0}^{n/2}b^{k}

ويُعطى تعقيد المساحة بواسطة

b^{n/2},

أين $n$ عدد العقد في أقصر $s,t$ -المسار. بما أن تعقيد وقت التشغيل للبحث العميق التكراري هو $\sum _{k=0}^{n}b^{k}$ ، يكون التسارع تقريبًا

{\frac {\sum _{k=0}^{n}b^{k}}{2\sum _{k=0}^{n/2}b^{k}}}={\frac {\frac {1-b^{n+1}}{1-b}}{2{\frac {1-b^{n/2+1}}{1-b}}}}={\frac {1-b^{n+1}}{2(1-b^{n/2+1})}}={\frac {b^{n+1}-1}{2(b^{n/2+1}-1)}}\approx {\frac {b^{n+1}}{2b^{n/2+1}}}=\Theta (b^{n/2}).

الشفرة الزائفة

دالة Find-Shortest-Path(s, t) هي: إذا كان s = t، فأرجع <s> ( B , F , Vf , Vb ₎ : ₌ (مكدس فارغ، ∅ , ∅ , ∅ ) ( Δ , lf _, lb ₎ := (0, 0, 0) كرر (F, Vf ₎ := ( ∅ , ∅ )إذا كانت قيمة |V _{f |}تساوي l _{f ،}فسيتم إرجاع قيمة فارغة (l _f , V b ₎ : = (|V _f |, ∅ ₎μ := Depth-Limited-Search-Backward(t, Δ , B, F, V _b ) إذا كانت μ $\neq$ إذا كانت القيمة nil، فقم بإرجاع Build-Path(s, μ , B, G) V _b := ∅ μ := Depth-Limited-Search-Backward(t, Δ + 1, B, F, V _b ) if μ $\neq$ nil ثم قم بإرجاع Build-Path(s, μ , B, G) إذا |B _b | = l _bثم يُرجع nil (l _b , Δ ) := (|V _b |, Δ + 1)

دالة Build-Path(s, μ , B) هي π := Find-Shortest-Path(s, μ ) (تحسب بشكل متكرر المسار إلى عقدة الترحيل) بوب (ب) إرجاع π $\circ$ ب (أضف المجموعة بدءًا من أعلاها.)

دالة البحث الأمامي المحدود العمق (u, Δ , F, V) هي: إذا كان u ∈ V ، فأرجع V := V ∪ {u}، وإذا كان Δ = 0 ، فأرجع F := F ∪ {u} (ضع علامة على u كعقدة حدودية). ثم لكل ابن من أبناء u ، نفّذ دالة البحث الأمامي المحدود العمق (الابن، Δ − 1، F، V).

الدالة Depth-Limited-Search-Backward(u, Δ , B, F, V) هي: إذا كان u ∈ V ، فأرجع nil Push(B, u) إذا كانت Δ = 0، فإذا كانت u ∈ F ، فأرجع u ( تم الوصول إلى العقدة المحددة، استخدمها كعقدة ترحيل). بوب (ب) أرجع قيمة فارغة. V := V ∪ {u} لكل عنصر أب لـ u ، قم بما يلي : μ := البحث العكسي المحدود العمق(العنصر الأب، Δ − 1، B، F، V) إذا كان μ $\neq$ ثم أعد μ إذا كانت القيمة nil بوب (ب) إرجاع قيمة فارغة

مراجع

1 2 3 4 5 6 7 8 كورف، ريتشارد (1985). "البحث التكراري العميق أولاً: بحث شجري مقبول أمثل". الذكاء الاصطناعي . 27 : 97-109 . doi : 10.1016/0004-3702(85)90084-0 . S2CID 10956233 .
1 2 ديفيد بول؛ آلان ماكوورث. "3.5.3 التعميق التكراري ‣ الفصل 3 البحث عن الحلول ‣ الذكاء الاصطناعي: أسس العوامل الحسابية، الطبعة الثانية" . artint.info . تم الاطلاع عليه بتاريخ 29 نوفمبر 2018 .
1 2 3 4 راسل، ستيوارت جيه .؛ نورفيج، بيتر (2003)، الذكاء الاصطناعي: منهج حديث ( الطبعة الثانية)، أبر سادل ريفر، نيو جيرسي: برنتيس هول، ISBN 0-13-790395-2
↑ راسل؛ نورفيج (1994). الذكاء الاصطناعي: منهج حديث .

[re1985-1] 1 2 3 4 5 6 7 8 كورف، ريتشارد (1985). "البحث التكراري العميق أولاً: بحث شجري مقبول أمثل". الذكاء الاصطناعي . 27 : 97-109 . doi : 10.1016/0004-3702(85)90084-0 . S2CID 10956233 .

[:0-2] 1 2 ديفيد بول؛ آلان ماكوورث. "3.5.3 التعميق التكراري ‣ الفصل 3 البحث عن الحلول ‣ الذكاء الاصطناعي: أسس العوامل الحسابية، الطبعة الثانية" . artint.info . تم الاطلاع عليه بتاريخ 29 نوفمبر 2018 .

[rn3-3] 1 2 3 4 راسل، ستيوارت جيه .؛ نورفيج، بيتر (2003)، الذكاء الاصطناعي: منهج حديث ( الطبعة الثانية)، أبر سادل ريفر، نيو جيرسي: برنتيس هول، ISBN 0-13-790395-2

[4] راسل؛ نورفيج (1994). الذكاء الاصطناعي: منهج حديث .

[ 1 ]

[

4

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗