تخفیف نوروزی پی استور
هزینه سفارش:
۲۶۹,۰۰۰ تومان قیمت اصلی: ۲۶۹,۰۰۰ تومان بود.۱۰۷,۶۰۰ تومانقیمت فعلی: ۱۰۷,۶۰۰ تومان.
در این بخش حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون قرار داده شده است. مسئله فروشنده دوره گرد از جمله مسائل ریاضیات میباشد که قابل حل به روشهای مختلفی است. اما از جمله مهمترین روشهایی که میتوان با استفاده از آن مسائل بهینه سازی نظیر مسئله فروشنده دوره گرد یا Travelling salesman problem که به اختصار TSP نامیده میشود را حل نمود، الگوریتم های فرا ابتکاری یا متاهیورستیک است. الگوریتم شبیه سازی تبرید یا SA یکی از الگوریتمهای متاهیورستیک است که با استفاده از آن میتوان مسئله فروشنده دوره گرد را حل نمود. در ادامه درمورد حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون بیشتر صحبت خواهیم کرد.
پیش از این که بخواهیم به موضوع حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون بپردازیم، بیایید ببینیم مسئله فروشنده دوره گرد چیست؟ مسئله فروشنده دوره گرد یکی از مسائل مهم در زمینه بهینه سازی و علوم کامپیوتر محسوب میشود که این مسئله را با روشهای مختلفی میتوان پیاده سازی و حل نمود. تاریخچه پیدایش این مسئله مشخص نیست اما بهطور کلی این مسئله برای اولین بار در کتابهای ریاضیات پیدا شده است.
مسئله فروشنده دوره گرد بدین صورت است که تعدادی شهر داریم که هزینه گذر از هر شهر را نیز میدانیم. با این حساب فروشنده دوره گرد بایستی به تمامی این شهرها برود و از آنها گذر کند تا به عنوان مثال کالاهای خود را به فروش برساند. در نهایت این فروشنده بایستی به شهر اول بازگردد، اما نکته حائز توجه اینجاست که فروشنده دوره گرد به نوعی مسیرها را انتخاب کند که کمترین هزینه را برای وی داشته باشد.
در عین حال فروشنده دوره گرد باید یک بار از هر شهر عبور کند و همزمان با کمترین هزینه، کمترین مسافت را نیز طی کند.
در علم مواد، بازپخت یا Annealing، تبرید (باز پخت) یک فرآیند فیزیکی است که برای سخت شدن فلزات، شیشه و غیره استفاده شده که با درجه حرارت بالا شروع میشود و به آرامی سرد میشود. بهعنوان مثال دمای شیشه را به آرامی پایین میآورند تا در هر دما اتمها بتوانند به اندازه کافی حرکت کنند تا پایدارترین جهت را به خود بگیرند. در واقع دما تعیین میکند که اتمها چقدر تحرک داشته باشند.
در علوم کامپیوتری برای پیدا کردن بهترین راه حل از بیت تعداد زیادی راه حلهای ممکن را بهینه سازی مسائل میگویند. در بعضی از این مسائل بهینه سازی به خطر وجود زیاد اشیا، امکان مدیریت وجود ندارد. مسئله فروشنده دوره گرد یکی از این مسئله هاست.
این روش به طور مستقل توسط اسکات کرک پاتریک، سی دانیل ژلات و ماریو پی وکی در سال ۱۹۸۳ و توسط ولادو سرنو در سال ۱۹۸۵ توصیف شد. SA احتمالاً پرکاربردترین روش فرااکتشافی در مسئله بهینه سازی ترکیبی است. این انگیزه با تشابه بین بازپخت فیزیکی فلزات و روند جستجو برای راه حل بهینه در مسئله بهینه سازی ترکیبی بدست آمده است. هدف اصلی روش SA فرار از بهینههای محلی و به تأخیر انداختن همگرایی است.
زبان برنامه نویسی پایتون یکی از زبانهای مهم در حوزه حل مسائل بهینه سازی است که با توجه به توابع و کتابخانههای آمادهای که دارد، قابلیت رقابت با زبان برنامه نویسی مانند متلب را داراست. این زبان برنامه نویسی قدرت بالایی دارد و به دلایل متعددی از جمله چند سکویی بودن توسط کاربران زیادی در سراسر دنیا استفاده میشود. در اینجا نیز الگوریتم SA برای حل مسئله فروشنده دوره گرد در زبان برنامه نویسی پایتون پیاده سازی شده است.
مسئله فروشنده دوره گرد یا TSP قابل حل با الگوریتمهای فرا ابتکاری میباشد که یکی از آنها الگوریتم تبرید شبیه سازی شده میباشد. این سورس کد دارای ۱ فایل اصلی SA.py است که در برگیرنده کدهای اصلی و فراخوانیها است. در یک پوشه به نام data نیز مقادیر و هزینههای شهرها در داخل فایلهای txt قرار گرفتهاند که در خط زیر میتوانید نام داده مدنظر خود را وارد کنید.
with open('./data/chn14.txt') as f:
برای مثال در این مورد فایل chn14.txt مدنظر قرار داده شده است. جهت مشاهده خروجی برنامه به ادامه توضیحات اثر مراجعه نمایید. بخشی از سورس کد در زیر آورده شده است.
import random as rd import numpy as np import matplotlib.pyplot as plt #__ City Class class City: def __init__(self,num, x, y): self.num=num self.x = x self.y = y def distance(self, city): xDis = abs(self.x - city.x) yDis = abs(self.y - city.y) distance = np.sqrt((xDis ** 2) + (yDis ** 2)) return distance def __repr__(self): return "(" + str(self.x) + "," + str(self.y) + ")"
قبل از اجرای سورس کد الگوریتم در محیط پایتون حتماً از نصب پکیجهای مورد استفاده در این سورس کد در Python خود مطمئن شوید پکیجهای استفاده شده در این سورس کد numpy و matplotlib است که اولی پکیج مربوط به استفاده از آرایهها و ماتریسها در پایتون و دومی مربوط به عملیاتهای نموداری و Plot گرفتن میباشد. پیشنهاد ما نصب اسپایدر (Spyder (Python 3.7 است که هم پایتون و پکیجهای مختلف و هم IDE های مختلفی را همراه با امکان آپدیتشان نصب میکند.
سورس کد حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون عنوان اثری است که در این پست به آن پرداخته شده است. این اثر در پایتون ۳.۱۰ برنامه نویسی شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است.
تیم برنامه نویسی پی استور یکی از اولین گروههای تشکیل شده در مجموعه آموزشی پی استور میباشد. این تیم از اساتید مجرب و فارغ التحصیلان رشتههای فنی و مهندسی تشکیل شده که در زمینههای مختلف برنامهنویسی و تهیه سورس کد فعال هستند.
نام اثر: | حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون |
نوع اثر: | سورس کد |
برنامهنویس: | تیم برنامهنویسی پیاستور |
زبان برنامه نویسی: | پایتون |
ویژگی: | دارای قابلیت ویرایش و اعمال انواع تغییرات |
توجه: کیفیت این محصول توسط پی استور تضمین شده و در صورت عدم رضایت از محصول، به انتخاب شما:
هزینه سفارش:
۲۶۹,۰۰۰ تومان قیمت اصلی: ۲۶۹,۰۰۰ تومان بود.۱۰۷,۶۰۰ تومانقیمت فعلی: ۱۰۷,۶۰۰ تومان.
نظرات
فاطمه اسماعیلی
نظرات و دیدگاه های خود را با ما درمیان بگذارید.