Maximum efficiency

Question

The problem with maximum efficiency

These are cities of N, and there is a wanderer.

The time required for it to move from city to another city is known - Txy (from city x to city y).

From any city, he can go to any other city so that it is a full schedule.

Each city has a sum of money that the wanderer wants to collect.

Not enough time to go through all the cities.

Having the total available time T and starting point i, the problem is to find the best route so that the money he collected is maximum.

Input Number Range:

• N is between 400 and 600
• Mx (M1, M2, ...) are between 100 and 500, x between 1 and N
• Txy are between 80 and 200, x and y are between 1 and N
• Txy is the optimal time, so Txy <Txz + Tzy, for any x, y and z between 1 and N.
• T is between 3500 and 5000

Answer 1

Seems dynamic:

Let a [x] be the money to collect from the city x.

Let dp [x] [t] mean the maximum amount of money he can collect, spend time t and complete in city x . Initialization and updating as follows:

• for the starting point x0 , dp [x0] [0]: = a [x0] . For other cities x dp [x] [0]: = -1 (invalid);
• for each time t from 1 to T :
  for each city x :
  for each city y st edge [y] [x] <= t :
  denote p: = t - edge [y] [x] ;
  if dp [y] [p]> = 0 // it is possible to get to y in time p
  then dp [x] [t] = max (dp [x] [t], dp [y] [t - edge [x] [y]] + a [x])
  
• returns the maximum over all dp [x] [t].

The total complexity is O (T * N ^ 2) .

Answer 2

I am thinking of a solution based on backtracking. You must determine the algorithm for finding the best solution (the one that gets the most money). You finish the algorithm either when you have traveled to all cities, or when you have exceeded the time that you have. To ignore unprofitable candidates: you need to check whether the money you need to earn based on the minimum number of cities that are still left to visit is at least the current optimal solution; and also check the minimum time spent moving from one city to all the rest.

To find out the minimum amount of money that you earn, you need to multiply the number of cities that have yet to be visited for the minimum amount of money in one city.

The same applies to the minimum time that must be visited in all other cities.

Edit: I forgot to tell you that the cost of this algorithm is O (a ^ n), where a is the number of arists of the graph (i.e., N * (N-1)) and n is the number of vertices (i.e., N). The cost may be better if you define good features to know when your actual candidate cannot be the solution, and also when it cannot be better than the current optimal solution (if you are lucky enough to find a solution at the beginning of the iteration process, it really helps reduce time

Answer 3

The amount of money in each city is unknown, so the best possible route is the shortest route from one city to another.

Here is what I would like to do if I programmed it in Javascript using recursion:

http://jsfiddle.net/rd13/ShL9X/5/

c = ['london', 'manchester', 'liverpool']; //Cities t = { 'liverpool': { 'manchester': 130, 'london': 260 }, 'london': { 'manchester': 250, 'liverpool': 260 }, 'manchester': { 'london': 250, 'liverpool': 130 } } //Time between cities cn = 'london'; //Current city var shortestDistance = 500, allottedTime = 300, next_city, time = 0, totalTime = 0, path = [cn]; optimal = function (cn) { for (i in t[cn]) { //So as not to visit cities that we have already visited if(path.indexOf(i)===-1) { next_city = t[cn][i] < shortestDistance ? i : next_city; shortestDistance = t[cn][i]; totalTime = Math.min(t[cn][i] , shortestDistance); } } time += totalTime; path.push(next_city); if(time > allottedTime){ document.write("The most optimal route between cities is: " + path); } else { optimal(next_city); } } optimal(cn); 

Sorry, there is no help on the algorithm, this is from a programming point of view, since I thought it was an interesting task. The above is not an optimal mind.

Answer 4

This is a variant of the well-known problem, commonly known as the traveling salesman problem. You can find a detailed description of this and similar problems, as well as further links to wikipedia here: http://en.wikipedia.org/wiki/Travelling_salesman_problem