To run follow run sections. Algorithm explained in the Algorithm section.
The fastest way to run it. Is use Dockerfile.
docker build --build-arg dir="Training Problems" --build-arg pyScript="evaluateShared.py" -t vpr:latest .
docker run vpr:latestOr run run.sh
The directory must contain the problems directory and evaluateShared.py. You can set them in build arguments dir and pyScript accordingly.
Default values
ARG dir="Training Problems"
ARG pyScript="evaluateShared.py"Alternatively, you can compile the Go binary for your operating system using the command:
go build .The original intent was to implement the A* or smt similar. However, I started with the Nearest Neighbor algorithm.
This allowed achieving a mean cost of 52041.86997702847 and an average runtime of 4.130744934082031ms. In the next iteration, I decided to tune it with some versions N recursive brute force Salesman algorithm.
This resulted in a slight improvement in the mean cost, down to 49508.511593292424, but a significant increase in runtime to 8068.529975414276ms. I figured out that some test cases contained a multitude of small vectors close to the depot (especially problems 5 and 6). What caused very deep recursions and consequently, longer runtimes.
So I decided to apply following KNOWHOW : If the algorithm's execution exceeded 1 second for N=3 (branching), the best result from N=1,2 would be selected instead.
Later I applied different evaluators functions.
After we have a list of possible routes we start evaluate them.
- GetTheBestByLengthAndCostMin - we filter the longest routes and choose route with minimal cost
- GetTheBestByLengthAndCostMax - we filter the longest routes and choose route with maximum cost
- GetTheBestByLengthAndRandom - we filter the longest routes and then choose random one from it. To ensure determinacy, I seed the random generator with content of source file. For every iteration we recreate a random generator so it always give the same random sequence.. I use CHACHA8 fast random generator which was added in rand/v2 go22.
See performance for details.
// 1 52041.86997702847 <-- NEAREST NEIGHBOR
// 2 49628.99589848467
// 3 49324.77775315616
...
// 48341.15786902501 <-- run N = 1, 2, 3 with Min, Max, Random evaluators
I am trying to demonstrate proficiency in GoLang and in general programming.
Most golish part is this clumsy code. As I explained in the Algorithm section, I noted that some test cases take less than 1ms with N=1 and up to 150 seconds with N=3. We start all tasks at the same time in different goroutines. I chose not to add a process limiter as the current implementation only uses up to 91 goroutines at most, with 3 of them finishing almost instantly. The important thing is to catch test cases that may take a lot of time and stop them right away. The mentioned logic handle it.