توضیحات
کد الگوریتم دایجسترا را برای کوتاه ترین مسیر وابسته به زمان با متلب
چکیده:
ما یک مطالعه مختصر از مشکل کوتاهترین مسیر وابسته به زمان ، خصوصیات نظری آن و الگوریتم های راه حل آن ارائه می دهیم. شبکه های وابسته به زمان ، که در آن زمان سفر در امتداد هر قوس ، یک عملکرد شناخته شده از زمان عزیمت در طول قوس است ، در بسیاری از برنامه های کاربردی عملی ، به ویژه آنهایی که مربوط به حمل و نقل وسایل نقلیه هستند ، بوجود می آیند. از آنجا که مشکل کلی حداقل NP- سخت است ، ما کاملاً روی پرونده شبکه های FIFO تمرکز می کنیم ، که کالاها از طریق قوس ها به روش First-In-First-Out حرکت می کنند. این مورد خاص در عمل بسیار متداول است و امکان توسعه ویژگی های غنی نظری و الگوریتم های راه حل حساس را فراهم می کند. هدف ما ارائه یک چارچوب یکپارچه است که شامل طیف گسترده ای از انواع مشکل در هر دو گسسته و مداوم است ، که به کارهای گذشته و تحولات اخیر می پردازد. پروژه صنایع
مقدمه
مشکل کوتاهترین مسیر استاتیک یکی از مشکلات مورد بررسی در تئوری نمودار الگوریتمی است. با این حال ، در واقعیت ، بسیاری از شبکه ها تمایل به ویژگی های پویا دارند که برای محاسبه کوتاهترین مسیرها به روشهای پیچیده تری نیاز دارند. دو نوع مشکل پویا کوتاهترین مسیر وجود دارد: در اولین ، باید کوتاهترین مسیرها را بخاطر تغییرات مکرر ، آنی و غیرقابل پیش بینی در داده های شبکه بازپرداخت کنید. این در واقع مسئله ی دوباره استفاده مجدد برای حل یک سری از مشکلات کوتاه مدت مسیر استاتیک نزدیک است. نوع دوم ، و مطالعه این مقاله ، مشکل کوتاهترین مسیر وابسته به زمان است که ویژگی های شبکه با زمان با روشی قابل پیش بینی تغییر می کنند. چنین مشکلاتی اغلب در حمل و نقل وسایل نقلیه بوجود می آید. کوتاهترین مسیری که از عکس فوری از داده های شبکه در زمان فعلی محاسبه می شود ممکن نیست مطلوب باشد اگر یک فرد تغییرات آینده قابل پیش بینی در زمان های قوس الکتریکی را در نظر بگیرد که هنگام سفر از طریق شبکه به خصوص در حدود زمان هایی مانند ساعت \ عجله اتفاق می افتد. .در مشکل کوتاهترین مسیر وابسته به زمان ، فرض می کنیم که زمان سفر در امتداد هر قوس ، تابعی از زمان عزیمت در طول قوس است و همه این کارکردها از قبل در طول زمان شناخته شده است. ، هنگامی که اولین بار در کوک و هالی توسط Cooke و Halsey مطرح شد. [5] مشکل کلیترین مسیر وابسته به زمان حداقل NP-Hard است زیرا ممکن است برای حل انواع مشکلات بهینه سازی NP-Hard مانند کوله پشتی استفاده شود. مشکل ، با این وجود ، بسته به اینکه چگونه این مشکل حل شده باشد ، ممکن است در NP نباشد زیرا خروجی آن به صورت چند جمله ای محدود نشده است ؛ علاوه بر این ، همانطور که توسط Orda و Rom نشان داده شده است [13] حتی نمونه هایی با زمان مداوم وجود دارد که کوتاهترین مسیرها در آن وجود دارد. از یک ترتیب توالی قوسها. در این مقاله ، ما یک کلاس خاص از شبکه های معروف به شبکه های FIFO را مطالعه می کنیم ، که کالاها به روش First-In-First-Out در امتداد قوس ها حرکت می کنند. در عمل ، بسیاری از شبکه ها ، به ویژه شبکه های حمل و نقل ، رفتار FIFO را نشان می دهند. تحت فرض FIFO ، مشکلات کوتاه مدت مسیر وابسته به زمان بسیاری از ویژگی های ساختاری خوب را نشان می دهد که امکان توسعه الگوریتم های راه حل چند جمله ای زمان دقیق را فراهم می کند. هدف ما در این بحث بررسی خصوصیات نظری و الگوریتم های راه حل مشکلات کوتاهترین مسیر وابسته به زمان در یک چارچوب ساده است که نتایج قبلی را در هر دو زمان مداوم و گسسته به هم می پیوندد. در این چارچوب ، طیف گسترده ای از انواع مشکل را در نظر می گیریم.
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.