CS2004_Applications_TSP_BinPacking_Clustering_Flashcards
(11 cards)
What is the Travelling Salesperson Problem (TSP)?
TSP asks for the shortest possible tour that visits each city exactly once and returns to the starting point.
✅ It is NP-Complete and commonly used in routing problems.
How is a TSP solution represented?
As a list or array of city indices indicating the order of visits.
✅ Example: [0, 2, 3, 1] means visit city 0, then 2, then 3, then 1.
What is the fitness function for TSP?
The fitness is the total length of the tour. Shorter tours have better fitness.
What is the small change operator for RMHC in TSP?
Swapping two cities in the tour to create a neighbour solution.
What is Bin Packing?
Bin Packing is an optimisation problem where the goal is to pack items into the fewest number of fixed-capacity bins.
What is the First-Fit Decreasing (FFD) algorithm?
FFD sorts items in decreasing order and places each into the first bin it fits in. If none fit, a new bin is opened.
Give a real-world example of Bin Packing.
Fitting files onto DVDs, loading boxes into shipping containers.
What is Data Clustering?
Clustering is the task of grouping similar data points into clusters based on similarity or distance.
What is K-Means Clustering?
An algorithm that partitions data into k clusters by assigning each point to the nearest centroid, then updating centroids iteratively.
How is clustering quality evaluated?
Using metrics like intra-cluster distance (compactness) and inter-cluster separation (separation).
What is a 1D cluster vector representation?
An array where each index represents a data point and the value indicates its assigned cluster.
✅ Example: [1, 2, 1, 3] means point 0 is in cluster 1, point 1 in cluster 2, etc.
