الگوريتم جستجوي دو طرفه

[p.parsaee]

سلام
ميخوام با الگوريتم جستجوي دو طرفه يك مسئله رو حل كنم. مسئله خاصي نيست و هر چيزي مي تونه باشه. از يك طرف مي خوام به روش bfs و از يك طرف ديگه مي خوام به روش dfs جستجو كنم.
دوستان كسي مي تونه يه مثال بزنه؟ و گراف فضاي حالت و درخت ايجاد شده رو رسم كنه؟
اگه كه چهار عامل ارزيابي پيچيدگي زماني، پيچيدگي فضايي، بهينه بودن و كامل بودن رو هم براش بررسي كنيد ممنون ميشم.
لطفا اگه وقت نداريد يه منبع خوب معرفي كنيد

[soroushp]

الگوریتم جستجوی دو طرفه بر bfs بنا شده اما اگر بخوای یک نمونه مساله رو با جستجوی دو طرفه با dfs حل کنی به احتمال زیاد به صورت موازی از همدیگه رد می شوند و به یکدیگر نمی رسند اما اگر سطحی پیمایش بشه مطمئنا به هم می رسند و پیچیدگی زمانی O(b^d/2)l رو داره
تو اینجا (http://barnamenevis.org/showthread.php?333573-%D9%85%D8%AB%D8%A7%D9%84%DB%8C-%D8%A7%D8%B2-Simulated-Annealing) یک مثالی آوردم که از s به g درختش رو می تونی رسم کنی و تو 5و8 به هم می رسند - متاسفانه هیچ کس حاضر نشد کمک کنه ؛ جوابشو پیدا کردم

[p.parsaee]

تشكر مي كنم به خاطر اينكه جوابمو دادين
اما منظور من اين نبود كه در دو طرف از dfs استفاده كنم. ميخوام bfs و dfs رو به صورت تركيبي استفاده كنم. يعني براي جستجوي forward از bfs و براي جستجوي backward از dfs يا برعكس براي جستجوي forward از dfs و براي backward از bfs استفاده كنم. حالا به نظرتون ميشه با همچنين روشي يه مسئله رو حل كرد يعني آيا الگوريتم كامل هست؟ پيچيدگي زماني و فضايي اون چه قدر هست؟ راه حل بهينه رو به دست مي ياره؟

[soroushp]

اگر از یک طرف dfs حرکت کنه به نظره من کامل هست اما مطمئنا بهینه نیست چون تا عمق d پایین می ره و به احتمال زیاد بر می گرده و پدرش رو ملاقات می کنه اما از اون طرف سطحی کامل و بهینه است اگر هزینه هر مسیر یک مقدار ثابت باشه مثال هم پست قبلی رو با دقت نگاه کن ،
پس جواب : کامل هست ، بهینه نیست ؛ پیچیدگی زمانی o(b^d/2 +1),O(m^m/2) رو در نظر بگیر.

[soroushp]

اینم اضافه کنم که پیچیدگی فضایی از طرف bfs O(b^d/2)میشه اما از طرف dfs O(b*m/2) یعنی خطی که همینطور که معلوم هست dfs مسیر رسیدن به گره هدف رو نگه می داره و از بقیه صرف نظر میکنه