Sharing of the sources

63 posts / 0 nouveau(x)
Dernière contribution
Reportez-vous à notre Notice d'optimisation pour plus d'informations sur les choix et l'optimisation des performances dans les produits logiciels Intel.

Heye, unfortunately I won't be able to check it next several days. So you think you wrote polynomial solution, which solves the problem without repeating cities? Have you test it on other scenarios? What about performance?

In the worst case it has to walk almost all paths twice, but the walk back is at max as long as the travel he did so far. I checked the run time, it worsened by about 10% to 20%... But I didn't go for optimization yet. Right now I am using the std::map, which is implemented as a Red-Black-Tree of Pairs I think.
I think the run time is now affected mostly by the insertions into the set because the case of visiting the same city twice shouldn't occur that often... If I replace the map by a vector of integers, that simply keeps the number of branches, I could also replacing the set I use to keep track of the cities I visited so far. If I have time I'll try that, but for now I need some But I could replace that by a vector of integers, that is simply keep the number of branches, therefore also replacing the set I use to keep track of the cities I visited so far.
One possible problem I see so far: I might have to change the shortcut I take (using the work hard spanning tree) but I have to create scenarios to test that...

Rock the bits!

Does anyone know if we can use benchmark cluster to test our programs after contest?

Heye, I've found a minute to play with tests for you new solution a bit.
Your solution is still invalid. Same test, just change max_layover to 33400. Now it finds non-optimal path.
Actually, when I constructed this test, I expected that your solution will behave as it behaves now (finding path with $2000 flight). But when I calibrated layover time, I found that in some cases your solution doesn't find path at all.

Zitat:

eviltosha schrieb:

Heye, I've found a minute to play with tests for you new solution a bit.
Your solution is still invalid. Same test, just change max_layover to 33400. Now it finds non-optimal path.
Actually, when I constructed this test, I expected that your solution will behave as it behaves now (finding path with $2000 flight). But when I calibrated layover time, I found that in some cases your solution doesn't find path at all.


Damn, you scared me.
At first I thought that you've made a typo error, Heye = Hey :)

Zitat:

eviltosha schrieb:

Heye, I've found a minute to play with tests for you new solution a bit.
Your solution is still invalid. Same test, just change max_layover to 33400. Now it finds non-optimal path.
Actually, when I constructed this test, I expected that your solution will behave as it behaves now (finding path with $2000 flight). But when I calibrated layover time, I found that in some cases your solution doesn't find path at all.


Damn, you scared me.
At first I thought that you'we made a typo error, Heye = Hey :)

Dusan, I haven't tested your code yet, but I hope I'll have time for it next week.
Have you managed to make polynomial algorithm, that always finds optimal path without repeating cities?

Hi eviltosha,

I assume that under polynomial algorithm you mean algorithm with polynomial complexityu? If that is the case, then no, I'm pretty shure that this algorithm doesn't have complexity that can be described with polynom.
If polynomial algorithm is one of the common algorithm, then it is not used (or not intentionally).

Unfortunately, code is not commented (at begining it is, but how end of the contest was closing, and I was short on time, code unfortunately becomes unstructured and uncommented), so my advice to you is to look at the readme.txt, main idea is there, the implementation is not so important.
Just to mention, I had no time to fix all memory leaks, since I was impossible to install intel parallel studio on Ubuntu, and have no time to search for them manually, only significant ones are fixed.

Also, could you upload your source or algorithm described in .txt, for now just few peoples uploaded their sources.

Hey,

You have really great result. My algorithm is not that good. I didn't use dijkstra algorithme because of negative path like in the tricky scenario in another post.
I use the default algorithme using cut in the tree as I compute the price of each travels.

There is my source code if someone want to have a look.

Okay, I got it, solves now both cases. But it got stuck finding the “Play Hard” Proposition 1 : ATLANTA in scenario 35.... That's probably the negative cycle you were talking about. But scenario 35 is too big to examine it, do you have a small scenario causing a negative cycle?
You said that you also saw some layover times where my algorithm didn't find any path at all. Which was it?

Rock the bits!

There can't be any negative cycles, only negative edges. You can try to extract little (minimal) scenario from big one. Probably the best way is to get all flights from your algorithm's answer and all flights from original answer. So graph will have both paths and be relatively small. But I'm not sure that this will work for this case. Another way is to write tester, that will remove flight, test whether your solution still invalid, and if it is, remove next flight. I heard Google Chrome team has such tester for their browser, that cuts HTML page, on which Chrome crushes, to minimal size.
(About layovers) Yes, but it was first version, and you have already fixed it.

My algorithm doesn't produce any answer, it hangs and just keeps eating ram. I could print out all edges I use in with the solution that was actually incorrect (but found the right path) and then compare them to the ones I use in the algo that hangs, but it's not worth the effort I think. I might just find out that it is not possible to solve it that way... :/

Rock the bits!

Pages

Laisser un commentaire

Veuillez ouvrir une session pour ajouter un commentaire. Pas encore membre ? Rejoignez-nous dès aujourd’hui