ALGORITHMS

This document briefly explains the algorithms that were used or taken into consideration in MyJuliaPackage to solve the problem described in the Google Hashcode 2014 competition. At the end it will explain the solution, with all separate algorithms taken into account.

Before explaining the algorithms, to save space and time, we stored our neighbors using a dictionary. ​​Each junction was stored as a key with its neighbors as values. This allowed us to find the neighbors of our junctions with time complexity O(1).

Greedy

To start, we will be considering a greedy algorithm. Essentially, the cars will move one street at a time, and will choose the next street based on a heuristic. In this example, said heuristic takes in all the neighbors (the streets touching our current junction) and finds which street takes the largest distance/duration from the current junction. That street then becomes the next path for our current car to take. However, it will not take that street if the time to traverse said street surpasses our time constraint. In that case, that car is now finished and does not get checked.

Of course, there must be some overlap since we have eight cars. To combat this, if every single neighbor has already been seen, then we choose the street with the shortest duration to go to next. Again, it will not take that street if the time to get to the next junction surpasses our time constraint.

This greedy algorithm will work quickly because each car only needs to look at the outgoing neighbors of its current junction. This means that the time complexity for each time step is O(E) with E being the number of streets (edges). Most junctions have only a few neighboring streets, so this is essentially a constant time complexity.

Also, at each time step we need to make a data structure of size O(E) to be able to search through our neighbors. That gives us an O(E) space complexity, but since there aren't that many streets connected to each junction the space impact is minimal.

Greedy with a Lookahead

To increase the greedy algorithm’s distance covered, we can have the cars look ahead a certain number of streets to find a more optimal path. Instead of taking the next street with the largest distance/duration, we look ahead through 12 streets (time steps) to see which path will give us the largest total distance/duration covered. This sends our car to the junction that would lead us to that path. It then repeats. Again, this takes into account the time constraint and will not send a car to a path that would exceed the total time. To look ahead we use a depth forward search (DFS). We have the depth currently set as a parameter that can be specified by the person running the algorithm. It automatically uses depth 10.

There of course will be overlap again, which we will combat within our DFS. If a street has already been seen, we do not have it contribute to the total distance/duration calculated for the path. This way, the car can still take the seen street if it leads to the outcome with the largest distance/duration, but it is more likely to take unseen streets.

Of course, this algorithm will be slower and take more space than our greedy algorithm. A branching factor B is the max number of neighbors a certain junction will have. For our data, we found this value to be six. Since we are looking ahead by 12 steps, we will be taking this branching factor to the tenth. Therefore, when we are searching using our DFS we find that our upper bound of time and space complexity for each time step is O(6^12) because not every junction has six streets that are connected to it.

Improving the Greedy Algorithm with a Lookahead

When running the greedy algorithm with a lookahead, we realized that many of the streets were being taken multiple times and we were leaving pockets of streets that were never taken. The cars were looking to the further streets with a very large distance/duration and trying to take the fastest path to get there. This caused it to ignore many small streets in the surrounding areas and retake previously seen streets.

Below are a few of our different approaches to solving this problem. The last section indicates our final solution which gave us our largest distance traveled.

Greedy with a Known Lookahead

Our first attempt to remove this issue involved understanding that our starting junction had four possible directions that the cars could take. The last four cars all went the same direction as the first car causing many sides of the city untraversed. So, we sent two cars down each of the streets and then let them begin using the algorithm. This gave us a slightly better total distance and kept the time/space complexity the same as it was before.

Greedy with Dijkstra’s Lookahead

We then thought that sending four cars immediately to each maximum and minimum latitude and longitude of the map would allow our cars to be spaced out much more quickly, and therefore repeat less streets.

We used the 'dijsktrashortestpaths' function in 'graphs.jl' to find the shortest paths (by distance/duration) that our cars could take to get to those max/min points. This did not end up changing our total distance at all and kept the time/space complexity the same as before.

Greedy with a Dependent Lookahead

Our next try involved reducing the depth of our lookahead when moving further into the map. We assumed that this would send our cars to different sides of the map, and then begin to take the streets that were less often seen. So for the first 1000 time steps (streets) we had it set to depth 10, and then for the remaining steps it was of depth 5.

This in fact made our solution worse, albeit faster (since the time steps >1000 had time and space complexity O(6^5)), but it lowered our total distance by at least 100,000 m. We also considered a few different changes in depth, but each still lowered our total distance.

Greedy with a Weighted Lookahead

Our final and best fix was to add weights to the depths of our search. We wanted the distance of the streets further away from our current junction to account for less in the total distance to reward taking closer streets that have not been taken (since distances traveled on previously taken streets do not contribute to the overall goal).

To do this, we multiplied the distance/duration of the street by the square root of the depth/11 (so the distance/duration of the closest street, i.e. depth 11, was weighted by (10^1/2)/11, and the distance/duration of the second closest street, i.e. depth 9, was weighted by (9^1/2)/11, and so on and so forth).

This didn’t make the solution any slower than our earlier greedy algorithm with a lookahead and it increased our distance traveled by about 500,000 m.

Upper Bound

To find the upper bound for this problem, we need to find the total distance that could possibly be covered by all of our cars within the time limit. This number does not need to take into account feasibility since we just want an upper bound. We chose to look at three ways to solve this: the fastest streets, the longest streets, and making our own algorithm an undirected graph.

For our first idea, we simply take a list of all the streets and sort them by their distance/duration, putting those with the largest speed first. We then sum the distance and time (separately) of the streets from fastest to slowest until the summed time (plus the next street) exceeds our time limit multiplied by the number of cars. Since we considered the last street possibly taking us over the time limit and did not include it, we got a lower upper bound than without it. The summed distance of those streets is our first possible upper bound. We found this to be: 1525273m

For the second idea, we sort the streets by their distance, putting those with the longest distance first. We then sum the duration and the distance of those streets (separately) from longest to shortest until our total time duration exceeds the time limit multiplied by the number of cars. The summed distance of those streets is our second possible upper bound. In practice, this idea did not work as well. Since we are trying to maximize distance over 18000 seconds, we should be considering distance over time.

For a final idea, we would’ve used our own algorithm to make an upper bound. If we changed our graph to an undirected graph it would make the solution see more streets in a faster amount of time. We however would’ve needed to account for the fact that our algorithm does not hit the true upper bound with 54000 seconds (the original total time limit). So, we would take the difference between the distance of our algorithm and the total distance of the streets in our problem and add it to the bound we just calculated. We did not put this idea into practice, but it would likely be a lower upper bound than our past two ideas.