سلام.
این سوالو پوران گفته جوابش ۳۷ می شه اما راهیان ارشد گفته جواب ۱۳ است. کدوم درسته و چرا؟
ضریب انشعاب یک درخت جست و جو سه می باشد. حل مسئله در آخرین راسی که در عمق دو جست و جو می شود وجود دارد.
چه تعداد راس باید بسط داده شوند. تا این راس بازدید شود. در صورتیکه از جست و جوی عرض نخست (bfs) استفاده شود؟
(فرض بر این است که حل مسئله بودن یک گره در زمان باز کردن فرزندان آن گره بررسی می گردد.)
(فرض بر این است که حل مسئله بودن یک گره در زمان باز کردن فرزندان آن گره بررسی می گردد.)
یعنی وقتی میخوای گره های فرزند را بسط دادی میفهمی جواب هست یا نه.
وقتی ۱۳ گره تا عمق دو را گسترش میدی هنوز نتونستی جواب را پیدا کنی چون باید گره های فرزندشون را هم گسترش بدی تا بفهمی جوابه.
واسه همینم تمام فرزندان ۹ گره سطح آخر را گسترش میدی. البته نهمی را که گسترش دادی جواب بدست میاد. یعنی ۸ گره قبلی هر کدوم ۳ تا فرزند ازشون گسترش میدی که هیچکدوم از این ۸ تا جواب نیستند که تا اینجا ۱۳+ ۲۴ گره باز کردی و هنگامی که میخوای گره نهمی (گره جواب) در سطح ۲ را بسط بدی میفهمی گره هدفه