Предположим, что у нас есть 100 млн. долларов, которые нужно вложить в несколько возможных инвестиций. Каждое из этих вложений имеет различную стоимость и различный ожидаемый доход. Мы должны решить, как потратить деньги, чтобы получить максимальную прибыль.
Задачи такого типа называются задачами формирования портфеля. У нас есть несколько позиций (инвестиций), которые должны поместиться в портфель фиксированного размера (100 млн. долларов). Каждая позиция имеет свою прибыльность. Необходимо найти набор позиций, которые помещаются в портфель и дают максимальную прибыль.
Многие из вас скажут, что никакие эвристики тут не нужны, и что вполне можно обойтись полным перебором. Другие заявят, что и полный перебор не нужен, ведь существует метод ветвей и границ. Но как быть, если количество возможных инвестиций 65? Полное дерево решений содержит более 7*10^19 узлов. Предположим, что метод ветвей и границ перебирает десятую часть процента этих узлов, а компьютер проверяет миллион узлов в секунду. В этих условиях для решения задачи потребовалось бы более 2 млн. лет. Именно для таких сложных задач и используются эвристики. Если вам интересно, милости прошу под кат.

Недавно здесь проскакивала тема расписания занятий, и мне захотелось рассказать о своем опыте построения алгоритма составления расписания для ВУЗа, а точнее, больше об эвристике, которую применил.

Иллюстрация Патрика Андерсона, на которой он в 2012 году предположил самый длинный возможный прямой маршрут по морю

В декабре 2012 года в подреддите /r/MapPorn разгорелась любопытная дискуссия. Один из пользователей под ником Kepleronlyknows (Патрик Андерсон) опубликовал изображение с картой мира, на котором изобразил прямой судоходный маршрут. Патрик высказал гипотезу, что это самый длинный прямой маршрут, который можно проложить по воде на нашей планете. Без единого поворота вы проплывёте по прямой около 32 000 километров, стартовав в районе Пакистана и финишировав на Камчатке. Абсолютно прямой маршрут проходит мимо Африки, Южной Америки и через Тихий океан до самой России.

Конечно же, автор произвёл расчёт по интуиции. Он предложил форумчанам проверить его гипотезу и найти более длинный маршрут, если таковой существует. Или попробовать доказать, что именно этот маршрут — самый прямой.