Чего релаксация сделать не может, так это дать гарантированный доступ к идеальному решению. Но компьютерная наука может количественно выразить компромисс между потраченным временем и качеством решения, который предлагает релаксация. Во многих случаях этот коэффициент грандиозен, немыслим (например, ответ, который наполовину так же хорош, как идеальное решение, полученный в одну квадриллионную времени, требующегося для получения идеального решения). Идея простая, но глубокая: если мы готовы принять решения, которые достаточно близки, то даже самые заковыристые проблемы можно решить с помощью правильных методов.
Временное снятие ограничений, как в минимальном остовном дереве и в вопросе «что, если вы выиграете в лотерею?», является наиболее исчерпывающей и понятной формой алгоритмической релаксации. Но есть еще и два других, более трудноуловимых вида релаксации, которые неоднократно возникают в исследованиях оптимизации. Они доказали свою важную роль в решении некоторых неразрешимых проблем в этой сфере, напрямую влияя на ситуации в реальной жизни – от градостроительства и борьбы с болезнями до планирования спортивных соревнований.
Бесчисленное множество оттенков серого: непрерывная релаксация
Проблема коммивояжера и задача Меган Беллоуз по поиску лучшего плана рассадки – особый вид задач оптимизации, известный также как дискретная оптимизация – то есть задача, не имеющая бескрайнего множества решений. Коммивояжер едет либо в этот город, либо в тот; вы сидите или за пятым столиком, или за шестым. Только два варианта и никаких оттенков серого!
Подобных задач дискретной оптимизации вокруг полно. В городах, например, проектировщики стараются расположить пожарные машины так, чтобы доехать до каждого дома за определенный отрезок времени, скажем за пять минут. С математической точки зрения каждая пожарная машина «охватывает» все дома в округе, до которых можно добраться от исходной точки в течение пяти минут. Задача заключается в том, чтобы найти минимальное количество локаций, охватывающих все дома. «Представители этой профессии [пожарные и спасатели] только что перешли на такую модель покрытия, и это здорово, – говорит Лора Альберт Маклей из Висконсинского университета в Мэдисоне. – Это то, что легко смоделировать». Но так как пожарная машина либо стоит в указанном месте, либо нет, то попытки рассчитать этот минимальный набор вариантов включают дискретную оптимизацию. И, как замечает Маклей, «это та точка, начиная с которой большинство задач становятся трудными в вычислительном отношении, потому что невозможно сделать половину того и половину этого».