Коллапс волновой функции. От одного заказчика услышал новый для себя термин "алгоритм коллапса волновой функции". Посмотрел. Это по сути жадный алгоритм, но после каждого жадного шага происходит вычеркивание невозможных вариантов и фиксация тех ситуаций, где уже вариант однозначен. Если решения не найдено, отменяем заменяем последнее принятое решение (перебор с возвратом). Как люди в судоку играют, в общем. В целом вполне себе эффективный алгоритм по соотношению качество/скорость. Если надо, может быть упрощен до жадного, или усложнен до линейного программирования. Между коллапсом и ЛП есть еще промежуточные по сложности варианты. Можно, например, выбором шага играться, где мы фиксируем. После нескольких прогонов находить узкие места где все сыпется и т.п. Нормальный алгоритм в целом, хотя я непосредственно с ним еще не сталкивался. Пока получалось, что либо задачи надо решать быстро, либо достаточно качественно. Но у заказчика как раз промежуточный случай похоже. Решать надо за секунды, и задача всегда имеет решение, то есть замороченный алгоритм не нужен.