TSP Monte Carlo

Membangkitkan Bilangan Acak Menggunakan Matlab

Traveling Salesman Problem

•Traveling Salesman Problem (TSP) adalahsuatupermasalahandimanaseorangsales harusmelaluisemuakotayang ditunjukdenganjarakyang paling pendekdansetiapkotahanyabolehdilaluisatukali.

•PenyelesaiandalamTSP adalahjaluryang dilaluiolehsalesman sesuaidenganbatasandiatas. Penyelesaianterbaikadalahjalurdenganjarakterpendek.

•TSP adalahsalahsatucontohpermasalahankombinatorialdengankemungkinanpenyelesaianyang sangatbanyak.

TSP dengan3 kota

•TSP dengan3 kota(1,2,3) hanyamempunyaisatukemungkinansepertigambardibawahini.

•TSP dengan3 kotatidakperludiselesaikanmenggunakankomputer

123

TSP dengan4 kota•TSP dengan4 kota(1,2,3,4) hanyamempunyai3 kemungkinansepertigambardibawahini.•TSP dengan4 kotatidakperludiselesaikanmenggunakankomputer123412341234

TSP dengan5 kota•TSP dengan4 kota(1,2,3,4,5) hanyamempunyai12 kemungkinansepertigambardibawahini.•TSP dengan5 kotamulaiperludiselesaikanmenggunakankomputer. Teknikyang dipakaibisaberupamencobasemuakemungkinandandibandingkanjaraknyauntukmemperolehjarakpaling pendek123451234512345. . .

TSP dengann kota

•TSP dengann kota(1,2,3,4,5,…,n) mempunyai

(n-1)!/2 kemungkinan.

•TSP dengan15 kotamempunyai14!/2 atau4.3589.1010kemungkinan. Metodepencariansatu-satumemerlukanwaktuyang sangatlama.

•TSP dengan20 kotamempunyai19!/2 atau6.08 1016kemungkinan, suatujumlahyang sangatbesar. Denganmenganggapbahwakomputermampumenyelesaikan1 Giga (109) prosesper-detikmakauntukmencarisemuasolusidiperlukan6.08 107detikatau1.69.104jam atau704 hari. Waktuyang sangatlama.

•BagaimanabilaTSP dengan30,40,50 atau100 kota?

PenyelesaianTSP

DenganMonte Carlo

•PenyelesaianTSP adalahjaluryang melewatisemuakotadansetiapkotahanyadilaluisatukali, halinidapatdinyatakansebagaikombinasiurutannomorkota, misalkanuntukTSP 6 kota: 1-2-3-4-5-6

•Penyelesaiandicarisecaraacakmisalkan: 3-2-5-1-6-4, kemudiandihitungtotal jaraksetiapjaluryang dipilih.

•Untukmencaripenyelesaianyang baru, dilakukanprosesupdate denganmengubahurutandaribeberapatitiksaja(tidakperlusemuatitik).

•Prosespencarianjalurdilakukansecaraberulang-ulanghinggadiperolehjalurdenganjarakterpendek.

Flowchart PenyelesaianTSP MenggunakanMonte CarloMulaiMasukkanjumlahkota(n)Bangkitkanjalursecaraurut1-2-3-…-n, nyatakansebagaiSminBaca data posisin kotaHitungjarak(Emin)11Update Solusidenganmemilih2 posisip1 danp2, kemudianurutanSp1–Sp2dibalikmenjadiSp2-Sp1. NyatakansebagaiS.Hitungjarak(E)E < EminSmin􀃅SEmin􀃅EStop Kriteria?yatidakSelesaiSolusioptimum Sminya1tidak

Flowchart PenyelesaianTSP MenggunakanMonte Carlo

#include <fstream.h>

#include <stdlib.h>

#include <math.h>

intx[100],y[100];

float HitungJarak(intS[100],int n)

{

float d,dx,dy;

inti;

d=0;

for(i=0;i<n-1;i++){

dx=pow(x[S[i]]-x[S[i+1]],2);

dy=pow(y[S[i]]-y[S[i+1]],2);

d+=sqrt(dx+dy);

}

dx=pow(x[S[0]]-x[S[n-1]],2);

dy=pow(y[S[0]]-y[S[n-1]],2);

d+=sqrt(dx+dy);

return d;

}

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s


%d blogger menyukai ini: