درصورتیکه جستجو اول سطح استفاده شود و ضریب انشعاب ( فاکتور شاخه شدن) یک درخت جستجو ۳ باشد. حل مساله در آخرین راسی که درعمق ۲ جستجو میشود (عمق جواب بهینه) وجود دارد. چه تعداد راس باید بسط و چه تعداد راس باید تولید شوند؟
این سوال دولتی ۸۷
من جواب راهیان براتون می ذارم اگه بازم مشکلی بود بگین تا بیشتر توضیح بدم
منظور از گره های بسط داده شده گره هایی که فرزندهای آنها تولید و به درخت اضافه شده
الگوریتم bfs تا قبل از رسیدن به گره هدف در عمق ۲، گره های عمق ۰ و ۱و ۲ را بسط میدهد
در عمقهای ۰ و ۱و ۲ به ترتیب b0=1 , b1=3 , b2=9 گره بسط داده شده تا به جواب برسیم ۱+۳+۹ =۱۳
تعداد گره های تولید شده از فرمول زیر با جایگذاری b=3 , d=2 جواب را بدست می آوریم
[tex]1 b ... b ^d b(b^{d}-1)[/tex]
[tex]1 b b^{2} b(b^{2}-1)=1 3 3^{2} 3(3^{2}-1)[/tex]
که برابر ۳۷
[tex]1 b b^{2} b(b^{2}-1)=1 3 3^{2} 3(3^{2}-1)[/tex]
که برابر ۳۷
مفهوم بسط دادن اینه که ما گره رو ملاقات کنیم و با ملاقات گره فرزنداش هم به وجود اومدن...که در جست و جوی اول سطح وقتی به آخرین گره یعنی به گره هدف رسیدیم تمام گره های پشت سرمون (یعنی اونایی که ازش رد شدیم تا به هدف برسیم ) میشه جزء گروه بسط داده شده...
گر ه های تولید شده ، گره های بسط داده شده به اضافه ی بچه هایی که در سطر بعدی به وسیله ی گرهای بالاییشون تولید شدن....
در مورد مقدارشون هم که دوستمون در پست قبلی جواب رو نوشتن
