Traveling Salesperson Problem: TSP is a problem that tries to find a tour of minimum cost that visits every city exactly once. In this visualization, it is assumed that the underlying graph is a complete graph with (near-)metric distance (meaning the distance function satisfies the triangle inequality) by taking the distance of two points and round it to the nearest integer.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
View the visualisation of TSP algorithm here.
Originally, all edges in the input graph are colored grey.
Throughout the visualization, traversed edge will be highlighted with orange.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
Terdapat dua metode berbeda untuk menggambar graf masukan:
- Gambar Graf: Anda dapat meletakkan beberapa titik dalam kotak gambar, tetapi anda tidak boleh menggambar edge agar properti (hampir) metrik dari graf terpenuhi. Setelah anda selesai menggambar titik-titik, seluruh edge akan digambar secara otomatis.
- Graf Contoh: Anda dapat memilih dari daftar graf yang ada.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Visualisation Scale
Ubah Graf
Input Graph
Graf-Graf Contoh
Bruteforce
Pemrograman Dinamis
Penaksiran
Bitonic TSP
Local Search