В среде математиков популярна задача про зерна и шахматную доску. Один мудрец оказал услугу своему хозяину, после чего последний предложил ему выбрать любое вознаграждение. Мудрец был не промах и попросил шахматную доску, где на каждой клетке лежали бы зерна пшеницы в определенном порядке: на первой клетке – 1, на второй – 2, на третьей 23=8 и так далее на остальных клетках.
Поначалу хозяин был рад, что мудрец попросил такую маленькую награду. Но когда пришло время выполнить просьбу, все оказалось сложнее. Объем зерна, если соблюдать все условия задачи, должен был составить около 1000 триллионов тонн. Это в сотни раз больше, чем общемировой ежегодный урожай пшеницы!
Экспоненциальные алгоритмы
Эта задача относится к разряду тех, где бессилен даже самый навороченный компьютер. Суть проблемы в том, что достаточно незначительно увеличить входные данные, чтобы перейти от решаемой задачи к трудно решаемой.
В этих случаях количество операций возрастает в зависимости от числа входов по закону, близкому к экспоненте еn (е≈2,72; другое название – экспоненциальные алгоритмы).
Транспортные логисты маленькой такой компании
Представьте что мы с вами логисты небольшой транспортной компании.
Допустим, у компании, в которой мы работаем, небольшой бизнес.
1 большая машина и 25 клиентов.
Как логисты мы составили маршрут алгоритмом ближайшего соседа (всегда добавляем в маршрут ближайшую точку от последней в маршруте). Но начальник как всегда хочет больше прибыли и ставит перед нами задачу оптимизации длины пути. Не долго думая, мы сели решать задачу полным перебором.
Несколько шагов для полного счастья полного перебора
Имеем:
1) матрица расстояний между всеми клиентами
2) маршрут, составленный жадным алгоритмом
1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-24-25
3) длина пути l=76
Начинаем перебирать варианты:
2-1-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-24-25
l=74
Ура! получили вариант лучше. Побежали к начальнику. А начальник недоволен. Говорит, мало сэкономили, хочет больше. Видимо, придется показать ему все варианты, чтобы из них выбрать лучший, и тогда точно начальник будет доволен.
Следующий вариант:
2-3-1-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20-21-22-23-24-25
l=92
и т.д.
Перестановки
На 325 варианте рабочий день закончился. Решения нет. Появился вопрос: а сколько всего вариантов надо будет посчитать? Пошли гуглить про перестановки.
Число всех перестановок порядка n равно числу размещений из n по n, то есть факториалу.
Хорошо что на калькуляторе есть n!
25! = 15 511 210 043 330 985 984 000 000
Да это же 15,5 септиллионов (15,5*1024)
Впечатляет! Руками на бумаге столько раз длину пути не посчитаешь. Нужен компьютер и даже не excel.
Псевдокод полного перебора
цикл по вариантам
перестановка двух точек
вычисление длины маршрута по матрице расстояний
если длина нового маршрута < длины предыдущего
замена предыдущего значения длины на новую
конец цикла
Хорошо, что мы знакомы с C++. А ведь в университете думали, что логистам это никогда не понадобится. Написали программу. Запустили, ждем…
Прошло три часа, в файле отчета увидели новые маршруты и постоянно меняющуюся длину пути.
Второй день работы подошел к концу. Программа все еще работает. Снова вопрос: а сколько времени будет работать программа?
Гугл, Гугл ты могуч!
Производительность современного настольного компьютера в диапазоне от 10 до 100 GFLOPS.
Нам для выполнения оптимизации начальник выдал Core i5-2500K 3.3 ГГц ~ 100 Гфлопс, т.е. 1011 операций в секунду.
Долго ли, коротко ли?
Значит, даже если каждый вариант будет требовать вычисления всего одной операции, например сложения, то для задачи с 25 клиентами потребуется 15,5*1024 / 1011 = 15,5*1013 секунд.
Или 1,55112E+14 / 60 = 2,5852E+12 минут,
Или 2,58520E+12 / 60 = 43086694565 часов,
Или 43086694565 / 24 = 1795278940 дней,
Или 1795278940 / 365 = 4918572 лет.
Ого! это чтобы дождаться окончания программы потребуется примерно 50 000 жизней. Что же делать? Идти к начальнику с вестью о том, что решить проблему оптимизации не получиться?
Нет, ну в top500 уже есть IBM Sequoia (2012) — 16,32 Пфлопс
Так за сколько эту задачу решит самый мощный на данный момент суперкомпьютер в мире?
1,55112E+25 / 1,632E+16 = 950441791 секунд
Или 950441791 / 60 / 60 / 24 / 365 = 30 лет
Эх… многовато.
Ну ничего, производительность растет быстро.
По личному мнению Ректора МГУ Садовничего, высказанного в октябре 2011 года, в МГУ:
через пару лет (к 2014 году) может появиться суперкомпьютер производительностью до 10 Эфлопс
1,55112E+25 / 1E+19 = 1551121 секунд
Или 1551121 / 60 / 60 / 24 = 17,9527894 дней
Жаль, что начальник не хочет ждать пару лет, да и доступ к такому суперкомпьютеру маленькой фирме не дадут.
Утром пришли на работу сообщить печальную новость начальнику.
Начальник опережает своей новостью — появилось ещё 2 клиента.
27! = 10 888 869 450 418 352 160 768 000 000
Из-за 2 новых клиентов считать 10,88 октиллионов вариантов (10,88*1027)
Это же на 10 873 358 240 375 021 174 784 000 000 (10,87 октиллионов) больше чем при 25 клиентах.
А почему так много?
Снова пошли гуглить, теперь про факториал.
Факториал является чрезвычайно быстро растущей функцией. Он растёт быстрее, чем многочлен любой степени (полином), и быстрее, чем экспоненциальная функция.
Следовательно, временная сложность алгоритма полного перебора для этой задачи обладает эффектом комбинаторного взрыва.
| 5! | 10! | 15! | 20! | 25! | 30! | 35! | 40! | 45! | 50! |
| ~102 | ~106 | ~1012 | ~1018 | ~1025 | ~1032 | ~1040 | ~1047 | ~1056 | ~1064 |
Так это же даже суперкомпьютеру будущего надо будет считать 1,08888694504183E+28 / 1E+19 = 1088886945 секунд. Или 1088886945 / 60 / 60 / 24 / 365 = 34 года. Добавили 2-х клиентов, и 17 дней превратились в 34 года.
Идем к начальнику с повинной — не можем решить эту задачу, видимо, слишком тупы :(
Полным перебором на современных настольных ПК можно решать задачи порядка 17 точек на одну машину.
Вывод
Для малых размерностей полный перебор это реальность, а для больших — миф, т.к. точные методы имеют экспоненциальную временную сложность. Для решения задач больших размерностей существуют лишь эвристические (приближенные) методы решения.
Автор: Glonassova
