Романтика искусственного интеллекта. В. В. Потопахин
Читать онлайн книгу.
куча, а оставшиеся вне сочетания камни – другая. Для каждой полученной таким образом пары определим разницу в весе и выберем из всех пар ту, для которой разница минимальна.
Проблема в том, что этот алгоритм переборный. А количество всех возможных сочетаний из N элементов равно 2N. То есть даже при очень небольшой исходной куче, например в 100 камней, общее количество сочетаний 2100. И получается так, что решение есть и его как бы нет. Дождаться, когда компьютер его обнаружит, человеческой жизни не хватит. А теперь давайте откажемся от желания найти идеальное решение. Пусть нам будет достаточно решения хорошего. Тогда возможен такой алгоритм:
• Упорядочим исходную кучу камней в порядке убывания веса.
• Пока в исходной куче камней есть хотя бы один камень, делаем:
– берем очередной камень;
– если правая куча тяжелее левой, то кладем очередной камень в левую кучу, иначе кладем его в правую.
Проиллюстрируем алгоритм примером. Пусть исходная куча содержит такие камни: (9, 15, 1, 1, 7, 4).
После упорядочивания массив примет такой вид: 15, 9, 7, 4, 1, 1.
Шаг 1: Правая – 15; Левая – 0; Исходная 9, 7, 4, 1, 1.
Шаг 2: Правая – 15; Левая – 9; Исходная 7, 4, 1, 1.
Шаг 3: Правая – 15; Левая – 9 + 7 = 16; Исходная 4, 1, 1.
Шаг 4: Правая – 15 + 4 = 19; Левая – 9 + 7 = 16; Исходная 1, 1.
Шаг 5: Правая – 15 + 4 = 19; Левая – 9 + 7 + 1 = 17; Исходная 1.
Шаг 6: Правая – 15 + 4 = 19; Левая – 9 + 7 + 1 + 1 = 18; Исходная – Пусто.
Заметим, что за шесть шагов было найдено идеальное решение. А алгоритм полного перебора отработал бы 26 = 64 варианта. Вот что такое эвристический алгоритм. Его суть в том, что принимается допущение, которое не обязательно верно во всех случаях жизни, но выглядит вполне правдоподобно. Например, рыбак, выбирая место для ловли, может рассуждать так: «Вон там я вижу омут. В омуте может водиться крупная рыба. Попробую я, однако, порыбачить там». Конечно, рыбак может и ошибаться. В этой реке вообще может рыбы не быть. Но предположение, что в омуте она есть, выглядит разумно, и это эвристическое допущение.
Эвристика создает качественно новые возможности для разработки эффективных алгоритмов, вводя в наш инструментарий такую вещь, как опыт
Эвристика все меняет радикально. Классический алгоритм принимает во внимание только входные данные, и если они такие же, как и в предыдущем запуске, то и ответ будет тем же. Эвристический алгоритм, кроме входных данных, имеет возможность оценивать опыт. В примере с рыбаком это работает так: «Я имею перед собой реку, в ней есть отмель и есть омут (это примерно так, как выглядит на рис. 1.6). Я уже десять раз встречал такую ситуацию и восемь раз из десяти был успешен, порыбачив в омуте. Значит, есть смысл попробовать еще раз».
Рис. 1.6. Эвристический рыбак
Заметим, что для нашего рыбака первая река с омутом и отмелью не несет в себе никакой дополнительной информации. Но уже первый заход создает новую