الاستدلال المقبول

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

يرتبط هذا بمفهوم الاستدلالات المتسقة . فبينما تُعتبر جميع الاستدلالات المتسقة مقبولة، إلا أن ليس كل الاستدلالات المقبولة متسقة.

تُستخدم طريقة استدلالية مقبولة لتقدير تكلفة الوصول إلى حالة الهدف في خوارزمية بحث مُستنيرة . ولكي تكون هذه الطريقة الاستدلالية مقبولة في مسألة البحث، يجب أن تكون التكلفة المُقدَّرة دائمًا أقل من أو تساوي التكلفة الفعلية للوصول إلى حالة الهدف. تستخدم خوارزمية البحث هذه الطريقة الاستدلالية المقبولة لإيجاد مسار أمثل مُقدَّر إلى حالة الهدف انطلاقًا من العقدة الحالية. على سبيل المثال، في خوارزمية البحث A*، تُستخدم دالة التقييم (حيث ${\displaystyle n}$(العقدة الحالية) هي:

${\displaystyle f(n)=g(n)+h(n)}$

أين

${\displaystyle f(n)}$= دالة التقييم.

${\displaystyle g(n)}$= التكلفة من عقدة البداية إلى العقدة الحالية

${\displaystyle h(n)}$= التكلفة التقديرية من العقدة الحالية إلى الهدف.

${\displaystyle h(n)}$يتم حسابها باستخدام الدالة الاستدلالية. مع دالة استدلالية غير مقبولة، قد تتجاهل خوارزمية A* الحل الأمثل لمسألة البحث بسبب المبالغة في تقديرها.${\displaystyle f(n)}$.

${\displaystyle n}$هي عقدة

${\displaystyle h}$هو أسلوب استدلالي

${\displaystyle h(n)}$التكلفة المشار إليها بواسطة${\displaystyle h}$للوصول إلى هدف من${\displaystyle n}$

${\displaystyle h^{*}(n)}$التكلفة المثلى للوصول إلى هدف ما من${\displaystyle n}$

${\displaystyle h(n)}$مقبول إذا،${\displaystyle \forall n}$

${\displaystyle h(n)\leq h^{*}(n)}$

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

ينطبق مثالان مختلفان من الاستدلالات المقبولة على مسألة الألغاز الخمسة عشر :

• مسافة هامينغ
• مسافة مانهاتن

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

تُعرَّف مسافة مانهاتن للغز على النحو التالي:

${\displaystyle h(n)=\sum _{\text{جميع البلاطات}}{\mathit {المسافة}}({\text{البلاطة، الموضع الصحيح}})}$

لنفترض اللغز التالي حيث يرغب اللاعب في تحريك كل قطعة بحيث تكون الأرقام مرتبة. تُعد مسافة مانهاتن طريقة تقريبية مقبولة في هذه الحالة، لأنه سيتعين تحريك كل قطعة على الأقل بعدد الخانات بينها وبين موضعها الصحيح. ^{[ 2 ]}

تشير الأرقام السفلية إلى مسافة مانهاتن لكل بلاطة. إجمالي مسافة مانهاتن للغز الموضح هو:

${\displaystyle h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36}$

إذا استُخدمت دالة استدلالية مقبولة في خوارزمية، بحيث تتقدم في كل تكرار على المسار ذي أقل تقييم (التكلفة الحالية + الدالة الاستدلالية) من بين عدة مسارات مرشحة، وتتوقف بمجرد وصول استكشافها إلى الهدف، والأهم من ذلك، أنها تغلق جميع المسارات المثلى قبل التوقف (وهو أمر ممكن مع خوارزمية البحث A* إذا لم تُتخذ عناية خاصة ^{[ 3 ]} )، فإن هذه الخوارزمية لا يمكن أن تتوقف إلا على مسار أمثل. ولتوضيح ذلك، انظر إلى البرهان التالي بالتناقض :

لنفترض أن خوارزمية كهذه تمكنت من إنهاء العملية على مسار T بتكلفة حقيقية T _{_true} أكبر من تكلفة المسار الأمثل S بتكلفة حقيقية S _{_true} . هذا يعني أنه قبل إنهاء العملية، كانت التكلفة المُقَدَّرة لـ T أقل من أو تساوي التكلفة المُقَدَّرة لـ S (وإلا لكان تم اختيار S). لنرمز لهاتين التكلفتين المُقَدَّرتين بـ T_{_eval} و S _{_eval} على التوالي. يمكن تلخيص ما سبق كما يلي:

S _صحيح < T _صحيح

Teval ≤ Seval_​​

إذا كان أسلوبنا الاستدلالي مقبولاً، فإنه يترتب على ذلك أنه في هذه الخطوة قبل الأخيرة، يكون T _eval = T _true، لأن أي زيادة في التكلفة الحقيقية بفعل الأسلوب الاستدلالي على T ستكون غير مقبولة، ولا يمكن أن يكون الأسلوب الاستدلالي سالباً. من ناحية أخرى، يتطلب الأسلوب الاستدلالي المقبول أن يكون S _eval ≤ S _true، وهو ما يعطينا، بالاقتران مع المتباينات السابقة، T _eval < T _true، وبشكل أكثر تحديداً T _eval ≠ T _true . بما أن T _eval و T _true لا يمكن أن تكونا متساويتين وغير متساويتين في الوقت نفسه، فلا بد أن افتراضنا كان خاطئاً، وبالتالي يستحيل إنهاء العملية على مسار أكثر تكلفة من المسار الأمثل.

على سبيل المثال، ^{[ 4 ]} لنفترض أن لدينا التكاليف على النحو التالي: (التكلفة أعلى/أسفل العقدة هي التكلفة التقريبية، والتكلفة عند الحافة هي التكلفة الفعلية)

0 10 0 100 0 البداية ---- O ----- الهدف | | 0| |100 | | O ------- O ------ O 100 1 100 1 100

لذلك من الواضح أننا سنبدأ بزيارة العقدة الوسطى العليا، لأن التكلفة الإجمالية المتوقعة، أي${\displaystyle f(n)}$، يكون${\displaystyle 10+0=10}$ثم يصبح الهدف هو اختيار مرشح، مع${\displaystyle f(n)}$يساوي${\displaystyle 10+100+0=110}$ثم نختار بوضوح العقد السفلية واحدة تلو الأخرى، متبوعة بالهدف المُحدَّث، لأنها جميعًا تمتلك${\displaystyle f(n)}$أقل من${\displaystyle f(n)}$من الهدف الحالي، أي${\displaystyle f(n)}$يكون${\displaystyle 100,101,102,102}$لذا، على الرغم من أن الهدف كان مرشحًا، لم نتمكن من اختياره لوجود مسارات أفضل. وبهذه الطريقة، يمكن لأسلوب استدلالي مقبول ضمان الوصول إلى الحل الأمثل.

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

• أسلوب استدلالي متسق
• دالة استدلالية
• خوارزمية البحث