تخفیف نوروزی پی استور

کد تخفیف: PR1404

شامل تمامی آثار
روز
ساعت
دقیقه
ثانیه

با خرید اشتراک ویژه ، با هزینه بسیار کمتر به فایل های پاورپوینت دسترسی داشته باشید!

حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون

هزینه سفارش:

تخفیف ویژه 60 درصدی

قیمت اصلی: ۲۶۹,۰۰۰ تومان بود.قیمت فعلی: ۱۰۷,۶۰۰ تومان.

روز
ساعت
دقیقه
ثانیه
دریافت کد تخفیف با گردونه شانس %
تعداد فراگیر
198 نفر
امتیاز کاربران
امتیاز 5.00 از 5

در این بخش حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون قرار داده شده است. مسئله فروشنده دوره گرد از جمله مسائل ریاضیات می‌باشد که قابل حل به روش‌های مختلفی است. اما از جمله مهم‌ترین روش‌هایی که می‌توان با استفاده از آن مسائل بهینه سازی نظیر مسئله فروشنده دوره گرد یا Travelling salesman problem که به اختصار TSP نامیده می‌شود را حل نمود، الگوریتم های فرا ابتکاری یا متاهیورستیک است. الگوریتم شبیه سازی تبرید یا SA یکی از الگوریتم‌های متاهیورستیک است که با استفاده از آن می‌توان مسئله فروشنده دوره گرد را حل نمود. در ادامه درمورد حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون بیشتر صحبت خواهیم کرد.

شرح مسئله فروشنده دوره گرد

پیش از این که بخواهیم به موضوع حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون بپردازیم، بیایید ببینیم مسئله فروشنده دوره گرد چیست؟ مسئله فروشنده دوره گرد یکی از مسائل مهم در زمینه بهینه سازی و علوم کامپیوتر محسوب می‌شود که این مسئله را با روش‌های مختلفی می‌توان پیاده سازی و حل نمود. تاریخچه پیدایش این مسئله مشخص نیست اما به‌طور کلی این مسئله برای اولین بار در کتاب‌های ریاضیات پیدا شده است.

مسئله فروشنده دوره گرد بدین صورت است که تعدادی شهر داریم که هزینه گذر از هر شهر را نیز می‌دانیم. با این حساب فروشنده دوره گرد بایستی به تمامی این شهرها برود و از آن‌ها گذر کند تا به عنوان مثال کالاهای خود را به فروش برساند. در نهایت این فروشنده بایستی به شهر اول بازگردد، اما نکته حائز توجه اینجاست که فروشنده دوره گرد به نوعی مسیرها را انتخاب کند که کم‌ترین هزینه را برای وی داشته باشد.

در عین حال فروشنده دوره گرد باید یک بار از هر شهر عبور کند و همزمان با کم‌ترین هزینه، کمترین مسافت را نیز طی کند.

الگوریتم تبرید شبیه سازی شده یا Simulated annealing

در علم مواد، بازپخت یا Annealing، تبرید (باز پخت) یک فرآیند فیزیکی است که برای سخت شدن فلزات، شیشه و غیره استفاده شده که با درجه حرارت بالا شروع می‌شود و به آرامی سرد می‌شود. به‌عنوان مثال دمای شیشه را به آرامی پایین می‌آورند تا در هر دما اتم‌ها بتوانند به اندازه کافی حرکت کنند تا پایدارترین جهت را به خود بگیرند. در واقع دما تعیین می‌کند که اتم‌ها چقدر تحرک داشته باشند.

در علوم کامپیوتری برای پیدا کردن بهترین راه حل از بیت تعداد زیادی راه حل‌های ممکن را بهینه سازی مسائل می‌گویند. در بعضی از این مسائل بهینه سازی به خطر وجود زیاد اشیا، امکان مدیریت وجود ندارد. مسئله فروشنده دوره گرد یکی از این مسئله هاست.

این روش به طور مستقل توسط اسکات کرک پاتریک، سی دانیل ژلات و ماریو پی وکی در سال ۱۹۸۳ و توسط ولادو سرنو در سال ۱۹۸۵ توصیف شد. SA احتمالاً پرکاربردترین روش فرااکتشافی در مسئله بهینه سازی ترکیبی است. این انگیزه با تشابه بین بازپخت فیزیکی فلزات و روند جستجو برای راه حل بهینه در مسئله بهینه سازی ترکیبی بدست آمده است. هدف اصلی روش 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) + ")"

تصاویر خروجی حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون

نحوه پیمایش شهرها در حل مسئله فروشنده دوره گرد با الگوریتم تبرید شبیه سازی شده
نحوه پیمایش شهرها در حل مسئله فروشنده دوره گرد با الگوریتم تبرید شبیه سازی شده
نمودار همگرایی حل مسئله فروشنده دوره گرد با الگوریتم تبرید شبیه سازی شده
نمودار همگرایی حل مسئله فروشنده دوره گرد با الگوریتم تبرید شبیه سازی شده

***  توجه  ***

قبل از اجرای سورس کد الگوریتم در محیط پایتون حتماً از نصب پکیج‌های مورد استفاده در این سورس کد در Python خود مطمئن شوید پکیج‌های استفاده شده در این سورس کد numpy و matplotlib است که اولی پکیج مربوط به استفاده از آرایه‌ها و ماتریس‌ها در پایتون و دومی مربوط به عملیات‌های نموداری و Plot گرفتن می‌باشد. پیشنهاد ما نصب اسپایدر (Spyder (Python 3.7 است که هم پایتون و پکیج‌های مختلف و هم IDE های مختلفی را همراه با امکان آپدیتشان نصب می‌کند.


درباره سورس کد حل مسئله فروشنده دوره گرد با الگوریتم SA

سورس کد حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون عنوان اثری است که در این پست به آن پرداخته شده است. این اثر در پایتون ۳.۱۰ برنامه نویسی شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است.

مشاهده بیشتر

ویدئوی معرفی اثر

نحوه اجرای سورس کد


برنامه‌نویس:  تیم برنامه‌نویسی پی‌استور

متشکل از اساتید و فارغ التحصیلان رشته‌های فنی - مهندسی

تیم برنامه نویسی پی استور یکی از اولین گروه‌های تشکیل شده در مجموعه آموزشی پی استور می‌باشد. این تیم از اساتید مجرب و فارغ التحصیلان رشته‌های فنی و مهندسی تشکیل شده که در زمینه‌های مختلف برنامه‌نویسی و تهیه سورس کد فعال هستند.

مشخصات تکمیلی سورس کد

نام اثر: حل مسئله فروشنده دوره گرد با الگوریتم SA در پایتون
نوع اثر: سورس کد
برنامه‌نویس: تیم برنامه‌نویسی پی‌استور
زبان برنامه نویسی: پایتون
ویژگی: دارای قابلیت ویرایش و اعمال انواع تغییرات

راهنمای خرید و ثبت سفارش

تصویر مراحل خرید از پی استور

اگر در مورد این اثر یا نحوه تهیه آن سوالی دارید؟
  • با شماره تلفن واحد مخاطبین 44225175 (پیش شماره 041) تماس بگیرید. – تمام ساعات اداری
  • با ما مکاتبه ایمیلی داشته باشید (این لینک). – تمام ساعات

توجه: کیفیت این محصول توسط پی استور تضمین شده و در صورت عدم رضایت از محصول، به انتخاب شما:

تصویر و لوگوی گارانتی

نظرات

1 نظر|5.00 (میانگین امتیاز کاربران)

  1. آواتار فاطمه اسماعیلی

    فاطمه اسماعیلی

    نظرات و دیدگاه های خود را با ما درمیان بگذارید.

دیدگاه خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

هزینه سفارش:

تخفیف ویژه 60 درصدی

قیمت اصلی: ۲۶۹,۰۰۰ تومان بود.قیمت فعلی: ۱۰۷,۶۰۰ تومان.

دریافت کد تخفیف %