Question

یافتن بهترین مسیر با حداقل احتمال تصادفات

Answer 1

شکل شما وضوح کمی دارد و وزن یکی از یال‌ها را نیاورده‌اید. یال ۳ به ۴.

با این حال من وزن آن یال را یک صدم قرار دادم و بقیه را سعی کردم تا آنجا که می‌شود دقت کنم و نزدیک‌ترین حدسم را یادداشت کردم. حاصل مسیر ۱ به ۴ به ۵ به ۷ به ۱۰ شد با احتمال تصادف یک و دو دهم درصد. البته نیاز به یک توضیح داشت که احتمال وقوع تصادف در مسیر را چگونه تعریف می‌کنید. من اینگونه گرفتم که احتمال وقوع تصادف در یک مسیر را جمع احتمال وقوع تصادف در خیابان‌های مورد استفاده در نظر گرفته‌اید.

الگوریتم بسیار ساده‌ای برای این کار وجود دارد که معمول است در درس ریاضیات گسسته یا گراف کارشناسی اشاره شود هر چند که بستگی به دانشگاه مورد نظر نیز دارد.

در رأس شروع وزن صفر را بگذارید و برای گره‌های دیگر وزن را متغیر دهید مثل $x_i$. یال‌هایی که از آن خارج می‌شوند را در نظر بگیرید به هر گره که می‌رسید مینیمم جمع یالی که با آن به آن وارد شدید بعلاوهٔ وزن گرهٔ آغاز آن یال جهت‌دار را به ازای یال‌هایی که به آن گره ختم می‌شوند محاسبه کنید و آن را به عنوان مقدار وزنش قرار دهید و یالی که این مینیمم برایش رخ داده را پررنگ کنید. همین‌گونه پیشروی کنید. پایان‌پذیر بودن الگوریتم به دلیل متنهایی بودن تعداد گره‌ها است. برای هر گره تنها یک یال انتخاب شده و این یال از یک گرهٔ دیگر می‌آید که آن نیز تنها یک یال ختم شونده به خودش پررنگ دارد و این دنباله به گرهٔ ریشهٔ گرافمان (چشمه) منتهی می‌شود پس دقیقا یک مسیر داریم. از نحوهٔ انتخاب وزن و یال نیز کمینه بودن وزن مسیر انتخاب شده نسبت به سایر مسیرها را نیز می‌توانید اثبات کنید.

اکنون نتیجه با توجه به حدس من در مورد وزن‌های یال‌های گراف شما.

Comments

@ AmirHosein
@rahele.ch
به نظرم این یک سوال تحلیل شبکه هست که چندین راه برای این پیشنهاد میشه که میتونید توی اکثر کتاب‌های تحقیق در عملیات این‌ روش‌ها رو پیدا کرد
یکی از این روش‌ها، روش  shortest route یا همان کوتاه ترین مسیر هستش که تقریبا از روش‌های دیگر آسون‌تر هستش