آزمایشگاه آزاد؛ بدون نیاز به ورود
هزارتو رو با BFS و DFS حل کن
در هزارتو، پیدا کردن هر راهی کافی نیست؛ شاید بخوای کوتاه‌ترین راه رو پیدا کنی. دو جور جست‌وجو رو روی همین نقشه امتحان کن و ببین چه نتیجه‌ای می‌دن.
آزمایش رو شروع کناول BFS رو انتخاب کن و اجرا رو بزن؛ بعد DFS رو امتحان کن. رنگ مسیر رو با خانه‌های بررسی‌شده قاطی نکن. عدد «طول مسیر» تعداد خانه‌های مسیر است، با شروع و پایان؛ تعداد حرکت‌ها یکی کمتره.
آزمایشگاه در حال آماده شدنه…
حالا خودت امتحان کن
هر بار فقط یک چیز رو تغییر بده تا اثرش رو ببینی. قبل از اجرا، نتیجه رو حدس بزن.
جست‌وجو لایه‌به‌لایه
BFS رو از فهرست الگوریتم انتخاب کن و اجرا رو بزن. مسیر رنگی از شروع تا مقصد رو دنبال کن.
حدست چیه؟ حدس می‌زنی مسیر انتخاب‌شده چند خانه داره و چند حرکت بینشونه؟
توضیح نتیجه رو ببین
این نقشه برای BFS مسیری با ۱۷ خانه نشان می‌ده؛ چون خانه‌ی شروع و مقصد هم شمرده می‌شن، مسیر ۱۶ حرکت دارد. هر حرکت این هزارتو یکسان است، پس BFS کوتاه‌ترین مسیر را پیدا می‌کند.
یک شاخه تا ته مسیر
الگوریتم رو روی DFS بذار و اجرا کن. مسیر رنگی رو با راه BFS مقایسه کن.
حدست چیه؟ DFS که یک شاخه رو تا جایی که بشه دنبال می‌کنه، اینجا راه کوتاه‌تری پیدا می‌کنه یا بلندتر؟
توضیح نتیجه رو ببین
برای DFS، مسیر ۲۹ خانه است؛ یعنی ۲۸ حرکت. این روش به مقصد می‌رسه، اما این بار مسیرش از راه BFS بلندتره؛ DFS کوتاه‌ترین راه رو تضمین نمی‌کنه.
دو جور نتیجه را جدا بخوان
یک بار BFS و یک بار DFS رو انتخاب کن و دو عدد «خانه‌های بررسی‌شده» و «طول مسیر» رو کنار هم بخون.
حدست چیه؟ اگر یکی از روش‌ها خانه‌ی کمتری بررسی کند، حتماً مسیرش هم کوتاه‌تر می‌شود؟
توضیح نتیجه رو ببین
این مدل برای BFS عدد ۳۲ و برای DFS عدد ۳۱ در خانه‌های بررسی‌شده نشان می‌ده، ولی مسیرها به‌ترتیب ۱۷ و ۲۹ خانه‌اند. پس تعداد خانه‌های بررسی‌شده و کوتاهی مسیر دو چیز جدا هستند؛ ضمن اینکه شمارش خانه‌های بررسی‌شده در این مدل برای دو الگوریتم تعریف یکسانی ندارد.
پشت این حرکت چه خبره؟
هزارتو مثل یک گراف است
هر خانه‌ی باز رو یک نقطه در نظر بگیر و بین خانه‌های بازِ چسبیده به هم راه بکش. دیوارها راه رو می‌بندن؛ شروع بالا و سمت چپ و مقصد پایین و سمت راست نقشه است. حرکت مورب نداریم و همه‌ی حرکت‌ها یک هزینه دارند.
BFS اول نزدیک‌ها را می‌گردد
جست‌وجوی پهنا اول، اول خانه‌های یک حرکت دورتر رو می‌بینه، بعد خانه‌های دو حرکت دورتر و همین‌طور لایه‌به‌لایه پیش می‌ره. چون همه‌ی قدم‌ها در این نقشه هم‌هزینه‌اند، اولین مسیری که به مقصد می‌رسه کمترین تعداد حرکت رو دارد.
DFS یک شاخه را دنبال می‌کند
جست‌وجوی عمق اول از یک شاخه جلو می‌ره؛ اگر به بن‌بست یا خانه‌های دیده‌شده برسد، برمی‌گرده و شاخه‌ی دیگری رو امتحان می‌کنه. ممکنه سریع به مقصد برسد، اما اولین راهی که پیدا می‌کنه لزوماً کوتاه‌ترین نیست.
سؤالت رو بپرس، جوابش رو هم ببین
وقتی توی چت دربارهٔ یک مفهوم درس می‌خونی، دستیار هوش مصنوعی می‌تونه شبیه‌سازی مرتبط رو کنار توضیحش نشون بده. پارامترها رو تغییر می‌دی و با کمک توضیح بعدی، نتیجه رو بهتر می‌فهمی.
شروع یادگیری با چتبرای ادامه در چت، وارد مسیر شروع و ورود می‌شی. نتیجهٔ این آزمایش به چت منتقل نمی‌شه.
نمونهٔ نمایشی از آموزش در چت
چرا DFS با اینکه به مقصد می‌رسه، مسیرش از BFS طولانی‌تره؟
DFS اول یک شاخه رو تا جای ممکن دنبال می‌کنه و وقتی گیر کنه برمی‌گرده. شاید از همین راه به مقصد برسد، اما قبلش از کنار مسیر کوتاه‌تر رد شده باشه. BFS لایه‌به‌لایه می‌گرده؛ با هزینه‌ی برابر برای هر حرکت، اولین راهش کمترین تعداد قدم رو دارد.
سؤال‌های رایج
BFS یعنی چی؟
یعنی جست‌وجوی پهنا اول: از شروع، خانه‌های نزدیک را لایه‌به‌لایه بررسی می‌کند. برای پیدا کردن کوتاه‌ترین مسیر در نقشه‌ای با حرکت‌های هم‌هزینه مناسبه.
DFS همیشه کوتاه‌ترین راه رو پیدا می‌کنه؟
نه. DFS یک شاخه رو جلو می‌ره و وقتی لازم باشه عقب‌گرد می‌کنه. ممکنه راهی پیدا کند که به مقصد برسد، ولی راه کوتاه‌تر دیگری وجود داشته باشد.
چرا خروجی مسیر ۱۷ است ولی ۱۶ حرکت می‌بینم؟
چون این مدل خانه‌های روی مسیر رو می‌شمارد و خانه‌ی شروع و مقصد هم جزوشان‌اند. بین ۱۷ خانه، ۱۶ جابه‌جایی وجود دارد؛ عدد خروجی را با تعداد حرکت اشتباه نگیر.
کدام عدد می‌گوید الگوریتم سریع‌تره؟
این صفحه زمان اجرا نمی‌سنجد. حتی شمارنده‌ی خانه‌های بررسی‌شده هم در BFS و DFS به یک شکل ساخته نشده، پس از تفاوت ۳۲ و ۳۱ نتیجه نگیر کدام سریع‌تر است.
اگر بعضی خانه‌ها سخت‌تر یا پرهزینه‌تر باشن چی؟
آن وقت کمترین تعداد قدم لزوماً کمترین هزینه نیست. این نقشه برای همه‌ی حرکت‌ها هزینه‌ی یکسان فرض می‌کند؛ مسئله‌ی مسیرهای وزن‌دار به الگوریتم دیگری نیاز دارد.