Given a set of m things (1,2,...,m), we want to group them in clusters that contain adjacent things. For each cluster there is a cost $c_{ij}$. We are looking for the grouping in clusters so that the total cost is minimal. I am asked to write this problem as a shortest path problem. What do I have to do? Do I have to draw a directed weighted graph?
Asked
Active
Viewed 185 times
0
-
Do you have a target number of clusters? – Henry Dec 19 '13 at 17:21
-
are clusters just pairs? – mathemagician Dec 19 '13 at 17:22
-
@Henry: No,we don't have the target number of clusters.. – Mary Star Dec 19 '13 at 17:28
-
What is the indexing in $c_{ij}$ over?($i$ and $j$). And what is exactly a cluster? – Aman Dec 19 '13 at 17:29
-
@mathemagician: No,they are not just pairs.. – Mary Star Dec 19 '13 at 17:29
-
Almost certainly $c_{ij}$ is the cost of clustering the elements ${i, \ldots, j}$. – universalset Dec 19 '13 at 17:30
1 Answers
1
You need to describe a directed, weighted graph so that there is a correspondence between paths (between two particular vertices) and a particular choice of clusters, and so that the shortest path corresponds to the lowest-cost grouping; then you should demonstrate that this correspondence holds.
Hint: Make a graph with an edge from $i$ to $j$ with cost $c_{i(j-1)}$ for each pair $1\leq i<j\leq m+1$. Why does finding the shortest path from $1$ to $m+1$ solve your problem?
universalset
- 8,269
- 20
- 33