Романтика искусственного интеллекта. В. В. Потопахин

Читать онлайн.
Название Романтика искусственного интеллекта
Автор произведения В. В. Потопахин
Жанр Прочая образовательная литература
Серия
Издательство Прочая образовательная литература
Год выпуска 2016
isbn 978-5-97060-476-2



Скачать книгу

куча, а оставшиеся вне сочетания камни – другая. Для каждой полученной таким образом пары определим разницу в весе и выберем из всех пар ту, для которой разница минимальна.

      Проблема в том, что этот алгоритм переборный. А количество всех возможных сочетаний из 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. Эвристический рыбак

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