الگوریتم جست و جوی Bidirectional search - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

الگوریتم جست و جوی Bidirectional search

+2 امتیاز
الگوریتم Biderectional search چیست ؟

مرتبه یا order این الگوریتم چی هست ؟

مزیت نسبت به بقیه االگوریتم های جست و جو چیست ؟

به چه شکل پیاده میشود ؟
سوال شده شهریور 7, 1393  بوسیله ی َAI (امتیاز 200)   13 19 30
ویرایش شده شهریور 29, 1393 بوسیله ی BlueBlade

1 پاسخ

+2 امتیاز
 
بهترین پاسخ

الگوریتم Biderectional search به این شکل هست که ما یک یال انتخاب می کنیم بعد یک الگوریتم جست وجو مثلا (BFS) رو از 2 طرف همزمان انجام میدیم .

حالا اگر این 2 جست و جو هر 2 به یک یال هدف برسن (اشتراک داشته باشن ) جواب داریم.(البته باید چک هم بشه که آیا این مسیر آیا کوتاهترین مسیر هست یا نه که در زمان ثابت قابل انجامه)

 

این الگوریتم مثل IDFS اپتیمال هست و سرعت بهتری به نسبت IDFS داره(مرتبه زمانی این الگوریتم b^(d/2  هستش در حالی که IDFS مربتش b^d  هست ) ولی عیب بزرگی که داره اینه که مصرف حافظش به شدت زیاد تره( (b^(d/2 در مقابل bd)

پاسخ داده شده شهریور 29, 1393 بوسیله ی BlueBlade (امتیاز 15,315)   15 18 89
انتخاب شد مهر 4, 1393 بوسیله ی َAI
...