Skip to main content
SUPERVISOR
Ramin Gavadi jourtani
رامین جوادی جورتانی (استاد راهنما)
 
STUDENT
Shamisa Nematollahi
شمیسا نعمت الهی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1394

TITLE

Approximation Algorithms for the Traveling Salesman Problem
The traveling salesman problem(TSP) is one of the m most important combinatorial optimization problems. The salesman wants to visit some cities and he wants to visit t each city exactly once and return to the beginning city. minimize the total cost of the trip. At first one may to express the equivalence of the problem in graph theory , we are given a complete graph and the cost function such that each vertex represents a city and t he cost function c specifies the cost of going from each city to another one. The goal is to find a minimum cost tour that visits every vertex exactly once, i.e. a Hamiltonian cycle with minimum total cost.
مسأله فروشنده دوره‌گرد یکی از بنیادی‌ترین مسائل بهینه‌سازی است. فروشنده دوره‌گرد قصد دارد به تعدادی شهر سفر کند ، به‌طوری که از هر شهر دقیقاً یک بار عبور کند و همچنین هزینه سفر کمینه شود. در این پایان‌نامه ابتدا معادل مسأله را در نظریه گراف بیان می‌کنیم و حالت‌های مختلف مسأله را تعریف می‌کنیم ، که مهم‌ترین آن‌ها ، مسأله در حالت ‌های متقارن و نامتقارن است. سپس به بررسی پیچیدگی محاسباتی مسأله می‌پردازیم و از آنجایی که مسأله -کامل است ، به سراغ الگوریتم‌های تقریبی می‌رویم و بهترین الگوریتم‌های تقریبی موجود برای مسأله در حالت‌های مختلف را بررسی می‌کنیم. نهایتاً به مفهوم درخت نازک و ارتباط آن با وجود الگوریتم تقریبی برای مسأله در حالت نامتقارن می‌پردازیم

ارتقاء امنیت وب با وف بومی