Я написал сайт на основе JavaScript, который может вводить, редактировать и решать Нонограммы . Как вы, возможно, знаете, решение нонограммы - это NP-полная проблема.
Моей первой попыткой был чистый (однопоточный) JavaScript. Но на больших неграммах Chrome показал свой BSOD и через несколько минут убил скрипт JS. Следующая попытка была использовать Web Workers . Я разделил алгоритм решения так, чтобы каждый работник получил одну строку / столбец для решения и вернул результат. Это было улучшение, и он смог решить нонограммы среднего размера. Но, тем не менее, иногда браузер убивал виртуальную машину JS, показывающую BSOD, через некоторое время, плюс веб-сайт не был действительно адаптивным, как я и ожидал, поскольку для этого и созданы веб-работники, не так ли?
Просто для удовольствия я перенес алгоритм решения на Python и использовал запросы ajax, вызывающие скрипт python вместо Web Workers. Интересно, что это было даже медленнее, чем JavaScript, но после некоторого времени вычислений запрос возвратил 500 Internal Server Error. Я полагаю, что это связано с максимальным временем выполнения сценария CGI, равным 30 с на PHP afaik.
Идея CGI была не самой лучшей, потому что когда несколько пользователей хотят решить неограмму, сервер работает на 100% ЦП, поэтому я, вероятно, придерживаюсь вычислений на стороне клиента.
Итак, вопрос в том, каков наилучший способ сделать это вычисление (которое может занять около 10 минут для больших неограмм)? Я думаю, что время выполнения не является проблемой, пока веб-сайт продолжает отвечать и до тех пор, пока браузер не убивает выполнение задач.
Тем временем я также пытаюсь оптимизировать рекурсивный алгоритм ....
Спасибо!