|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Simple solution tips | Gilles Deleuze | 1399. Economical Director | 22 Dec 2020 18:02 | 1 | Please, think about the problem yourself at first!
I think you could use this problem to exercise your heuristics and optimization skills and thus I'm sharing a solution that is both easy to think and implement so that somebody less experienced might learn new strategies in optimization problems.
//////
Yes, it's a Vehicle Routing Problem, as even confirmed by the author on this forum.
Firstly, you can compute —with Dynamic Programming— optimal distance visiting some subset of nodes starting at node 0 and ending at some other node. Let dp[S][last] be the state of such DP, which computes the smallest path cost that visits each vertex of S once and starts at 0 and ends at last. This is a classic TSP DP problem that can be computed in O(N^2 2^n). Note, that you have to use a type shorter than 32-bit to store the DP. The cost of a trip is then dp[S][last] + D(last, 0).
Generate a starting solution that performs a trip for each lorry, M trips in total.
So far, nothing a beginner cannot do!
Perform heuristic search to improve it.
I used a Large Neighbourhood Search heuristic.
Remove some number of lorries from trips from the CURRENT_SOLUTION and try to insert them one by one again. That is, greedily calculate the cost of insertion, using DP, of each lorry in each trip —or creating a new trip— and choose the lorry and a trip with smallest possible value.
Decide if the obtained repaired solution is the new CURRENT_SOLUTION. I implemented this decision using Simulated Annealing, but you can simply do it if the repaired solution has a better cost.
If the CURRENT_SOLUTION is better than the BEST_SOLUTION, well, you know what to do!
I started from the small number of removed lorries and gradually increased it if after some iterations there weren't an update to the BEST_SOLUTION. This is a gradual increase of Neighbourhood.
In fact, my solution is terribly inefficient, and I could use better data representation and save time making some calculations, improved heuristic by adding more complex rules, and perhaps get rid of the DP step in favor of simple random greedy insertions. But, I just decided to keep things simple.
| | WA on test #28 | Shen Yang | 1399. Economical Director | 14 Dec 2016 20:03 | 5 | any one help?? I need help... I use radom to generate 200 chain list,and then cut the chain list, using O(polynomial) dynamic programming, it is WA on test # 26,
then I use regular brute_force search times>=1e7 return, it WA on test #28...
anyone give some ideas?? I think cut the chain method get WA is because though between two rows there is at most one same buyer, but there maybe more then two rows have same buyers
for exmaple ,structure of solution maybe 0--1---2--3--4--5---0
0--1--6--0
0--2--7--0
0--3--8--0
0--4--9--0
0--5--10--0
Edited by author 14.12.2016 14:14 AC now it is some stupid bugs on my code?? btw , I think this problem is much easier than ural 1394 why not find accuarcy solution? | | I have some thought on this problem: | Shen Yang | 1399. Economical Director | 7 Dec 2016 14:25 | 1 | first use dynamic programming to find the minimum value of distance from 0 and visit 1~m once then to 0, we can get a chain 0--i1-i2--...-im--0
then we consider to cut this chain, use dynameic programming dp[i] to record distance.we cut first i node of the chain..
dp[m] is the result..
I'll try this idea... | | Help from author (+) | Sandro (USU) | 1399. Economical Director | 22 Mar 2007 12:01 | 1 | This is a variation of "Vehicle routing problem" (VRP). You can search for some good ideas in the Internet. | | 1399 Interesting for all people problem | svr | 1399. Economical Director | 2 Feb 2007 20:23 | 3 | This problem may open new type of contest for
difficult ptactice-oriented problems by number of passed tests from big their amount in given TLE Additional!
But if correspondent send his test-case for which it's program
gives better result tnah jure's one he also win and must get accepted contest for difficult ptactice-oriented problems by number of passed tests What is the difference between this suggestion and TopCoder's Marathon Matches? | | New problem is available to solve! 1399 "Economical Director" (-) | Vladimir Yakovlev (USU) | 1399. Economical Director | 3 Jan 2007 02:25 | 9 | "Your program will pass a test if it produces an answer that is no worse than the answer produced by the jury’s program for the same data"
Does it mean, that the author can not prove his solution? Or (more over!) he does not know correct solution, and the tests are generated by brute force... Clarification is required. Yes, the hint is quite ambiguous and let's us understand that the author wants heuristic solutions.
So, I wonder, must our answer be optimal for an AC? Or just better then the author's solution? Why not?
For example, you have a value of some hash function crypt() (MD5 or smth) and the problem is to find a key such that crypt(key) is as close to the given value as possible. Then optimality checking is trivial but solution is very hard :) md5() is unidirectional, and this problem's effectiveness function is not. I think that to check the optimality is not easier than to find a solution (both problems seem to be NP, although I may be mistaken). Jury has not optimal solutions for tests. Answers for tests are outputs of jury's program that passes TL and ML. Validator checks the correctness of your output and compares it to the jury's answer. So your answer should be just better then the jury's one. The problem is really novel. If one cannot solve a problem, he may just add it to Timus, I will think about it ;)
Edited by author 03.01.2007 02:06 The problem is obvious NP-hard, so to get optimal answers for all tests is not so easy. :) Try to create some heuristics. |
|
|
|
