الگوریتم زنجیره عقبگرد backward chaining در هوش مصنوعی
الگوریتم زنجیره عقبگرد backward chainingدر هوش مصنوعی
خانواده بزرگی از الگوریتم های استنتاج منطقی، از روش زنجیره عقبگرد استفاده میکنند که برای کلازهای معین بیان شده است. این الگوریتم ها، از هدف به عقب برمیگردند تا حقایق شناخته شده ای را پیدا کنند که اثبات را پشتیبانی میکنند. کاربرد این الگوریتم در برنامه نویسی منطقی است که پرکاربردترین شکل استدلال خودکار است. این الگوریتم در مقایسه با زنجیره ی پیشرو معایبی دارد.
الگوریتم زنجیره عقبگرد (پسرو)
در ادامه شبه کد این الگوریتم را بیان خواهیم کرد. در این شبه کد، اگر پایگاه دانش شامل کلازی به شکل lhs → goal باشد که lhs (کلاز سمت چپ یا left- hand side) لیستی از ترکیب های عطفی باشد، FOL – BC – ASK (KB, goal) اثبات خواهد شد. یک حقیقت اتمیک بعنوان کلازی در نظر گرفته میشود که lhs آن، لیستی خالی است. اکنون پرس و جویی که شامل متغیرهاست، ممکن است به چندین روش حل شود. بنابراین الگوریتم FOL – BC – ASK را به صورت یک مولد پیاده سازی میکنیم. مولد، تابعی است که چندین بار اجرا میشود و هر بار یک نتیجه ممکن را برمیگرداند.
زنجیره پیشرو نوعی جست وجوی AND/ OR است. علت وجود بخش OR این است که پرس وجوی هدف میتواند با هر قانونی در پایگاه دانش اثبات شود، و علت وجود بخش AND این است که تمام عطف های موجود در lhs مربوط به کلاز باید اثبات شود.
FOL – BC – OR به این صورت کار میکند: تمام کلازهایی را که ممکن است با هدف یکسان سازی شوند، دریافت میکند، متغیرهای موجود در کلاز را استاندارد میکند تا به متغیرهای جدیدی تبدیل شوند، و سپس اگر rhs مربوط به کلاز با هدف یکسان سازی شود، هر ترکیب عطفی موجود در lhs را با استفاده از FOL – BC – AND اثبات میکند، سپس آن تابع هر یک از ترکیبات عطفی را به نوبت اثبات میکند و جایگزینی های انباشته شده را در حین انجام کار، نگهداری میکند.
آنطور که زنجیره عقبگرد را نوشتیم، یک الگوریتم جست وجوی عمقی است. معنایش این است که نیازمندی فضای حافظه ی آن بر حسب اندازه ثابت خطی است. همچنین به معنای این است که زنجیره عقبگرد (بر خلاف زنجیره پیشرو) با مشکلاتی از قبیل حالتهای تکراری و ناکامل بودن مواجه است
شبه کد الگوریتم زنجیره عقبگرد ساده برای پایگاه داده های مرتبه اول
function FOL – BC – ASK (KB, query) returns a generator of substitutions
return FOL – BC – OR (KB, query, {})
function FOL – BC – OR (KB, goal, θ) yields a substitution
for each rule (lhs → rhs) in FETCH-RULES-FOR-GOAL(KB, goal) do
(lhs, rhs) ← STANDARDIZE-VARIABLES ( (lhs, rhs) )
for each θ’ in FOL – BC – AND (KB, lhs, UNIFY (rhs, goal,θ)) do
yield θ’
function FOL – BC – AND (KB, goal, θ) yields a substitution
if θ = failure then return
else if LENGTH(goal) = 0 then yield θ
else do
first, rest ← FIRST (goal), REST (goals)
for each θ’ in FOL – BC – OR (KB, SUBST(θ , first) , θ) do
for each θ’’ in FOL – BC – AND (KB, rest , θ’ ) do
yield θ’’
.gif)
