4 ms·

> best heuristic code for TSP .. 100k-city instances These "best cases" are hand-tuned for the domain by algorithm experts - right? How big is the performance

• bopbeepboop 6y ago
  My impression of Alpha Zero research is that given enough feedback, AI would find “good” routes in the sense of sensible driving, minimal lefts, nearby bathrooms, etc — but not that it had anything in particular to say about hard combinatorics. Ie, AI would find “fast” routes in the sense of “a human driving these gets done fast, all things considered” but not necessarily “fast” in a simple combinatorics problem — which is actually good, because simple combinatorics often fails in the real world (eg, longer routes without left turns are faster). Did I miss something about how this more directly applies to combinatorics?
  • algo_trader 6y ago
    Combinatorics (and AZ) can have unlimited self-play (i.e. search) with precise reward. This is quite rare in most real world problems. I dont really have a strong intuition for mathematics. It is possible that nets are simply good with spatial boards and not good enough with arbitrary graphs.
• thxg 6y ago
  > These "best cases" are hand-tuned for the domain by algorithm experts - right? Correct. It is arguably more than just "hand-tuned". The algorithm I mentioned, LKH, was entirely designed for TSP, and I'm not aware of it being applicable to much else. > How big is the performance jump from generic z3 or whatever? For TSP, an enormous jump. Certainly more than 3 orders of magnitude.