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

Чтение книги онлайн.

СКАЧАТЬ на заре развития компьютерной техники) – вещь, железно приводящая к одному и тому же результату вне зависимости от количества запусков алгоритма. Миллион раз запускаем, миллион раз получаем один и тот же ответ при одних и тех же входных параметрах. А если входных данных не хватает, то алгоритм просто не работает.

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

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

      Прежде чем двигаться дальше, позвольте привести простой пример эвристического алгоритма. В учебниках по программированию можно встретить задачу о двух кучах камней. Ее условие таково: есть одна большая куча камней, возможно разного веса. Требуется раскидать ее на две кучи так, чтобы между ними была минимальная разница в весе.

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

      Проблема в том, что этот алгоритм переборный. А количество всех возможных сочетаний из N элементов равно 2^N. То есть даже при очень небольшой исходной куче, например в 100 камней, общее количество сочетаний 2¹⁰⁰. И получается так, что решение есть и его как бы нет. Дождаться, когда компьютер его обнаружит, человеческой жизни не хватит. А теперь давайте откажемся от желания найти идеальное решение. Пусть нам будет достаточно решения хорошего. Тогда возможен такой алгоритм:

      • Упорядочим исходную кучу камней в порядке убывания веса.

      • Пока в исходной куче камней есть хотя бы один камень, делаем:

      – берем очередной камень;

      – если правая куча тяжелее левой, то кладем очередной камень в левую кучу, иначе кладем его в правую.

      Проиллюстрируем алгоритм примером. Пусть исходная куча содержит такие камни: (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.

      Шаг СКАЧАТЬ