Improving GASMA

[GZHoffie]

• [x] Find ways of speeding up finding highways
• [x] Write draft code for shortsighted-GASMA, a more greedy approach that looks for a good highway in a small subset that is very close to the current position
• [x] Write benchmark code for accuracy testing (MAE between GASMA and result of Needleman-Wunsch)
• [x] Write benchmark code for used time
• [x] Add unit tests
• [x] Slides for meeting

Way of speeding up finding highways:

• [x] Not use multi-processing

[GZHoffie]

Idea of shortsighted-GASMA:

1. Find the hurdle matrix,
2. Flip all single zeros to ones, flip all single ones to zeros (need benchmark result of effect)
3. Delete the columns at which all rows is a 1, and +1 to hurdleCost, "The hurdles that you must cross"
4. Starting from the starting position, find the highways that start within 3 columns, and among those highways choose the longest one
5. go to the end of the highway and repeat step 4 until no more highway is left.

[GZHoffie]

Benchmark results with simulated data (1000 * L = 100, e = 5 %)

Algorithms	Time	MAE	Correct Rate
Needleman-Wunsch (without backtrack)	36.87	0	1
GASMA	1.935	0.172	0.91
GASMA-Shortsighted	0.815	0.247	0.869

There may be some errors in my implementation, so it needed to be checked again.

TODO:

• [ ] Find potential errors in my implementation
• [ ] Test it on other datasets

[GZHoffie]

Problems with the current implementation:

• In GASMA, I end the algorithm as soon as we reach the final column. Should be the final column in the central lane?