Menu
What would be a good heuristic to use to solve the following challenge?
Quality Blimps Inc. is looking to expand their sales to other cities (N), so they hired you as a salesman to fly to other cities to sell blimps. Blimps can be expensive to travel with, so you will need to determine how many blimps to take along with you on each trip and when to return to headquarters to get more. Quality Blimps has an unlimited supply of blimps.
You will be able to sell only one blimp in each city you visit, but you do not need to visit every city, since some have expensive travel costs. Each city has an initial price that blimps sell for, but this goes down by a certain percentage as more blimps are sold (and the novelty wears off). Find a good route that will maximize profits.
https://www.hackerrank.com/codesprint4/challenges/tbsp
This challenge is similar to the standard Travelling Salesman Problem, but with some extra twists: The salesman needs to track both his own travel costs and the blimps'. Each city has different prices which blimps sell for, but these prices go down over his journey. What would be a fast algorithm (i.e. n log n ) to use to maximize profit?
The prices of transporting the items in a way makes the TSP simpler. If the salesman is in city A and wants to go to B, he can compare The costs of going directly to B vs. costs of going back to Headquarters first to pick up more blimps. I.e. is it cheaper to take an extra blimp to B via A or to go back in-between. This check will create a series of looped trips, which the salesman could then go through in order of highest revenue. But what would be a good way to determine these loops in the first place?
698
To solve the TSP using the Brute-Force approach, you must calculate the total number of routes and then draw and list all the possible routes. Calculate the distance of each route and then choose the shortest one—this is the optimal solution. This method breaks a problem to be solved into several sub-problems.
The traveling salesman problem (TSP) is a classical problem of combinatorial optimization. In the TSP, one is given a n × n distance matrix C = ( c i j ) and looks for a cyclic permutation of the set { 1 , 2 , … , n } that minimizes the function c ( τ ) = ∑ i = 1 n c i τ ( i ) .
Travelling Salesman Problem (TSP) : Given a set of cities and distances between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
The water flow-like algorithm (WFA) is a relatively new metaheuristic that performs well on the object grouping problem encountered in combinatorial optimization. This paper presents a WFA for solving the travelling salesman problem (TSP) as a graph-based problem.
This is a search problem. Assuming the network is larger than can be solved by brute force, the best algorithm would be Monte Carlo Tree Search.
132
Algorithms for such problems are usually of the "run the solution lots of times, choose the best one" kind. Also, to choose what solution to try next, use results of previous iterations.
As for a specific algorithm, try backtracking with pruning, simulated annealing, tabu search, genetic algorithms, neural networks (in order of what I find relevant). Also, the monte carlo tree search idea proposed by Tyler Durden looks pretty cool.
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
