machine learning for NP hard problems
сузить пространство для поиска
я увидел эту идею на лекции от Huawei, и она мне очень запала.
лекция была о том, как применить МЛ алгоритмы для NP сложных проблем, задачи где, возможно, время чтобы решить её не полиномное (NP)
не трудно убедиться что время МЛ алгоритма чаще всего полиномное (P). иногда огромное, но зато P, что лучше чем NP
тогда, как насчёт – обучить МЛ алгоритм решать NP сложные задачи? тогда оно будет решаться за P
прикольная идея. но что вообще значит, решать такую задачу через МЛ алгоритм? как например применить МЛ для traveling salesman problem?
ответ: МЛ алгоритм, не решает задачу на прямую, он не выдает ответ. он помогает быстро отсеять неоптимальные решения. или другими словами сузить пространство поиска
по сути, это та же эвристика, но теперь она умная – выученная на данных
эта идея взорвала мой мозг и думаю об этом частенько 🫠