How would you look at developing an algorithm for this hotel problem?

Question

There is a problem I am working on for a programming course and I am having trouble developing an algorithm to suit the problem. Here it is:

You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < ... < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. You'd ideally like to travel 200 miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is (200 - x)^2. You want to plan your trip so as to minimize the total penalty that is, the sum, over all travel days, of the daily penalties. Give an efficient algorithm that determines the optimal sequence of hotels at which to stop.

So, my intuition tells me to start from the back, checking penalty values, then somehow match them going back the forward direction (resulting in an O(n^2) runtime, which is optimal enough for the situation).

Anyone see any possible way to make this idea work out or have any ideas on possible implmentations?

Answer 1

Here is my Python solution using Dynamic Programming:

distance = [150,180,250,340]

def hotelStop(distance):
    n = len(distance)
    DP = [0 for _ in distance]
    for i in range(n-2,-1,-1):
        min_penalty = float("inf")
        for j in range(i+1,n):
            # going from hotel i to j in first day
            x = distance[j]-distance[i]
            penalty = (200-x)**2
            total_pentalty = penalty+ DP[j]
            min_penalty = min(min_penalty,total_pentalty)
        DP[i] = min_penalty
    return DP[0]

hotelStop(distance)

Answer 2

As a proof of concept, here is my JavaScript solution in Dynamic Programming without nested loops.

1. We start at zero miles.

2. We find the next stop by keeping the penalty as low as we can by comparing the penalty of a current hotel in the loop to the previous hotel's penalty.

3. Once we have our current minimum, we have found our stop for the day. We assign this point as our next starting point.

4. Optionally, we could keep the total of the penalties:

let hotels = [40, 80, 90, 200, 250, 450, 680, 710, 720, 950, 1000, 1080, 1200, 1480]

function findOptimalPath(arr) {
    let start = 0
    let stops = []
    for (let i = 0; i < arr.length; i++) {
        if (Math.pow((start + 200) - arr[i-1], 2) < Math.pow((start + 200) - arr[i], 2)) {
        stops.push(arr[i-1])
        start = arr[i-1]
    }
  }
  console.log(stops)
}
findOptimalPath(hotels)

Answer 3

I have come across this problem recently and wanted to share my solution written in Javascript.

Not dissimilar to the most of the above solutions, I have used dynamic programming approach. To calculate penalties[i], we need to search for such stopping place for the previous day so that the penalty is minimum. penalties(i) = min_{j=0, 1, ... , i-1} ( penalties(j) + (200-(hotelList[i]-hotelList[j]))^2) The solution does not assume that the first penalty is Math.pow(200 - hotelList[1], 2). We don't know whether or not it is optimal to stop at the first top so this assumption should not be made. In order to find the optimal path and store all the stops along the way, the helper array path is being used. Finally, the array is being traversed backwards to calculate the finalPath.

function calculateOptimalRoute(hotelList) {
const path = [];
const penalties = [];

for (i = 0; i < hotelList.length; i++) {
    penalties[i] = Math.pow(200 - hotelList[i], 2)
    path[i] = 0
    for (j = 0; j < i; j++) {
        const temp = penalties[j] + Math.pow((200 - (hotelList[i] - hotelList[j])), 2)
        if (temp < penalties[i]) {
            penalties[i] = temp;
            path[i] = (j + 1);
        }

    }
}

const finalPath = [];
let index = path.length - 1

while (index >= 0) {
    finalPath.unshift(index + 1);
    index = path[index] - 1;
}
console.log('min penalty is ', penalties[hotelList.length - 1])
console.log('final path is ', finalPath)

return finalPath;

}

// calculateOptimalRoute([20, 40, 60, 940, 1500])
// Outputs [3, 4, 5]

// calculateOptimalRoute([190, 420, 550, 660, 670])
// Outputs [1, 2, 5]

// calculateOptimalRoute([200, 400, 600, 601])
// Outputs [1, 2, 4]

// calculateOptimalRoute([])
// Outputs []

Answer 4

Step 1 of 2

Sub-problem:

In this scenario, "C(j)" has been considered as sub-problem for minimum penalty gained up to the hotel "ai" when "0<=i<=n". The required value for the problem is "C(n)".

Algorithm to find minimum total penalty:

If the trip is stopped at the location "aj" then the previous stop will be "ai" and the value of i and should be less than j. Then all the possibilities of "ai", has been follows:

C(j) min{C(i)+(200-(aj-ai))^2}, 0<=i<=j.

• Initialize the value of "C(0)" as "0" and “a0" as "0" to find the remaining values.

• To find the optimal route, increase the value of "j" and "i" for each iteration of and use this detail to backtrack from "C(n)".

Here, "C(n)" refers the penalty of the last hotel (That is, the value of "i" is between "0" and "n").

Pseudocode:

//Function definition

Procedure min_tot()

//Outer loop to represent the value of for j = 1 to n:

//Calculate the distance of each stop C(j) = (200 — aj)^2

//Inner loop to represent the value of for i=1 to j-1:

//Compute total penalty and assign the minimum //total penalty to "c(j)"

C(j) = min (C(i), C(i) + (200 — (aj — ai))^2}

//Return the value of total penalty of last hotel

return C(n)

Step 2 of 2

Explanation: The above algorithm is used to find the minimum total penalty from the starting point to the end point.

• It uses the function "min()" to find the total penalty for the each stop in the trip and computes the minimum penalty value.

Running time of the algorithm:

This algorithm contains "n" sub-problems and each sub-problem take "O(n)" times to resolve.

• It is needed to compute only the minimum values of "O(n)".

• And the backtracking process takes "O(n)" times.

• The total running time of the algorithm is nxn = n^2 = O(n^2) .

Therefore, this algorithm totally takes "0(n^2)" times to solve the whole problem.

Answer 5

Following is the MATLAB code for hotel problem.

clc
clear all

% Data     
% a = [0;50;180;150;50;40];    
% a = [0, 200, 400, 600, 601];    
  a = [0,10,180,350,450,600];    
% a = [0,1,2,3,201,202,203,403];

n = length(a);    
opt(1) = 0;    
prev(1)= 1;

for i=2:n
    opt(i) =Inf;
    for j = 1:i-1
        if(opt(i)>(opt(j)+ (200-a(i)+a(j))^2))
            opt(i)= opt(j)+ (200-a(i)+a(j))^2;
            prev(i) = j; 
        end
    end
    S(i) = opt(i);
end

k = 1;
i = n;
sol(1) = n;

while(i>1)
   k = k+1;
   sol(k)=prev(i);
   i = prev(i);   
end

for i =k:-1:1
    stops(i) = sol(i);
end
stops

Answer 6

As @rmmh mentioned you are finding minimum distance path. Here distance is penalty ( 200-x )^2

So you will try to find a stopping plan by finding minimum penalty.

Lets say D(ai) gives distance of ai from starting point

P(i) = min { P(j) + (200 - (D(ai) - D(dj)) ^2 } where j is : 0 <= j < i

From a casual analysis it looks to be

O(n^2) algorithm ( = 1 + 2 + 3 + 4 + .... + n ) = O(n^2)

Answer 7

If x is a marker number, ax is the mileage to that marker, and px is the minimum penalty to get to that marker, you can calculate pn for marker n if you know pm for all markers m before n.

To calculate pn, find the minimum of pm + (200 - (an - am))^2 for all markers m where am < an and (200 - (an - am))^2 is less than your current best for pn (last part is optimization).

For the starting marker 0, a0 = 0 and p0 = 0, for marker 1, p1 = (200 - a1)^2. With that starting information you can calculate p2, then p3 etc. up to pn.

edit: Switched to Java code, using the example from OP's comment. Note that this does not have the optimization check described in second paragraph.

public static void printPath(int path[], int i) {
    if (i == 0) return;
    printPath(path, path[i]);
    System.out.print(i + " ");
}

public static void main(String args[]) {
    int hotelList[] = {0, 200, 400, 600, 601};
    int penalties[] = {0, (int)Math.pow(200 - hotelList[1], 2), -1, -1, -1};
    int path[] = {0, 0, -1, -1, -1};
    for (int i = 2; i <= hotelList.length - 1; i++) {
        for(int j = 0; j < i; j++){
            int tempPen = (int)(penalties[j] + Math.pow(200 - (hotelList[i] - hotelList[j]), 2));
            if(penalties[i] == -1 || tempPen < penalties[i]){
                penalties[i] = tempPen;
                path[i] = j;
            }
        }
    }
    for (int i = 1; i < hotelList.length; i++) {
        System.out.print("Hotel: " + hotelList[i] + ", penalty: " + penalties[i] + ", path: ");
        printPath(path, i);
        System.out.println();
    }
}

Output is:

Hotel: 200, penalty: 0, path: 1 
Hotel: 400, penalty: 0, path: 1 2 
Hotel: 600, penalty: 0, path: 1 2 3 
Hotel: 601, penalty: 1, path: 1 2 4 

Answer 8

It looks like you can solve this problem with dynamic programming. The subproblem is the following:

d(i) : The minimum penalty possible when travelling from the start to hotel i.

The recursive formula is as follows:

d(0) = 0 where 0 is the starting position.

d(i) = min_{j=0, 1, ... , i-1} ( d(j) + (200-(ai-aj))^2)

The minimum penalty for reaching hotel i is found by trying all stopping places for the previous day, adding today's penalty and taking the minimum of those.

In order to find the path, we store in a separate array (path[]) which hotel we had to travel from in order to achieve the minimum penalty for that particular hotel. By traversing the array backwards (from path[n]) we obtain the path.

The runtime is O(n^2).

Answer 9

I don't think you can do it as easily as sysrqb states.

On a side note, there is really no difference to starting from start or end; the goal is to find the minimum amount of stops each way, where each stop is as close to 200m as possible.

The question as stated seems to allow travelling beyond 200m per day, and the penalty is equally valid for over or under (since it is squared). This prefers an overage of miles per day rather than underage, since the penalty is equal, but the goal is closer.

However, given this layout

A ----- B----C-------D------N
0       190  210     390    590

It is not always true. It is better to go to B->D->N for a total penalty of only (200-190)^2 = 100. Going further via C->D->N gives a penalty of 100+400=500.

The answer looks like a full breadth first search with active pruning if you already have an optimal solution to reach point P, removing all solutions thus far where

sum(penalty-x) > sum(penalty-p)  AND  distance-to-x <= distance-to-p - 200

This would be an O(n^2) algorithm

---

Something like...

• Quicksort all hotels by distance from start (discard any that have distance > hotelN)
• Create an array/list of solutions, each containing (ListOfHotels, I, DistanceSoFar, Penalty)
• Inspect each hotel in order, for each hotel_I
    Calculate penalty to I, starting from each prior solution
• Pruning
    For each prior solution that is beyond 200 distanceSoFar from
    current, and Penalty>current.penalty, remove it from list
• loop

Answer 10

To answer your question concisely, a PSPACE-complete algorithm is usually considered "efficient" for most Constraint Satisfaction Problems, so if you have an O(n^2) algorithm, that's "efficient".

I think the simplest method, given N total miles and 200 miles per day, would be to divide N by 200 to get X; the number of days you will travel. Round that to the nearest whole number of days X', then divide N by X' to get Y, the optimal number of miles to travel in a day. This is effectively a constant-time operation. If there were a hotel every Y miles, stopping at those hotels would produce the lowest possible score, by minimizing the effect of squaring each day's penalty. For instance, if the total trip is 605 miles, the penalty for travelling 201 miles per day (202 on the last) is 1+1+4 = 6, far less than 0+0+25 = 25 (200+200+205) you would get by minimizing each individual day's travel penalty as you went.

Now, you can traverse the list of hotels. The fastest method would be to simply pick the hotel that is the closest to each multiple of Y miles. It's linear-time and will produce a "good" result. However, I do not think this will produce the "best" result in all cases.

The more complex but foolproof method is to get the two closest hotels to each multiple of Y; the one immediately before and the one immediately after. This produces an array of X' pairs, which can be traversed in all possible permutations in 2^X' time. You can shorten this by applying Dijkstra to a map of these pairs, which will determine the least costly path for each day's travel, and will execute in roughly (2X')^2 time. This will probably be the most efficient algorithm that is guaranteed to produce the optimal result.

Answer 11

This is equivalent to finding the shortest path between two nodes in a directional acyclic graph. Dijkstra's algorithm will run in O(n^2) time.

Your intuition is better, though. Starting at the back, calculate the minimum penalty of stopping at that hotel. The first hotel's penalty is just (200-(200-x)^2)^2. Then, for each of the other hotels (in reverse order), scan forward to find the lowest-penalty hotel. A simple optimization is to stop as soon as the penalty costs start increasing, since that means you've overshot the global minimum.