These are the type of articles that makes HN worth looking in to every once in while :). The circuit routing is indeed worth $100M problem. And it's going to re

These are the type of articles that makes HN worth looking in to every once in while :). The circuit routing is indeed worth $100M problem. And it's going to remain unsolved in classical sense because its NP-Hard. The reason this is very interesting problem is that basic version of the problem is fairly easy to specify: You are given bunch of polygons, each with few fixed points on it. You are also given series of sets, each containing list of points that must be connected together. Can you come up with connections that has minimum crossing with each other (see Wikipedia [1] for more formal statement of routing problem). The more practical version of the problem will include more constraints to make sure the design meets timing, has no crosstalk problems, meets any metal density requirements, does not suffer from antenna effects, and so on. Recently Travelling Salesman Problem was attacked using reinforcement learning[2] and that could be a good start to attack routing problem. I'll be definitely looking in to this! [1] https://en.wikipedia.org/wiki/Routing_(electronic_design_automation) https://en.wikipedia.org/wiki/Routing_(electronic_design_aut... [2] https://arxiv.org/abs/1611.09940 https://arxiv.org/abs/1611.09940