Игра «Тетрис», созданная в 1985 году российским программистом Алексеем Пажитновым, знакома, пожалуй, каждому пользователю какого бы то ни было электронного устройства — от телефона до компьютера. Хотя он относится к числу игр, требующих известных умственных усилий, вряд ли играющим в «Тетрис» приходит в голову, что они — в меру сил — участвуют в решении классической математической задачи. Ученые Массачусетского технологического института, проанализировав вычислительную сложность алгоритма этой игры, пришли к выводу, что, при определенных условиях, он имеет много общего с так называемой задачей коммивояжера. Задача коммивояжера состоит в определении оптимального маршрута, проходящего через некоторое число пунктов, задачу же «Тетриса» можно сформулировать как выбор оптимальной стратегии игры, т. е. набор максимального числа очков за минимальное число ходов. Обе они относятся к классу так называемых NP-полных комбинаторных задач.

Поделитесь материалом с коллегами и друзьями