تعداد امکان عبور از یک شبکه شش ضلعی.

مدیران انجمن: parse, javad123javad

ارسال پست
نمایه کاربر
rohamjpl

نام: Roham Hesami رهام حسامی

محل اقامت: فعلا تهران قیطریه بلوار کتابی 8 متری صبا City of Leicester Area of Leicestershire LE7

عضویت : سه‌شنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴


پست: 1651

سپاس: 3161

جنسیت:

تماس:

تعداد امکان عبور از یک شبکه شش ضلعی.

پست توسط rohamjpl »

رباتی در امتداد بخش های خط در شبکه شش ضلعی نشان داده شده از ابتدا تا انتها راه می رود. اگر فلش وجود داشته باشد، ربات باید در جهتی که نشان داده شده است برود و هرگز روی یک پاره خط دو بار نمی رود. ربات چند مسیر مختلف می تواند طی کند؟تصویر
من به دنبال پاسخی برای این نیستم، فقط راهنمایی در مورد چگونگی شروع. من یک راه اندازی ماتریس مجاورت دارم و می دانم که می توانم از A^r برای یافتن احتمالات برای تعداد r طول استفاده کنم، اما این شامل انتخاب مجدد همان مسیرها می شود. چگونه از آن دست انداز عبور کنم؟نمودار نردبانی معادل
ابتدا عبارت ماتریس در شکل بالا را فراموش کنید. برخی از لبه های این نمودار نردبانی با یک عدد برچسب گذاری شده اند. این بدان معنی است که لبه در نمودار نردبان با چندین لبه در شانه عسل اصلی مطابقت دارد.
واضح است که نمودار نردبانی از 3 واحد تکراری تشکیل شده است. تصویر زیر مطابقت بین سمت چپ شانه عسلی را با اولین واحد ساختمان نشان می دهد.تصویر
واحد ساختمانی
هر واحد از 2 ورودی در سمت چپ، 2 خروجی در سمت راست، 2 متر فلش رو به جلو و 1 فلش رو به عقب در وسط تشکیل شده است. می توان ورودی یک واحد مثلا A را به 3 روش ممکن به خروجی های B یا C متصل کرد.
جریان های احتمالی در یک واحد ساختمانیتصویر
همانطور که در شکل 3 نشان داده شده است، وجود دارد
(شکل 3a) راه های$ m+m=2m$ بدون استفاده از فلش رو به عقب به B متصل می شوند.
(شکل 3b) راه های$ m+m=2m$ بدون فلش رو به عقب به C متصل می شوند.
(شکل 3c) راه های $m \times m = m^2$ با استفاده از فلش رو به عقب به C متصل می شوند.تصویر
برای هر واحد ساختمانی، می‌توانیم تعداد احتمالات اتصال ورودی به خروجی را با استفاده از یک ماتریس 2×2 خلاصه کنیم:
$A(m) = \begin{pmatrix}2m & 2m+m^2\\2m+m^2 & 2m\end{pmatrix}$
به طور خاص، برای واحدهای ساختمانی A(1) و A(2) که در شانه عسل ظاهر می شوند، داریم:
$A(1) = \begin{pmatrix}2 & 3\\3 & 2\end{pmatrix}\;\;\text{ and }\;\;
A(2) = \begin{pmatrix}4 & 8\\8 & 4\end{pmatrix}$
هنگامی که می توان یک گراف جهت دار را به زنجیره ای از زیرگراف ها تقسیم کرد که خروجی یک زیرگراف به ورودی زیرگراف بعدی وارد می شود. شمارش تمام مسیرهای ممکن از ابتدا تا انتها ساده شده است. این به یک مجموع شرط از تعداد مسیرها مشروط به یال هایی که بین زیرگراف ها گرفته می شود تبدیل می شود.
محاسبه تعداد کل مسیرها $\mathcal{N}_{path}$ به ارزیابی حاصل ضرب ماتریس ماتریس‌های متناظر تبدیل می‌شود و عبارت ماتریس را می‌توان با بررسی نمودار یادداشت کرد! این همان چیزی است که عبارت ماتریس مرموز در شکل 1 برای آن است و نتیجه نهایی این است:
$\mathcal{N}_{path} = \begin{pmatrix}1\\1\end{pmatrix}^T
\begin{pmatrix}2 & 3\\3 & 2\end{pmatrix}
\begin{pmatrix}2 & 0\\0 &2\end{pmatrix}
\begin{pmatrix}4 & 8\\8 & 4\end{pmatrix}
\begin{pmatrix}2 & 0\\0 &2\end{pmatrix}
\begin{pmatrix}2 & 3\\3 & 2\end{pmatrix}
\begin{pmatrix}1\\1\end{pmatrix} = 2400$
اگر از هیچ یک از فلش های رو به عقب استفاده نمی کنید، به وضوح $2^2\cdot 4^3 \cdot 2^2=2^{10}=1024$ مسیر وجود دارد. شما می توانید از هر زیر مجموعه ای از سه فلش رو به عقب استفاده کنید، اما هر یک از آنها تعداد مسیرهای ممکن را ضریب 2 (برای ستون چهارم) یا 4 (برای ستون دوم و ششم) کاهش می دهد: می توانید از نیمی از مسیر جلو استفاده کنید. فلش ها اولین باری که با فلش رو به عقب در سراسر ستون به جلو می روید (آنهایی که می توانید بدون عبور از ردیف مرکزی به آنها برسید و ضریب 1/2 را نشان دهید). شما می توانید از نیمه دیگر بار دوم استفاده کنید (یک انتخاب اضافی، دادن ضریب 1 یا 2). و هنگامی که از ستون بعدی به سمت راست عبور می کنید، فقط می توانید از نیمی از فلش ها استفاده کنید (دوباره، آنهایی که می توانید بدون عبور از ردیف مرکزی به آنها برسید و ضریب دیگری برابر با 1/2 می دهد). بنابراین نتیجه این است
$1024 \cdot \left(1+\frac{1}{4}\right)\cdot\left(1+\frac{1}{2}\right)\cdot\left(1+\frac{1}{4}\right)=2400.$
به طور خاص، 1024 مسیر بدون فلش رو به عقب، 1024 با استفاده از یک فلش رو به عقب، 320 با استفاده از دو تا از آنها و 32 با استفاده از هر سه وجود دارد. میشه 2400.hope I helped you understand the question. Roham Hesami, sixth
semester of aerospace engineering
smile072 smile072 رهام حسامی ترم ششم مهندسی هوافضاتصویر
تصویر

ارسال پست