مساله اقلیدسی مسیر bitonic فروشنده دوره گرد

[mah.s]

سلام
از فصل ششم برنامه نویسی پویا(کتاب دکتر فراهی) سوال اولش که مساله اقلیدسی مسیر bitonic فروشنده دوره گرد رو مطرح کرده کسی هست جوابش رو بدونه؟؟؟؟؟؟؟؟؟؟

[Borna66]

سلام
از فصل ششم برنامه نویسی پویا(کتاب دکتر فراهی) سوال اولش که مساله اقلیدسی مسیر bitonic فروشنده دوره گرد رو مطرح کرده کسی هست جوابش رو بدونه؟؟؟؟؟؟؟؟؟؟

با سلام

شما خوده الگوریتم اش یا (الگوریتم فروشنده دوره گرد) رو می خواهید تا جواب نهایی این مسئله را؟


روزگار خوش

[mah.s]

الگوریتم فروشنده دوره گردکه از مسیر bitonic حل میشه؟؟؟؟؟؟

[Borna66]

الگوریتم فروشنده دوره گردکه از مسیر bitonic حل میشه؟؟؟؟؟؟

دوست گرامی این هم توضیحات بیشتر در مورد مسئله فروشنده دوره گرد The traveling-salesman problem که بدین صورت هست.

مسئله فروشنده دوره گرد TSP یکی از مسائل مهم در زمره تئوری پیچیدگی محاسباتی الگوریتم ها می باشد که در گروه NP-Hard قرار می گیرد این مسئله اولین بار توسط دو دانشمند به نام های 1- هامیلتون ایرلندی و 2- کیرکمن بریتانیایی مطرح شد . معمولا بحث در خصوص این تئوری در مطالب اولیه دروس ریاضیات دانشجویان ریاضی ارائه می شود و در دروسی نظیر تئوری گراف می توانید مطالب مشابه را نیز بدست آورید .

طرح مسئله
تعدادی شهر داریم و هزینه (مسافت) مسافرت به هر یک از آنها مشخص است به دنبال کم هزینه ترین مسیر هستیم بطوریکه از همه شهرها فقط یکبار عیور کنیم و مجددا به محل شروع بازگردیم یا به عبارتی دیگر

فرض بر اینه که فروشنده ای می خواد به شهرهای مختلف بره. این شهرها هم با فاصله های معین از هم قرار دارن و ممکنه یه شهر به شهر دیگه راه نداشته باشه! حالا فروشنده باید مسیرهای مختلف رو محاسبه کنه که از همه ی شهرها رد بشه و کمترین مسافت رو طی کنه!
برای مشخص کردنش از ساختمان داده ی گراف وزن دار استفاده می شه و راه های مختلفی برای حلش وجو داره!

پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد
این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می شود اما اگر به روش برنامه نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن ( (O( (n^2)*(2^ n خواهد شد که جز مرتبه های نمایی است. باید توجه داشت علی رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می باشد .

برای اطلاع بیشتر در این زیمه به ادرس زیر مراجعه کنید

http://pnu-club.com/pnu.thread55261.html#post174278

موفق باشید

روزگار خوش

[mah.s]

ممنون ولی این مسئله رو با استفاده از مسیر bitonic می خواستم یعنی مسیرهایی که ازسمت چپ ترین نقطه شروع میشوند وبه سمت راست ترین نقطه رفته و سپس از راست به طرف چپ برمی گردند(صفحه 245 کتاب درسی)

[Borna66]

ممنون ولی این مسئله رو با استفاده از مسیر bitonic می خواستم یعنی مسیرهایی که ازسمت چپ ترین نقطه شروع میشوند وبه سمت راست ترین نقطه رفته و سپس از راست به طرف چپ برمی گردند(صفحه 245 کتاب درسی)

با سلام
بله همین طور هست

موفق باشید

روزگار خوش