Traveling salesman problem

---

Revisi terkini pada 7 Mei 2012 15.19

Daftar isi 1 Sejarah 2 Definisi dan latar belakang 3 Penerapan 4 Solusi 4.1 Triangle inequality 4.2 Solusi umum 4.3 Aproksimasi menggunakan pendekatan Pohon Rentang Minimum 5 Pranala luar

Traveling Salesman Problem (TSP) adalah suatu masalah optimasi kombinatorial pada pokok bahasan teori graf di bidang ilmu Teknik Komputasi. TSP termasuk kedalam masalah NP-hard. TSP dikemukakan pertama kali oleh William Hamilton pada tahun 1930.

[sunting] Definisi dan latar belakang

Inti dari masalah dari TSP adalah, bagaimana membentuk Sirkuit Hamilton dari edges-edges yang ada dengan biaya se-minimal mungkin.

TSP dapat diterapkan untuk menyelesaikan masalah-masalah perencanaan, logistik, desain microchip, hingga penentuan urutan DNA (DNA Sequencing).

[sunting] Triangle inequality

[sunting] Solusi umum

[sunting] Aproksimasi menggunakan pendekatan Pohon Rentang Minimum

[sunting] Pranala luar

• bin Mohammad, Rashid, Traveling salesman Problem, http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/AproxAlgor/TSP/tsp.htm 

• Adleman, Leonard, Revision:The Travelling Salesman Problem, http://www.thestudentroom.co.uk/wiki/Revision:The_Travelling_Salesman_Problem 

• Hoffman, Karla, Traveling Salesman Problem, http://iris.gmu.edu/~khoffman/papers/trav_salesman.html 

180.253.241.117 07 May, 2012

-
Source: http://id.wikipedia.org/w/index.php?title=Traveling_salesman_problem&diff=5479171&oldid=0
--
Manage subscription | Powered by rssforward.com