مساله اقلیدسی مسیر bitonic فروشنده دوره گرد [بایگانی] - باشگاه دانشجویان دانشگاه پیام نور

PDA

توجه ! این یک نسخه آرشیو شده می باشد و در این حالت شما عکسی را مشاهده نمی کنید برای مشاهده کامل متن و عکسها بر روی لینک مقابل کلیک کنید : مساله اقلیدسی مسیر bitonic فروشنده دوره گرد

mah.s

06-07-2011, 10:55 AM

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

Borna66

06-07-2011, 11:45 AM

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

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

روزگار خوش

mah.s

06-09-2011, 06:37 PM

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

Borna66

06-09-2011, 11:32 PM

الگوریتم فروشنده دوره گردکه از مسیر 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

06-10-2011, 06:53 PM

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

Borna66

10-23-2011, 12:25 AM