Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > مقدمات هوش مصنوعی > حل مسائل معروف هوش مصنوعي


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۰۹-۳-۱۳۸۸, ۱۲:۵۲ بعد از ظهر   #1 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,307 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Arrow حل مسئله فروشنده دوره گرد(tsp) به روش هاي مختلف

مسئله فروشنده دوره‌گرد (به انگلیسی: Travelling salesman problem ، به‌اختصار: TSP )



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

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

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

كد:
C({1},1) = 0
for (S=2 to n )
for All Subsets S subset of {1,2,3,...} of size S and containing 1
C(S,1) = &
for All J member of S , J<>1
C ( S , J ) = min { C ( S - { J } , i ) + D i,J : i member of S , i <> J }
return min j C ( {1 . . . n}, J ) + D J,1
.............
اين مسئله ، مسئله‌ای مشهور است که ابتدا در سده ۱۸ مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثل کارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.
شرح مسئله بدین شکل است:
تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
تعداد کل راه‌حل‌ها برابر است با برای n>۲ که n تعداد شهرها است. در واقع این عدد برابر است با تعداد دورهای همیلتونی در یک گراف کامل با n رأس.

مسئله‌های مرتبط

مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP ) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاٌ از یک شهر عبور کند. این مسئله به « مسئله سیاست‌مدار مسافر» نیز شهرت دارد.

الگوریتم‌ها
مسئله فروشنده دوره‌گرد جزء مسائل NP-hard است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:
طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
استفاده از الگوریتم‌های مکاشفه‌ای که جواب‌هایی به‌دست می‌دهد که احتمالاٌ درست هستند.
پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.

الگوریتم‌های دقیق
سرراست ترین راه حل امتحان کردن تمامی جایگشت‌های ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی n22n حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.

الگوریتم‌های مکاشفه‌ای
الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که می‌توان آنها را به صورت زیر دسته‌بندی کرد:
مکاشفه‌ای سازنده
بهبود تکراری
مبادله دوبه‌دو
مکاشفه‌ای k-opt
مکاشفه‌ای V-opt
بهبود تصادفی
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
*sepid* (۰۵-۱۳-۱۳۹۱), ali_85 (۰۳-۲۷-۱۳۹۱), e-eng (۱۱-۷-۱۳۸۹), elit (۰۶-۷-۱۳۹۱), green_Dream (۱۲-۶-۱۳۸۸), h.jaza (۱۰-۲۵-۱۳۸۸), intell23 (۰۷-۲۵-۱۳۹۲), lesanalgeib (۰۵-۲۳-۱۳۹۳), mav (۰۵-۱-۱۳۹۲), minoo007 (۰۳-۱۰-۱۳۹۱), mitrashooshtari (۰۲-۲۶-۱۳۹۱), nafise 2 (۰۳-۱۰-۱۳۹۱), r3d.w0rm (۰۶-۸-۱۳۹۲), raika (۰۵-۲۰-۱۳۹۱), sabora (۱۱-۷-۱۳۹۱), saeedeh23 (۰۳-۳-۱۳۹۱), samane_89 (۰۲-۲۵-۱۳۹۰), shima mechanic (۰۲-۱۳-۱۳۹۵), snowy_ night (۱۲-۲۵-۱۳۸۸), Solsal (۰۵-۱-۱۳۹۰), susaaan (۰۸-۲۹-۱۳۹۰), مهسا ج (۰۴-۳-۱۳۹۴), Violet_kia2 (۰۲-۶-۱۳۹۰)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۰۹-۳-۱۳۸۸, ۱۲:۵۶ بعد از ظهر   #2 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,307 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Arrow

ابتدا سايتهايي که کدهاي حل اين مسئله را از روش هاي متفاوت و زبانهاي مختلف ارائه کرده اند:



Source Code Library: Travelling Salesman Problem (TSP

Solving Travelling Salesman Problems Using Genetic Algorithms


Solution to Travelling Salesman Problem

Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
*sepid* (۰۵-۱۳-۱۳۹۱), ali_85 (۰۳-۲۷-۱۳۹۱), e-eng (۱۱-۷-۱۳۸۹), h.jaza (۱۰-۲۵-۱۳۸۸), intell23 (۰۷-۲۵-۱۳۹۲), m@r@l (۰۲-۱۰-۱۳۹۳), mav (۰۵-۱-۱۳۹۲), mitrashooshtari (۰۲-۲۶-۱۳۹۱), saeedeh23 (۰۳-۳-۱۳۹۱), snowy_ night (۱۲-۲۵-۱۳۸۸), Solsal (۰۵-۱-۱۳۹۰), susaaan (۰۸-۲۹-۱۳۹۰)
قديمي ۰۹-۳-۱۳۸۸, ۰۲:۴۶ بعد از ظهر   #3 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,307 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Smile

روش ابتکاری ساخت و بهبود تور مسئله فروشنده دوره گرد نامتقارن
فايل ضميمه
نوع فايل: pdf 52613859810.pdf (319.5 كيلو بايت, 3426 نمايش)
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
*sepid* (۰۵-۱۳-۱۳۹۱), arameshn (۱۲-۹-۱۳۸۹), mav (۰۵-۱-۱۳۹۲), mitrashooshtari (۰۲-۲۶-۱۳۹۱), PATRIOTE SAMURAI (۱۰-۱۴-۱۳۹۰), saeedeh23 (۰۳-۳-۱۳۹۱), snowy_ night (۱۲-۲۵-۱۳۸۸), Solsal (۰۵-۱-۱۳۹۰), susaaan (۰۸-۲۹-۱۳۹۰)
قديمي ۰۹-۴-۱۳۸۸, ۱۰:۱۰ قبل از ظهر   #4 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,307 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Lightbulb

کد حل مساله فروشنده دوره گرد با الگوريتم ژنتيک
فايل ضميمه
نوع فايل: zip TSP.zip (1.8 كيلو بايت, 2859 نمايش)
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
*sepid* (۰۵-۱۳-۱۳۹۱), alirezakia (۰۴-۱۹-۱۳۹۰), arameshn (۱۲-۹-۱۳۸۹), firethumbs (۱۰-۳-۱۳۹۲), free bird (۰۳-۱۲-۱۳۹۰), green_Dream (۱۲-۱۸-۱۳۸۸), hosna83 (۰۸-۱۸-۱۳۸۹), mav (۰۵-۱-۱۳۹۲), mitrashooshtari (۰۲-۲۶-۱۳۹۱), mnarx (۰۹-۷-۱۳۸۹), pampam (۱۰-۳-۱۳۸۸), saeedeh23 (۰۳-۳-۱۳۹۱), samane_89 (۰۴-۹-۱۳۹۰), shahriar0111 (۱۲-۱۶-۱۳۹۴), snowy_ night (۱۲-۲۵-۱۳۸۸), Solsal (۰۵-۱-۱۳۹۰), susaaan (۰۸-۲۹-۱۳۹۰)
قديمي ۰۹-۱۴-۱۳۸۸, ۰۴:۳۰ بعد از ظهر   #5 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,307 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

حل مسئله فروشنده دوره گرد (TSP) با شبکه هاپفیلد
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
*sepid* (۰۵-۱۳-۱۳۹۱), alirezakia (۰۴-۱۹-۱۳۹۰), ali_85 (۰۳-۲۷-۱۳۹۱), firethumbs (۱۰-۳-۱۳۹۲), mitrashooshtari (۰۲-۲۶-۱۳۹۱), saeedeh23 (۰۳-۳-۱۳۹۱), shahriar0111 (۱۲-۱۶-۱۳۹۴), snowy_ night (۱۲-۲۵-۱۳۸۸), Solsal (۰۵-۱-۱۳۹۰), susaaan (۰۸-۲۹-۱۳۹۰)
قديمي ۰۹-۱۷-۱۳۸۸, ۰۲:۰۷ بعد از ظهر   #6 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,307 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Cool برنامه tsp


و اين هم توضيحات کامل و برنامه همراه سورس سي پلاس پلاس
فايل ضميمه
نوع فايل: zip TSP[1].zip (67.1 كيلو بايت, 3312 نمايش)
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
*sepid* (۰۵-۱۳-۱۳۹۱), alirezakia (۰۴-۱۹-۱۳۹۰), arezoooo (۰۴-۱۱-۱۳۹۱), elit (۰۶-۷-۱۳۹۱), firethumbs (۱۰-۳-۱۳۹۲), free bird (۰۳-۱۲-۱۳۹۰), hafez11 (۰۹-۱۳-۱۳۹۲), ict69 (۰۷-۲۵-۱۳۸۹), lesanalgeib (۰۵-۱۸-۱۳۹۳), m@r@l (۰۲-۱۰-۱۳۹۳), minoo007 (۰۳-۱۰-۱۳۹۱), mitrashooshtari (۰۲-۲۶-۱۳۹۱), sabora (۱۱-۷-۱۳۹۱), saeedeh23 (۰۳-۳-۱۳۹۱), seda (۰۵-۱۳-۱۳۹۱), snowy_ night (۱۲-۲۵-۱۳۸۸), Solsal (۰۵-۱-۱۳۹۰), susaaan (۰۸-۲۹-۱۳۹۰)
قديمي ۱۰-۲۵-۱۳۸۸, ۰۵:۴۱ بعد از ظهر   #7 (لینک دائم)
عضو جدید
 
آواتار h.jaza
 
تاريخ عضويت: دي ۱۳۸۸
پست ها: 1
تشكرها: 4
5 تشكر در 1 پست
My Mood: Khoshhal
پيش فرض

حل TSP با Genetic Algorithms در #C
و روش حل با Simulated Annealing
h.jaza آفلاين است   پاسخ با نقل قول
از h.jaza تشكر كرده اند:
*sepid* (۰۵-۱۳-۱۳۹۱), mardin200 (۱۰-۲۵-۱۳۸۸), mohammadmono (۰۱-۲۹-۱۳۹۰), snowy_ night (۱۲-۲۵-۱۳۸۸), Solsal (۰۵-۱-۱۳۹۰)
قديمي ۰۱-۱۷-۱۳۸۹, ۰۸:۱۲ بعد از ظهر   #8 (لینک دائم)
عضو جدید
 
آواتار bagheri
 
تاريخ عضويت: اسفند ۱۳۸۸
پست ها: 3
تشكرها: 0
1 تشكر در 1 پست
پيش فرض

با سلام خدمت شما دوست عزیز وتشکر از پست مفیدتون
اگر امکان دارد در مورد تابع ابتکاری برای حل این مساله فروشنده دورگرد توضیح دهید
منظورم اینه که تابع ابتکاری این مساله چیه (در روش ژنتیک)
bagheri آفلاين است   پاسخ با نقل قول
قديمي ۰۳-۱۴-۱۳۸۹, ۰۳:۳۱ بعد از ظهر   #9 (لینک دائم)
عضو جدید
 
آواتار arghavan345
 
تاريخ عضويت: اسفند ۱۳۸۸
پست ها: 3
تشكرها: 1
0 تشكر در 0 پست
Question

با سلام
حل مسئله تی اس پی رو با زبان سی ++ و به روش الگوریتم ژنتیک می خواستم
با تشکر
arghavan345 آفلاين است   پاسخ با نقل قول
قديمي ۰۴-۸-۱۳۸۹, ۰۳:۱۲ بعد از ظهر   #10 (لینک دائم)
عضو جدید
 
آواتار amir-shakh
 
تاريخ عضويت: بهمن ۱۳۸۸
پست ها: 6
تشكرها: 0
3 تشكر در 3 پست
پيش فرض

سلام
اگر امکان دارد من را در مورد پیاده سازی مسئله فروشنده دوره گرد به کمک الگوریتم RBFS راهنمایی کنید و یا در صورت امکان اگه کدی در این مورد به هر زبانی داشتید برای من در این قسمت بگذارید و در مورد روشهای gentic algoritm و simulated annearling اگه میشه کد و راه حلی بزارید برای فروشنده دوره گرد
amir-shakh آفلاين است   پاسخ با نقل قول
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 
ابزارهاي تاپيک
نحوه نمايش

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۶:۲۸ بعد از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

استفاده از مطالب انجمن در سایر سایت ها، تنها با ذکر انجمن هوش مصنوعي به عنوان منبع و لینک مستقیم به خود مطلب مجاز است

Inactive Reminders By Icora Web Design