روش شمارش مسیرهای شبکه‌ای؛ از حرکت‌های محدود تا ترکیب‌ها

پاسخ کوتاه

روش شمارش مسیرهای شبکه‌ای برای مسئله‌هایی به کار می‌رود که در آن‌ها حرکت فقط در چند جهت مجاز است و باید تعداد راه‌های رسیدن از یک نقطه به نقطه دیگر را بیابیم. نکته اصلی این است که هر مسیر را می‌توان به رشته‌ای از حرکت‌ها تبدیل کرد؛ سپس با شمارش جایگاه حرکت‌های افقی یا عمودی، مسئله به ترکیب‌ها و ضرایب دوجمله‌ای تبدیل می‌شود.

مدل‌سازی مسیر روی شبکه

یک صفحه مختصات را در نظر بگیرید و نقطه آغاز را مبدأ فرض کنید. اگر حرکت فقط یک واحد به راست یا یک واحد به بالا باشد، برای رسیدن به نقطه (m,n) دقیقاً m حرکت راست و n حرکت بالا لازم است. بنابراین هر مسیر با رشته‌ای شامل m حرف R و n حرف U مشخص می‌شود. مسیر RURU مثلاً یعنی راست، بالا، راست، بالا.

شمارش مسیر بدون مانع

در رشته‌ای با m+n حرکت، کافی است جایگاه m حرکت راست را انتخاب کنیم؛ جایگاه‌های باقی‌مانده خودبه‌خود با حرکت بالا پر می‌شوند. پس تعداد مسیرها برابر است با C(m+n,m) یا به طور هم‌ارز C(m+n,n). فرمول ترکیب نیز چنین است: C(p,q)=p!/(q!(p-q)!). برابری دو شکل از فرمول، نتیجه تقارن انتخاب q عضو یا کنارگذاشتن p-q عضو است.

روش شمارش مسیرهای شبکه‌ای با اصل ضرب

گاهی مسیر باید از چند ناحیه مشخص عبور کند. اگر نقطه میانی A تنها مرحله واسط باشد، تعداد مسیرهای آغاز تا A را در تعداد مسیرهای A تا پایان ضرب می‌کنیم. این کار از اصل ضرب می‌آید: برای هر انتخاب در مرحله اول، هر انتخاب مرحله دوم قابل ترکیب است. اگر چند نقطه واسط جداگانه وجود داشته باشد، باید بررسی کنیم آیا مسیرها هم‌پوشانی دارند یا نه؛ در صورت هم‌پوشانی، جمع ساده می‌تواند باعث شمارش دوباره شود.

وجود مانع و حذف مسیرهای نامعتبر

اگر عبور از نقطه‌ای ممنوع باشد، ابتدا تعداد کل مسیرها را می‌یابیم و مسیرهایی را که از آن نقطه می‌گذرند کم می‌کنیم. تعداد مسیرهای عبوری از نقطه (a,b) برابر حاصل‌ضرب C(a+b,a) در C(m+n-a-b,m-a) است. این روش زمانی مناسب است که یک مانع یا چند مانع مستقل داشته باشیم. برای چند مانع نزدیک، باید دقت کرد که مسیرهای عبوری از دو مانع ممکن است دوبار کم شده باشند؛ در این حالت اصل شمول و عدم شمول لازم می‌شود.

محدودیت جهت حرکت و تشخیص امکان‌پذیری

اگر حرکت به سمت چپ یا پایین مجاز نباشد، هر نقطه فقط زمانی قابل دسترسی است که مختصات مقصد آن از مبدأ کمتر نباشد. اگر بخواهیم از (x1,y1) به (x2,y2) برویم، در صورت x2<x1 یا y2<y1 هیچ مسیر مجازی وجود ندارد. در حالت مجاز، تعداد حرکت‌های افقی x2-x1 و عمودی y2-y1 است و فرمول با جایگزینی همین دو مقدار استفاده می‌شود.

مثال حل‌شده و کنترل منطقی

از (0,0) به (3,2) می‌رویم؛ پس سه حرکت راست و دو حرکت بالا داریم و تعداد مسیرها C(5,3)=10 است. اگر عبور از نقطه (1,1) ممنوع باشد، مسیرهای عبوری از مانع برابر C(2,1)×C(3,2)=2×3=6 می‌شود. بنابراین 10-6=4 مسیر مجاز باقی می‌ماند. برای کنترل، می‌توان مسیرهای مجاز را بر اساس اولین حرکت دسته‌بندی کرد: مسیرهایی که ابتدا راست می‌روند و مسیرهایی که ابتدا بالا می‌روند.

جمع‌بندی؛ نقشه حل مسئله

ابتدا نقطه آغاز و پایان و جهت‌های مجاز را دقیق مشخص کنید. سپس تعداد حرکت‌های هر نوع را بشمارید و از ترکیب برای انتخاب جایگاه آن‌ها استفاده کنید. اگر نقطه واسط وجود داشت، اصل ضرب و اگر مانع وجود داشت، حذف مسیرهای نامعتبر یا شمول و عدم شمول را به کار ببرید. در پایان، کوچک‌ترین حالت‌ها را ذهنی بررسی کنید؛ مثلاً از (0,0) به (1,1) باید دو مسیر وجود داشته باشد: راست سپس بالا، یا بالا سپس راست.

تمرین‌های خودسنجی

تمرین ۱: چند مسیر از (0,0) به (4,3) با حرکت فقط راست و بالا وجود دارد؟ پاسخ: چهار حرکت راست و سه حرکت بالا داریم؛ بنابراین C(7,4)=35. تمرین ۲: از (0,0) به (3,3) می‌رویم و عبور از (1,1) ممنوع است. چند مسیر باقی می‌ماند؟ پاسخ: کل مسیرها C(6,3)=20 است. مسیرهای عبوری از مانع C(2,1)×C(4,2)=2×6=12 می‌شود؛ پس 8 مسیر مجاز داریم. تمرین ۳: از (2,1) به (5,4) چند مسیر وجود دارد؟ پاسخ: سه حرکت راست و سه حرکت بالا لازم است؛ بنابراین C(6,3)=20.

تمرین خودسنجی با پاسخ