Hi all

I'm pretty new to heuristic things and I tried to implement both Hill Climbing and Simulated Annealing for this begginner-friendly and considered-as-a-tutorial problem for heuristic contests on AtCoder https://atcoder.jp/contests/intro-heuristics/tasks/intro_heuristics_a.

It looks like Hill Climbing and Simulated Annealing yield similar results ( SA: https://atcoder.jp/contests/intro-heuristics/submissions/64189473, HC: https://atcoder.jp/contests/intro-heuristics/submissions/64189544 ).

I'm trying to understand why, and the only reason I could come up with was that there are "loads of neighbours" for each state ((26-1)*365 neighbours per state) so it's basically impossible to get stuck in a local optimum? I guess it could be deeper than that — I'm sure there are actually local optima (it makes sense when you read the problem), so what am I missing? Why wouldn't SA yield to better results here? Maybe I just implemented it wrong? Maybe Hill Climbing would only be bad if the algorithms were allowed to run for 15 hours? I checked locally the initial temperature and temperature decay, there are some "bad transitions accepted" early on and then very few when we get close to 2 seconds. So I don't think the problem is that my temperature + temperature decay are set up such that I'm actually never accepting bad transitions and degenerating to HC.

Any help is appreciated, keep it beginner friendly please :). I should add I'm not really looking for micro optimisation tips (although they're welcome*), but rather trying to grasp a better understanding of when SA >>>>> HC.

*except if you just say code everything in C it'll be ever so slightly faster than C# AOT and will yield better results for both HC and SA