MHB Question about Dynamic programming-Shortest Path Problem

[mathmari]

Given a set of n things (1,2,...,n), 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?
Since the problem is general, do I have to draw the first vertex, the last vertex, and some between them for example the vertex $i$ and $j$,and at the edge from $i$ to $j$ there is a cost $c_{ij}$??

 

[I like Serena]

Given a set of n things (1,2,...,n), 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?
Since the problem is general, do I have to draw the first vertex, the last vertex, and some between them for example the vertex $i$ and $j$,and at the edge from $i$ to $j$ there is a cost $c_{ij}$??

Things? What kind of things?
Marbles?
That's important!

Hmm, are you sure you're supposed to use a shortest path algorithm?
Seems to me it should be a minimal spanning tree (or forest).
I think that for a general problem you would need to specify an algorithm.

 

[mathmari]

Things? What kind of things?
Marbles?
That's important!

Hmm, are you sure you're supposed to use a shortest path algorithm?
Seems to me it should be a minimal spanning tree (or forest).
I think that for a general problem you would need to specify an algorithm.

At the first subquestion I have to write the problem as a shortest path problem, at the second subquestion I have to specify an algorithm, and at the third I have to apply this algorithm in a specific problem.

We could consider the problem as a system of nodes (0,...,n) and curves $ \text arc(i,j)$ with $j>i$. Each $ \text arc(i,j)$ with $i<n$ corresponds to a cluster of edges $i+1,i+2,...,j$, whose cost is $c_{ij}$, while $ \text arc(n,n)$ has cost $0$.

 

[mathmari]

What is meant by writing the problem as a shortest path problem?

 

[mathmari]

To understand the exericse, to find the grouping so that the total cost is minimal, do I have to find the shortest path? Or how can I find it? Could you give me an example because I'm really confused..

 

[I like Serena]

The problem statement for the shortest path problem is finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

In my opinion that really does not apply to your problem.
So I think it may be a typo.

 

[Evgeny.Makarov]

Given a set of n things (1,2,...,n), 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.

I assume $i$ and $j$ in $c_{ij}$ are indices of the first and last objects in a cluster; thus there is a $c_{ij}$ for each $1\le i\le j\le n$.

I suggest checking if the following idea works. Given a grouping problem, we construct a directed graph. The vertices are $1,\dots,n+1$. There is an edge from $i$ to $j$ iff $i<j$, and its weight is $c_{ij-1}$. Then the minimum grouping cost is the shortest distance between 1 and $n+1$.

 

[mathmari]

I assume $i$ and $j$ in $c_{ij}$ are indices of the first and last objects in a cluster; thus there is a $c_{ij}$ for each $1\le i\le j\le n$.

I suggest checking if the following idea works. Given a grouping problem, we construct a directed graph. The vertices are $1,\dots,n+1$. There is an edge from $i$ to $j$ iff $i<j$, and its weight is $c_{ij-1}$. Then the minimum grouping cost is the shortest distance between 1 and $n+1$.

Could you explain me why the weight for the edge from $i$ to $j$ iff $i<j$ is $c_{ij-1}$ ?
And also, why are the vertices denoted till $n+1$ ?

 

[Evgeny.Makarov]

Could you explain me why the weight for the edge from $i$ to $j$ iff $i<j$ is $c_{ij-1}$ ?

Are you wondering why the edge from $i$ to $j$ corresponds to $c_{ij-1}$ as opposed to $c_{ij}$? For one, a segment consisting of one object #$i$ makes sense and has a cost $c_{ii}$. On the other hand, a loop is never a part of the shortest path.

And also, why are the vertices denoted till $n+1$ ?

If you need to employ $c_{in}$ and, according to the reasoning above, the second index is the result of subtracting 1, then the last vertex should be $n+1$.

For each partitioning problem you get a direct graph. You should prove that there is a bijection between partitions and paths from 1 to $n+1$, and it maps cost to length. Then minimal length would correspond to minimal cost.

 

[mathmari]

Are you wondering why the edge from $i$ to $j$ corresponds to $c_{ij-1}$ as opposed to $c_{ij}$? For one, a segment consisting of one object #$i$ makes sense and has a cost $c_{ii}$. On the other hand, a loop is never a part of the shortest path.

If you need to employ $c_{in}$ and, according to the reasoning above, the second index is the result of subtracting 1, then the last vertex should be $n+1$.

For each partitioning problem you get a direct graph. You should prove that there is a bijection between partitions and paths from 1 to $n+1$, and it maps cost to length. Then minimal length would correspond to minimal cost.

For example for n=5, is the graph the following?

View attachment 1793

 

[mathmari]

You should prove that there is a bijection between partitions and paths from 1 to $n+1$, and it maps cost to length.

Could you give me a hint how to do this? I have not really understood the relation between the grouping problem and the shortest path problem..

 

[Evgeny.Makarov]

For example for n=5, is the graph the following?

Yes.

 

[mathmari]

Could you give me a hint how to do this? I have not really understood the relation between the grouping problem and the shortest path problem..

I got it now...your answers were helpful!