CODEWITHSUNDEEP
algorithmdynamic-programming
ArCh3r
ArCh3r

Reputation: 89

Algorithm for selecting closest pairs using Dynamic Programming

I have been trying to solve this problem my professor has given me but couldn't make a proper solution. The following is the problem

Problem: A rectangular circuit board has two parallel sides with width W between them. There are m terminals on the upper side of the board and n terminals (n < m) on the lower side. Let U1 < U[2] < … < U[m] be the distances from the left end of the board to the m terminals on the upper side, respectively. Let L1 < L[2] < … < L[n] be the distances from the left end of the board to the n terminals on the lower side, respectively. Now, we need to select n terminals from the m terminals on the upper side to be connected to the n terminals on the lower side by n straight line segments, respectively, such that the total length of the n line segments is minimized. The following figure illustrates the problem for m = 8 and n = 4.

Example

(a) Prove that, in an optimal solution, any two line segments will not intersect.

(b) Design an O(mn) dynamic programming algorithm to solve this minimization problem. You need to define sub-problems, show the inductive formula, initial conditions, and a pseudocode. You can use d(i, j) to denote the distance between U[i] and L[j], 1 ≤ i ≤ m, 1 ≤ j ≤ n. (The calculation of d(i, j) = ) can be omitted.

My Approach:

For the above problem, my approach was first to make a matrix d(i,j) where i are the terminals on the bottom and j are the terminals on the top. d(i,j) has all the distances from any two circuits.Then iterating through each row I will find the smallest distance and mark the respective terminal. But I am not sure this would work if the top circuits are all to the extreme right of the side. So can anyone provide me with a better approach.

Upvotes: 4

Views: 1102

Answers (1)

uSeemSurprised
uSeemSurprised

Reputation: 1834

I have written a recursive Dynamic Programming solution that uses memoisation, the complexity is O(mn), here at each recursive level we can either choose to join the current point defined in the U[] array with the point defined in the L[] array, or we can move forward without doing so:

#include<iostream>
#define INF 1e9

using namespace std;

int n, m, d[100][100], dp[100][100];

int solve(int idx1, int idx2){
    if(idx1 > m){
        if(idx2 < n) return INF;
        else return 0;
    }
    if(idx2 > n) return 0;
    if(dp[idx1][idx2] != -1) return dp[idx1][idx2];

    int v1, v2;

    //include current
    v1 = solve(idx1 + 1, idx2 + 1) + d[idx1][idx2];

    //do not include current
    v2 = solve(idx1 + 1, idx2);

    return dp[idx1][idx2] = min(v1, v2);
}

int main(){

    //enter the the distances

    for(int i = 0;i < 100;i++) for(int j = 0;j < 100;j++) dp[i][j] = -1;
    cout << solve(1, 1) << endl;
    return 0;
}

For the part (a) of your question, let us assume that 2 line segments do intersect, then we cannot have an optimal solution because if we just swapped the 2 end points of the line segments defined by the L[] array then the distance would reduce, hence giving us a better solution.

Upvotes: 1

Related Questions