Быстрое решение проблем с помощью эвристического поиска на языке Java

Познакомьтесь с реализацией популярного алгоритма поиска для искусственного интеллекта на языке Java

Познакомьтесь с областью эвристического поиска и его применением к искусственному интеллекту. Авторы этой статьи рассказывают, как они пришли к успешной реализации самого распространенного алгоритма эвристического поиска на языке Java™. Их решение использует отличную от Java Collections инфраструктуру и оптимальные методики, призванные исключить чрезмерный сбор мусора.

Мэтью Хейтем, старший программист, IBM

Matthew Hatem photoМэтью Хейтем (Matthew Hatem) — аспирант Нью-Хэмпширского университета. Его исследования охватывают алгоритмы и приложения эвристического поиска в параллельной и внешней памяти. Его работа была опубликована в материалах Ассоциации по продвижению искусственного интеллекта и материалах Симпозиума по комбинаторному поиску. Помимо этого, он является старшим программистом компании IBM и в настоящее время работает в команде Watson Solutions. Ранее он принимал участие в разработке различных продуктов Lotus и в деятельности eclipse.org.



Этан Бернс, программист, Google

Ethan Burns photoЭтан Бёрнс (Ethan Burns) — программист компании Google, обладатель степени PhD Нью-Хэмпширского университета. Принимал участие в различных проектах, включая модуль ядра iSCSI Linux, параллелизацию контролёра макетов SPIN, параллельный эвристический поиск и автоматическое планирование, методы планирования для робототехники, и алгоритмы эвристического поиска в условиях дефицита времени. Отмечен мемориальной премией Ричарда Личака (Richard Lyczak) для преподавателей за 2007 г., премией лучшему участнику Симпозиума по комбинаторному поиску в 2012 г. и годовой стипендией UNH за 2012–2013 гг.



Уилер Рамл, доцент, University of New Hampshire

Wheeler Ruml photoУилер Рамл (Wheeler Ruml) — доцент информатики и руководитель Группы искусственного интеллекта Нью-Хэмпширского университета. Является соучредителем Международного симпозиума по комбинаторному поиску и сопредседателем Конференции ICAPS 2014. Был избран членом комитета информатики DARPA, удостоен премии NSF CAREER и премии Выдающийся доцент UNH. До прихода в UNH руководил в исследовательском центре Xerox PARC группой, которая использовала методы искусственного интеллекта для создания самого быстрого в мире принтера. В 2002 году получил степень PhD Гарвардского университета.



18.10.2013

Решение проблем путём поиска в пространстве имеющихся решений — важнейший метод систем искусственного интеллекта. Этот метод называется поиском в пространстве состояний. Эвристический поиск является разновидностью поиска в пространстве состояний; в нем для более эффективного поиска решения используется знание проблемы. Эвристический поиск успешно применяется во многих областях. В этой статье мы познакомим вас с эвристическим поиском и представим реализацию алгоритма A* — самого распространённого алгоритма эвристического поиска — на языке программирования Java. Алгоритмы эвристического поиска предъявляют высокие требования к вычислительным ресурсам и объёму памяти. Кроме того, мы покажем, как мы улучшили свою реализацию на языке Java, исключив чрезмерный сбор мусора и использовав высокопроизводительную среду, отличную от Java Collections Framework (JCF). Весь код для этой статьи можно скачать здесь.

Эвристический поиск

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

Для перемещения по графу часто используются такие популярные алгоритмы, как поиск в глубину и поиск в ширину. Но эти алгоритмы являются неосведомлёнными о структуре задачи и зачастую сильно ограничены размером проблемы, которую они способны решить. Кроме того, поиск в глубину не гарантирует отыскания оптимального решения (а в некоторых случаях вообще любого решения), а поиск в ширину гарантирует отыскание оптимального решения лишь в определенных ситуациях. В противоположность этому, эвристический поиск относится к осведомлённым методам поиска, которые используют для более эффективного поиска решения закодированную в эвристику информацию о проблеме. Эвристический поиск позволяет решить многие сложные проблемы, недоступные неосведомлённым алгоритмам.

Популярной сферой применения эвристического поиска является поиск маршрутов в видеоиграх, но он может применяться и для решения более сложных проблем. Победитель соревнования самоуправляемых автомобилей DARPA Urban Challenge в 2007 году использовал эвристический поиск для отыскания наиболее гладкого и прямого маршрута (см. раздел Ресурсы). Кроме того, эвристический поиск успешно применяется для обработки естественных языков, где он используется для синтаксического анализа текста и пакетного декодирования в процессе распознания речи. Помимо этого, он применяется в робототехнике и биоинформатике. Эвристический поиск позволяет решить хорошо изученную проблему теории информации — проблему совмещения нескольких последовательностей (MSA), и делает это быстрее и с меньшим расходом памяти, чем классический подход динамического программирования.

Реализация эвристического подхода на языке Java

Язык программирования Java редко используется для реализации эвристического поиска в связи с присущей ему требовательностью к памяти и вычислительным ресурсам. Зачастую, из соображений производительности, для этой цели предпочитают C/C++. Однако мы продемонстрировали, что Java вполне пригоден для реализации эвристического поиска. Сначала мы показали, что классическая реализация алгоритма A* действительно работает медленно и интенсивно поглощает имеющуюся память при решении эталонного набора популярных задач. Мы решили эти проблемы, пересмотрев некоторые критические детали реализации и воспользовавшись альтернативной инфраструктурой вместо JCF.

Большая часть этой работы является продолжением работы, опубликованной в академической статье, написанной теми же авторами (см. раздел Ресурсы). И хотя исходная работа концентрируется на языке C/C++ , здесь мы показываем, что большая часть этих идей применима и к языку Java.


Поиск в ширину

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

Целью поиска в ширину является создание последовательности операций, которая переводила бы агент из исходного состояния в конечное. Начиная с исходного состояния, поиск в ширину в первую очередь посещает недавно созданные состояния. К каждому посещённому состоянию применяются все доступные операции, что создаёт новые состояния, которые добавляются к списку непосещённых состояний (называемых также границей поиска). Процесс посещения состояния и создания всех его последующих состояний обычно называется расширением состояния.

Эту процедуру можно представить в виде создания дерева: корневой узел дерева представляет исходное состояние, а дочерние узлы соединяются ветвями, представляющими операции, которые использовались для их создания. Такое дерево поиска показано на рисунке 1. Белые круги соответствуют узлам на границе поиска. Серые круги соответствуют узлам, которые подверглись расширению.

Рисунок 1. Поиск в двоичном дереве в ширину
Illustration of a search tree in breadth-first search. The tree's root node represents the initial state, and child nodes are connected by edges that represent the actions that were used to generate them. The white (empty) circles represent nodes in the frontier of the search. The grey (numbered) circles represent the nodes that have been expanded.

Каждый узел дерева поиска соответствует некоторому состоянию, при этом два уникальных узла могут соответствовать одному и тому же состоянию. Например, узел на другой глубине дерева поиска может соответствовать тому же состоянию, что и у другого расположенного выше узла. Такие дублирующиеся узлы соответствуют двум разным путям достижения одного и того же состояния в проблеме поиска. Дубликаты могут создавать проблемы, поэтому необходимо запоминать все посещённые узлы. В листинге 1 показан псевдокод поиска в ширину:

Листинг 1. Псевдокод поиска в ширину
функция: ПОИСК-В-ШИРИНУ(исходный)
открытые ← {исходный}
закрытые ← 0
цикл:
     если ПУСТ(открытые), то возвращаем ошибку
     узел ← С НАИМЕНЬШЕЙ ГЛУБИНОЙ(открытые)
     закрытые ← ДОБАВИТЬ(закрытые, узел)
     для каждой операции в ОПЕРАЦИИ(узел)
          последующий ← ПРИМЕНИТЬ(операция, узел)
          если последующий в закрытых, то продолжить
          если ЦЕЛЬ(последующий), то возвращаем РЕШЕНИЕ (узел)
          открытые ← ВСТАВИТЬ(открытые, последующий)

В листинге 1 мы храним границу поиска в списке, который назвали открытые (строка 2). Посещённые узлы хранятся в списке, который мы назвали закрытые (строка 3); этот список необходим для того, чтобы не посещать дважды один и тот же узел. Узел добавляется к границе лишь в том случае, если он отсутствует в списке закрытых. Цикл поиска продолжается до тех пор, пока список открытых узлов не опустеет, или пока не будет достигнута цель.

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

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

Алгоритм Дейкстры представляет собой расширение поиска в ширину, которое сортирует узлы на границе поиска (список открытых узлов) по весу достижения узла из исходного состояния. Этот алгоритм гарантирует отыскание оптимального решения в случае равного и неравного веса операций (если считать, что вес является неотрицательным значением). Тем не менее он требует посетить все узлы, вес которых меньше оптимального решения, поэтому его применимость ограничена небольшими задачами. В следующем разделе описан алгоритм, способный решать большие задачи, существенно сокращая число узлов, которые необходимо посетить для поиска оптимального решения.


Алгоритм поиска A*

Алгоритм A* (и некоторые его вариации) является одним из самых распространенных алгоритмов эвристического поиска. A* можно считать расширенной версией алгоритма Дейкстры, который использует знание задачи для сокращения объёма вычислений, необходимых для поиска решения, гарантируя при этом отыскание оптимального решения. Алгоритмы A* и Дейкстры являются классическими примерами алгоритмов перемещения в порядке ухудшения. Таким названием они обязаны тому, что в первую очередь посещаются наиболее перспективные узлы — узлы, которые кажутся кратчайшим путём к цели. Для многих проблем критически важно найти оптимальное решение, и именно это придает такую важность алгоритмам, подобным алгоритму A*.

Главное отличие алгоритма A* от других алгоритмов перемещения по графу — применение эвристики. Эвристика — это некоторые знания о задаче, которые помогают принять наилучшее решение. В контексте алгоритмов поиска эвристика имеет вполне определенное значение: это функция, которая оценивает вес, оставшийся до достижения цели от некоторого конкретного узла. Алгоритм A* может использовать эвристику для исключения лишних вычислений, определяя узел, который выглядит самым перспективным для посещения. A* пытается не посещать узлы графа, которые скорее всего не приведут к оптимальному решению, и может отыскивать решения быстро и с меньшими затратами памяти, чем менее информированные алгоритмы.

Для определения самого перспективного узла алгоритм A* вычисляет для каждого узла некоторое значение (мы будет называть его значением f) и сортирует список открытых узлов по этому значению. Значение f вычисляется по двум другим значениям узла — значению g и значению h. Значение g — это суммарный вес всех операций, необходимых для достижения узла из исходного состояния. Значение h — это прогнозируемый вес для достижения цели из узла. В эвристическом поиске эта оценка является эвристической. Узлы с минимальными значениями f считаются самыми перспективными для посещения. Описанная процедура поиска показана на рисунке 2:

Рисунок 2. Порядок поиска алгоритма A*, определяемый значениями f
Diagram of A* search order on f values, with white nodes marked with their f value

В примере на рисунке 2 граница состоит из трёх узлов. Два из них имеют значение f, равное 5, а один — равное 3. Следующим разворачивается узел с минимальным значением f, и этот узел приводит прямо к цели. Это избавляет алгоритм A* от посещения поддеревьев под двумя другими узлами, как показано на рисунке 3. В результате алгоритм A* оказывается значительно эффективней таких алгоритмов, как поиск в ширину.

Рисунок 3. Алгоритму A* не нужно посещать поддеревья под узлами с большими значениями f
Diagram showing that A* doesn't need to visit the subtrees under nodes with higher f values

Если используемая алгоритмом A* эвристика приемлема, A* посещает только узлы, необходимые для поиска оптимального решения. Именно этому A* обязан своей популярностью. Ни один другой алгоритм не гарантирует отыскания оптимального решения при посещении меньшего числа узлов, чем A* с приемлемой эвристикой. Чтобы эвристическая оценка была приемлемой, она должна представлять собой оценку снизу: значение меньшее или равное весу достижения цели. Если эвристика отвечает дополнительному требованию —согласованности— то каждое состояние генерируется при проходе по оптимальному маршруту только один раз, и алгоритм может эффективнее справляться с дубликатами.

Как и описанный в предыдущем разделе поиск в ширину, алгоритм A* хранит информацию о двух структурах данных. Созданные, но ещё не посещённые узлы заносятся в список открытых узлов, а все канонические уже посещенные узлы — в список закрытых узлов. Реализация таких структур и способ их применения сильно влияет на производительность. Более детально мы изучим этот вопрос в следующем разделе. В листинге 2 показан полный псевдокод классического поиска по алгоритму A*:

Листинг 2. Псевдокод поиска по алгоритму A*
функция: A*-ПОИСК(исходный)
открытые ← {исходный}
закрытые ← 0
цикл:
     если ПУСТ(открытые), то возвращаем ошибку
     узел ← ЛУЧШИЙ(открытые)
     если ЦЕЛЬ(узел), то возвращаем РЕШЕНИЕ(узел)
     закрытые ← ДОБАВИТЬ(закрытые, узел)
     для каждой операции в ОПЕРАЦИИ(узел)
          последующий ← ПРИМЕНИТЬ(операция, узел)
          если последующий в открытых или последующий в закрытых
              УЛУЧШИТЬ(последующий)
иначе
              открытые ← ВСТАВИТЬ(открытые, последующий)

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

Этот псевдокод можно упростить, сделав два предположения о решаемой проблеме: мы будем считать, что все операции имеют равный вес и что мы имеем приемлемую и согласованную эвристику. Поскольку эвристика согласована и все операции обладают одинаковым весом, мы никогда не посетим узел повторно по лучшему маршруту. Кроме того, было доказано, что в некоторых ситуациях эффективнее иметь дублирующиеся узлы в открытом списке, чем проверять дубликаты при каждом создании нового узла. Следовательно, мы можем упростить реализацию, добавляя все новые последующие узлы в список открытых узлов независимо от того, посещались ли они раньше. Мы упростим псевдокод, объединив последние четыре строки листинга 2 в одну. Но нам ещё нужно избавиться от циклов, поэтому мы должны проверить дубликаты до расширения узла. Мы можем опустить детали функции УЛУЧШИТЬ, поскольку в упрощенной версии она уже не нужна. Упрощенный псевдокод показан в листинге 3:

Листинг 3. Упрощенный псевдокод поиска по алгоритму A*
функция: A*-ПОИСК(исходный)
открытые ← {исходный}
закрытые ← 0
цикл:
     если ПУСТ(открытые), то возвращаем ошибку
     узел ← ЛУЧШИЙ(открытые)
     если узел закрыт, то продолжить
     если ЦЕЛЬ(узел), то возвращаем РЕШЕНИЕ(узел)
     закрытые ← ДОБАВИТЬ(закрытые, узел)
     для каждой операции в ОПЕРАЦИИ(узел)
          последующий ← ПРИМЕНИТЬ(операция, узел)
          открытые ← ВСТАВИТЬ(открытые, последующий)

Классическая реализация алгоритма A* на языке Java

В этом разделе мы рассмотрим классическую реализацию алгоритма A* на языке Java, основанную на упрощённом псевдокоде, приведённом в листинге 3. Далее вы увидите, что эта реализация не способна пройти стандартный тест скорости эвристического поиска с ограничением памяти до 30 ГБ.

Мы хотим сделать эту реализацию максимально универсальной, поэтому начнём с определения некоторых интерфейсов для абстрагирования задачи, которую будет решать алгоритм A*. Любая задача, которую мы хотим решить с помощью алгоритма A*, должна реализовывать интерфейс Domain. Интерфейс Domain предлагает методы для:

  • опроса исходного состояния;
  • опроса операций, применимых к состоянию;
  • вычисления эвристического значения состояния;
  • создания последующих состояний.

Полный код интерфейса Domain показан в листинге 4:

Листинг 4. Исходный код интерфейса Domain на языке Java
public interface Domain<T> {
  public T initial();
  public int h(T state);
  public boolean isGoal(T state);
  public int numActions(T state);
  public int nthAction(T state, int nth);
  public Edge<T> apply (T state, int op);
  public T copy(T state);   
}

Алгоритм поиска A* генерирует объекты ветвей и узлов дерева поиска, поэтому нам понадобятся классы Edge (ветвь) и Node (узел). Каждый узел содержит четыре поля: состояние, представленное узлом; ссылка на родительский узел; значения g и h для данного узла. Полный код класса Node приведен в листинге 5:

Листинг 5. Исходный код класса Node на языке Java
class Node<T> {
  final int f, g, pop;
  final Node parent;
  final T state;
  private Node (T state, Node parent, int cost, int pop) {
    this.g = (parent != null) ? parent.g+cost : cost;
    this.f = g + domain.h(state);
    this.pop = pop;
    this.parent = parent;
    this.state = state;
  } 
}

Каждая ветвь имеет три поля: вес ветви; операция, используемая для создания последующего узла ветви; операция, используемая для создания родительского узла ветви. Полный код класса Edge приведен в листинге 6:

Листинг 6. Исходный код класса Edge на языке Java
public class Edge<T> {
  public int cost; 
  public int action;   
  public int parentAction;    
  public Edge(int cost, int action, int parentAction) { 
    this.cost = cost;
    this.action = action;
    this.parentAction = parentAction;
  }  
}

Сам алгоритм A* будет реализовывать интерфейс SearchAlgorithm и требует только интерфейсов Domain и Edge. Интерфейс SearchAlgorithm предлагает лишь один метод для поиска с указанным исходным состоянием. Метод search() возвращает экземпляр класса SearchResult. Класс SearchResult предоставляет статистическую информацию о поиске. Определение интерфейса SearchAlgorithm приведено в листинге 7:

Листинг 7. Исходный код интерфейса SearchAlgorithm на языке Java
 public interface SearchAlgorithm<T> {
  public SearchResult<T> search(T state);  
}

Важной деталью реализации является выбор структур данных для списков открытых и закрытых узлов. Для реализации списка открытых узлов мы используем алгоритм PriorityQueue языка Java. PriorityQueue является реализацией сбалансированной двоичной кучи со временем постановки элементов в очередь и извлечения из очереди O(log n), линейным временем проверки присутствия элемента в очереди и постоянным временем доступа к заголовку очереди. Двоичная куча является популярной структурой для реализации поиска открытых узлов. Позже вы увидите, что в некоторых ситуациях список открытых узлов можно реализовать с помощью более эффективной структуры данных, получившей название блочная очередь с приоритетами (bucket priority queue).

Чтобы PriorityQueue мог корректно сортировать узлы, мы должны реализовать интерфейс Comparator. Для алгоритма A* необходимо сортировать узлы по их значениям f. В ситуациях, когда несколько узлов имеют одинаковые значения f, простым методом оптимизации является разрыв связей путём выбора узла с максимальным значением g. Задумайтесь, почему этот способ может улучшить производительность алгоритма A*. (Подсказка: h является оцениваемым значением, а g— нет). Полный код реализации Comparator приведён в листинге 8:

Листинг 8. Исходный код класса NodeComparator на языке Java
class NodeComparator implements Comparator<Node> {
  public int compare(Node a, Node b) {
    if (a.f == b.f) { 
      return b.g - a.g;
    }
    else {
      return a.f - b.f;
    }
  }    
}

Другая структура данных нужна для реализации списка закрытых узлов. Очевидным выбором для этого является класс HashMap языка Java. Класс HashMap является реализацией хеш-таблицы с ожидаемым постоянным временем извлечения и добавления элементов при условии использования хорошей хеш-функции. Нам придется переписать методы hashcode() и equals() этого класса, ответственные за реализацию состояния домена. Эту реализацию мы рассмотрим в следующем разделе.

Наконец, нам нужно реализовать интерфейс SearchAlgorithm. Для этого мы реализуем метод search() с помощью псевдокода, приведённого в листинге 3. Полный код метода search() алгоритма A* приведён в листинге 9:

Листинг 9. Исходный код метода search()алгоритма A* на языке Java
 public SearchResult<T> search(T init) {
  Node initNode = new Node(init, null, 0, 0 -1);    
  open.add(initNode);
  while (!open.isEmpty() && path.isEmpty()) {  
    Node n = open.poll();
    if (closed.containsKey(n.state)) continue;
    if (domain.isGoal(n.state)) {
      for (Node p = n; p != null; p = p.parent)
        path.add(p.state);
      break;
    }
    closed.put(n.state, n);
    for (int i = 0; i < domain.numActions(n.state); i++) {
      int op = domain.nthAction(n.state, i);
      if (op == n.pop) continue;
      T successor = domain.copy(n.state);
      Edge<T> edge = domain.apply(successor, op);      
      Node node = new Node(successor, n, edge.cost, edge.pop);
      open.add(node);
    }
  }
  return new SearchResult<T>(path, expanded, generated);
}

Для испытания реализации алгоритма A* нам нужна какая-либо задача. В следующем разделе мы опишем популярный метод оценки алгоритмов эвристического поиска. Все операции в этой ситуации имеют одинаковый вес, и используемая эвристика является приемлемой, поэтому нашей упрощённой реализации оказывается вполне достаточно.


Измерение скорости на головоломке 15

Для этой статьи мы используем популярную головоломку — т.н. игру в 15. Эта простая игра обладает вполне понятными свойствами и широко применяется в качестве стандартного теста скорости алгоритмов эвристического поиска. (Некоторые исследователи искусственного интеллекта называют эту головоломку «дрозофилой»). Игра в 15 является разновидностью головоломок с перемещаемыми плитками, в которой на поле размером 4x4 расположены 15 плиток. Плитки имеют 16 возможных положений, причём одно положение всегда свободно. Плитки, соседствующие со свободным местом, можно сдвигать из одного положения в другое. Задача состоит в том, чтобы переместить плитки в целевую конфигурацию. На рисунке 4 показана головоломка с произвольной конфигурацией плиток:

Рисунок 4. Произвольная конфигурация игры в 15
An illustration of a random configuration and the goal configuration of the 15 puzzle

На рисунке 5 показана целевая конфигурация игры:

Рисунок 5. Целевая конфигурация игры в 15
An illustration of the goal configuration of the 15 puzzle. The tiles are in numerical order from 1 to 15, starting in the upper left position, with the blank tile in the lower-right corner.

Для оценки скорости алгоритма эвристического поиска мы будем искать путь от начальной конфигурации до целевой конфигурации с минимальным числом ходов.

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

Возможно, сначала это не покажется столь очевидным, но мы можем представить игру в 15 графом, описав каждую возможную конфигурацию соответствующим узлом графа. Ветвь соединяет два узла в том случае, если существует операция, преобразующая одну конфигурацию в другую. Операция в данной ситуации сводится к перемещению плитки на свободное место. Этот граф поиска показан на рисунке 6:

Рисунок 6. Граф поиска в пространстве состояний для игры в 15
Illustration of a state-space search graph for the 15 puzzle

Существует 16! возможных способов размещения 15 плиток на игровом поле, но на самом деле возможных конфигураций (состояний) игры в 15 «всего» 16!/2 = 10 461 394 944 000. Это связано с тем, что физические ограничения игры в 15 позволяют достичь ровно половины всех возможных конфигураций. Чтобы осознать размер этого пространства состояний, представьте, что вы можете описать состояние всего одним байтом (что на самом деле невозможно). В этом случае для сохранения всего пространства состояний нам понадобится более 10 ТБ памяти. Это значительно превышает предельный объем памяти современных компьютеров. Мы покажем, как эвристический поиск может оптимально решить эту головоломку, посещая лишь малую часть пространства состояний.


Проведение экспериментов

В наших экспериментах мы будем использовать хорошо известный набор начальных конфигураций игры в 15, получивший название 100 комбинаций Корфа. Этот набор назван в честь Ричарда Е. Корфа (Richard E. Korf), который опубликовал первые результаты, показывающие, что игру в 15 можно решить с помощью разновидности алгоритма A* с итерационным углублением, который называется IDA*. С тех пор как эти результаты были опубликованы, использованные Корфом 100 случайных конфигураций стали часто применяться в бесчисленных экспериментах по эвристическому поиску. Мы же оптимизируем свою реализацию так, чтобы метод итерационного углубления оказался ненужным.

В каждый момент времени мы будем решать одну начальную конфигурацию. Каждая начальная конфигурация сохраняется в отдельном текстовом файле. Для запуска эксперимента местоположение файла указывается в аргументах командной строки. Нашей программе на Java нужна точка входа, которая будет обрабатывать аргументы командной строки, генерировать экземпляр проблемы и запускать поиск по алгоритму A*. Мы назовём класс, описывающий эту точку входа, TileSolver.

В конце каждого запуска на стандартное устройство вывода выводятся статистические показатели поиска. Самым интересным статистическим показателем для нас является время поиска. Мы суммируем время исполнения каждого запуска и получаем общее время исполнения теста.

Исходный код для этой статьи содержит операцию Ant для автоматизации экспериментов. Полный эксперимент можно запустить командой:

ant TileSolver.korf100 -Dalgorithm="efficient"

Выбор алгоритма задается значением параметра efficient (эффективный) или textbook (классический).

Кроме того, мы указываем цель Ant для запуска одного экземпляра. Например:

ant TileSolver -Dinstance="12" -Dalgorithm="textbook"

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

ant TileSolver.korf97 -Dalgorithm="textbook"

Может оказаться, что вашему компьютеру не хватит памяти для проведения полного эксперимента с классической реализацией. Чтобы избежать подкачки, необходимо тщательно ограничить объём памяти, доступный процессу Java. Если вы проводите этот эксперимент в Linux, можете с помощью команды оболочки ulimit установить предельный объём памяти для активной оболочки.

Первая попытка: неудача

В таблице 1 показаны результаты всех применённых нами методов. Результаты классической реализации алгоритма A* приведены в первой строке. (Упакованные состояния и HPPC, а также относящиеся к ним результаты мы опишем в последующих разделах).

Таблица 1. Результаты решения 97 из 100 конфигураций Корфа для игры в 15 с помощью трёх вариантов алгоритма A*
АлгоритмМакс. расход памятиОбщее время работы
Классический25 ГБ1,846 c
Упакованные состояния 11 ГБ1,628 c
HPPC7 ГБ1,084 c

Классическая реализация не смогла решить все экземпляры. Мы не смогли решить три самых сложных экземпляра, а на те экземпляры, которые удалось решить, ушло более 1800 секунд. Не впечатляет, учитывая, что лучшая реализация на C/C++ может решить все 100 экземпляров менее чем за 600 секунд.

Неудача при решении трех самых сложных экземпляров произошла из-за ограничения памяти. В каждой итерации поиска удаление узла из списка открытых узлов и его развертывание обычно приводит к созданию нескольких новых узлов, а с ростом числа узлов растёт и объём необходимой памяти для сохранения списка открытых узлов. Однако такая требовательность к памяти присуща не только нашей реализации; эквивалентная реализация на C/C++ также потерпела бы неудачу.

В своей статье Бёрнс (Burns) с соавторами (см. раздел Ресурсы) показал, что эффективная реализация алгоритма поиска A* на C/C++ может решить этот тест менее чем с 30 ГБ памяти — поэтому мы пока не готовы отказаться от реализации этого алгоритма на Java. Существует ещё два дополнительных метода, обсуждаемых в последующих разделах, которые позволяют эффективнее расходовать память. Результатом является эффективная реализация алгоритма A* на Java, способная быстро решить весь тест.


Упакованные состояния

Исследуя загрузку памяти нашим алгоритмом поиска A* с помощью таких профилировщиков, как VisualVM, мы замечаем, что вся память занята классом Node, а точнее классом TileState. Значит, для уменьшения расхода памяти нужно ещё раз взглянуть на реализацию этих классов.

Каждое состояние головоломки должно содержать положения всех 15 плиток. Для этого мы сохраняем положения всех плиток в массиве из 15 целых чисел. Мы можем представить эти положения более экономно, упаковав их в 64-разрядное целое число (long в языке Java). Когда нам понадобится сохранить узел в списке открытых узлов, мы можем сохранить упакованное представление состояния. Это сэкономит нам 52 байта на узел. Решение самой сложной конфигурации требует сохранения примерно 533 миллионов улов. С помощью упакованных состояний мы экономим более 25 ГБ памяти!

Для сохранения общей природы нашей реализации необходимо расширить интерфейс SearchDomain, дополнив его методами упаковки и распаковки состояний. Перед сохранением узла в открытом списке мы создаём упакованное представление этого состояния и сохраняем его в классе Node, а не в указателе на состояние. Когда нам понадобится создать последующий узел, мы просто распакуем это состояние. Реализация метода pack() показана в листинге 10:

Листинг 10. Исходный код метода pack() на языке Java
public long pack(TileState s) {
  long word = 0;
  s.tiles[s.blank] = 0;
  for (int i = 0; i < Ntiles; i++)
    word = (word << 4) | s.tiles[i];
  return word;
}

Реализация метода unpack() показана в листинге 11:

Листинг 11. Исходный код метода unpack() на языке Java
public void unpack(long packed, TileState state) {
  state.h = 0;
  state.blank = -1;
  for (int i = numTiles - 1; i >= 0; i--) {
    int t = (int) packed & 0xF;
    packed >>= 4;
    state.tiles[i] = t;
    if (t == 0)
      state.blank = i;
    else
      state.h += md[t][i];
  }
}

Поскольку упакованное представление является канонической формой состояния, мы можем сохранить упакованное представление в списке закрытых узлов. Мы не можем просто сохранить примитивы в классе HashMap. Их нужно упаковать в экземпляр класса Long.

Результаты эксперимента с упакованным представлением состояний показаны во второй строке таблицы 1. Используя упакованное представление состояния, мы сокращаем объем используемой памяти на 55 процентов и немного ускоряем работу, но по-прежнему не можем решить весь тест.

Проблема с Java Collections Framework

Если вам кажется, что упаковка каждого упакованного состояния в экземпляр Long связана с большими накладными расходами, то вы совершенно правы. Эта операция расходует много памяти и может потребовать чрезмерного сбора мусора. В JDK 1.5 появилась поддержка автоупаковки, которая автоматически преобразует значения примитивов в их объектное представление (long в Long) и наоборот. В больших коллекциях эти преобразования могут потреблять много памяти и ресурсов ЦП.

Кроме того, в JDK 1.5 появились обобщённые типы Java, которые часто сравнивают с шаблонами C++. Бёрнс с соавторами показал, что шаблоны C++ дают существенный выигрыш производительности при реализации эвристического поиска. Обобщенные типы такого преимущества не дают. Обобщённые типы реализуются с помощью затирания типов, которое во время компиляции удаляет всю информацию о типах. В результате возникает необходимость проверки информации о типах во время исполнения, что может снизить скорость работы для больших коллекций.

Ещё раз о памяти

From Java code to Java heap

Реализация класса HashMap выявила ещё один перерасход памяти. HashMap сохраняет массив экземпляров внутреннего класса HashMap$Entry. Каждый раз, когда мы добавляем элемент в HashMap, в массив добавляется новая запись. Реализация этого класса обычно содержит три ссылки на объект и одну ссылку на 32-разрядное целое число, что в сумме даёт 32 байта на запись. Если список закрытых узлов содержит 533 миллиона узлов, расход памяти превысит 15 ГБ.

Затем мы представили альтернативный вариант класса HashMap, который позволил дополнительно сократить расход памяти, непосредственно сохраняя примитивы.


Высокопроизводительные примитивы

Поскольку теперь мы сохраняем примитивы только в списке закрытых узлов, мы можем воспользоваться инфраструктурой High Performance Primitive Collections (HPPC). HPPC представляет собой альтернативную инфраструктуру коллекций, которая позволяет непосредственно сохранять значения примитивов без накладных расходов, присущих JCF (см. раздел Ресурсы). В отличие от обобщённых типов Java, в HPPC используется метод, подобный шаблонам C++, когда отдельные реализации каждого класса коллекции и типа примитива Java обобщаются во время компиляции. Это исключает необходимость упаковки значений примитивов в такие классы, как Long и Integer, при сохранении их в коллекции. В качестве побочного эффекта это позволяет избежать многочисленных приведений типов, необходимых в JCF.

Существуют и другие альтернативные JCF способы сохранения значений примитивов. Двумя великолепными примерами являются Apache Commons Primitive Collections и fastutils. Однако мы считаем, что инфраструктура HPPC обладает одним существенным преимуществом для реализации высокопроизводительных алгоритмов: она открывает внутреннее хранилище данных для всех классов коллекций. Прямой доступ к этому хранилищу открывает множество возможностей для оптимизации. Например, если мы хотим сохранить на диске список открытых или закрытых узлов, то эффективнее сделать это с помощью прямого доступа к нижележащим массивам данных, чем с помощью косвенного доступа через итератор.

Мы можем изменить реализацию алгоритма A* так, чтобы использовать для списка закрытых узлов экземпляр класса LongOpenHashSet. Необходимые изменения очень просты. Нам больше не нужно переопределять методы hashcode и equals класса состояния, поскольку теперь мы сохраняем только значения примитивов. Список закрытых узлов представляет собой набор (не содержащий дублирующихся элементов), поэтому нам достаточно сохранять значения, а не пары ключ/значение.

В третьей строке таблицы 1 показаны результаты эксперимента с HPPC вместо JCF. С HPPC объём используемой памяти снизился на 27 процентов, а время исполнения — на 33 процента.

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

Таблица 2. Результаты решения всех 100 экземпляров из 100 конфигураций Корфа с помощью трёх вариантов алгоритма A*
АлгоритмМакс. расход памятиОбщее время работы
HPPC30 ГБ1,892 c
Вложенная блочная очередь30 ГБ1,090 c
Устранение сбора мусора30 ГБ925 c

С помощью HPPC мы смогли решить все 100 экземпляров с 30 ГБ памяти, но на это ушло более 1800 секунд. Другие результаты, приведённые в таблице 2, показывают меры, которые мы использовали для ускорения своей реализации за счёт улучшения другой важной информационной структуры — списка открытых узлов.


Проблема с PriorityQueue

Всякий раз при добавлении элемента в список открытых узлов необходима сортировка очереди. На постановку в очередь и удаление из очереди PriorityQueue затрачивает время O(log(n)). Это высокая эффективность для сортировки, но все же не бесплатно, особенно для больших значений n. Вспомните, что для самых проблематичных экземпляров нам пришлось добавить в список открытых узлов более 500 миллионов узлов. Более того, поскольку все операции в нашем тесте имеют равный вес, диапазон возможных значений f невелик. Поэтому выгода от использования PriorityQueue может не стоить связанных с этим накладных расходов.

Одним из альтернативных путей является применение блочной очереди с приоритетами. Предполагая, что вес операций в нашей ситуации попадает в узкий диапазон значений, мы можем определить фиксированный диапазон блоков, по одному блоку на каждое значение f. При создании узла мы просто помещаем его в блок с соответствующим значением f. Когда нам требуется доступ к заголовку очереди, мы просматриваем блоки начиная с минимальных значений f, пока не найдём нужный узел. Такой тип структуры данных называется блочной очередью с приоритетами 1-го уровня и обеспечивает постоянное время занесения в очередь и удаления из очереди. Соответствующая структура данных показана на рисунке 7:

Рисунок 7. Блочная очередь с приоритетами 1-го уровня
Illustration of 1-level bucket priority queue

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

Рисунок 8. Вложенная блочная очередь с приоритетами
Illustration of nested bucket priority queue

Теперь мы можем обновить нашу реализацию алгоритма A*, применив вложенную блочную очередь с приоритетами к списку открытых узлов. Полная реализация вложенной блочной очереди с приоритетами приведена в файле BucketHeap.java, входящем в исходный код для этой статьи (см. раздел Загрузка).

Вторая строка таблицы 2 показывает результаты эксперимента с вложенной блочной очередью с приоритетами. Используя вложенную блочную очередь с приоритетами вместо PriorityQueue, мы улучшили время исполнения почти на 58 процентов, но оно всё ещё превышает 1000 секунд. Для дальнейшего ускорения работы мы можем сделать ещё один простой шаг.


Устранение сбора мусора

Сбор мусора часто считается узким местом языка Java. Существует множество статей, посвященных настройке сбора мусора в JVM (см. раздел Ресурсы), поэтому мы не будем вдаваться в подробности.

Как правило, алгоритм A* генерирует много короткоживущих объектов состояний и ветвей, что порождает большие затраты на сбор мусора. Повторно используя объекты, мы можем сократить требуемый объем сбора мусора. Для этого нужно внести несколько простых изменений. В каждой итерации цикла поиска алгоритма A* мы резервируем новую ветвь и новое состояние (533 миллиона для самой сложной задачи). Вместо того чтобы каждый раз резервировать новые объекты, мы можем повторно использовать одни и те же объекты состояний и ветвей во всех итерациях цикла.

Для многократного использования объектов состояний и ветвей необходимо изменить интерфейс Domain. Вместо метода apply(), возвращающего экземпляр Edge, нужно создать свой собственный экземпляр, который будет изменяться вызовом apply(). Изменения edge при этом будут не инкрементными, поэтому нам не придётся беспокоиться о том, какие значения были сохранены в edge перед передачей его в apply(). Однако изменения, которые выполняет apply() с объектом state, являются инкрементными. Для корректной генерации всех последующих состояний без необходимости копирования состояния нам понадобится способ отмены внесенных изменений. Для этого мы должны расширить интерфейс Domain так, чтобы он содержал метод undo(). Соответствующие изменения интерфейса Domain показаны в листинге 12:

Листинг 12. Обновленный интерфейс Domain
public interface Domain<T> {
  ...
   public void apply(T state, Edge<T> edge, int op);
   public void undo(T state, Edge<T> edge);
  ...  
}

В третьей строке таблицы 2 показаны результаты последнего эксперимента. Повторно используя объекты состояний и ветвей, мы устраняем сбор мусора и сокращаем время исполнения более чем на 15 процентов. С помощью нашей высокоэффективной реализации алгоритма A* мы можем теперь решить весь набор тестов за 925 секунд, израсходовав всего 30 ГБ памяти. Это превосходный результат, учитывая, что реализация на C/C++ тратит на эту работу 540 секунд и требует 27 ГБ памяти. Наша реализация на языке Java всего в 1,7 раз медленней и требует примерно того же объёма памяти.


Заключение

В этой статье мы познакомили вас с эвристическим поиском. Мы представили алгоритм A* и продемонстрировали его классическую реализацию на языке Java. Мы показали, что эта реализация работает медленно и не может решить стандартную тестовую задачу за приемлемое время и с приемлемым объёмом памяти. Мы решили эти проблемы, воспользовавшись инфраструктурой HPPC, применив некоторые методы экономии памяти и исключив ресурсоёмкий сбор мусора. Наша улучшенная реализация смогла решить тестовую проблему с умеренным расходом памяти за приемлемое время, показав, что Java хорошо подходит для реализации алгоритмов эвристического поиска. Кроме того, представленные в этой статье методы можно применять во многих реальных приложениях Java. Например, в некоторых случаях применение HPPC может мгновенно повысить производительность любого приложения Java, сохраняющего большое число значений примитивов.

Благодарности

Мы хотим выразить свою благодарность Национальному научному фонду США (гранты 0812141 и 1150068) и агентству DARPA (грант N10AP20029) за оказанную поддержку, а также Университету Нью-Хэмпшира за предоставление годовой диссертационной стипендии.


Загрузка

ОписаниеИмяРазмер
Пример кодаj-ai-code.zip58 КБ

Ресурсы

Научиться

  • Оригинал статьи: Faster problem solving in Java with heuristic search.
  • Implementing Fast Heuristic Search Code(Реализация быстрого эвристического поиска) (Этан Бёрнс (Ethan Burns) с соавторами, Proceedings of the Fifth Annual Symposium on Combinatorial Search, 2012): научная статья с более подробной информацией о реализации быстрого эвристического поиска.
  • Planning Long Dynamically-Feasible Maneuvers for Autonomous Vehicles (Планирование протяжённых динамически реализуемых манёвров для автономных транспортных средств) (Максим Лихачёв (Maxim Likhachev) и Дейв Фергюсон (Dave Ferguson), International Journal of Robotics Research, август 2009 г.): в этой статье представлены алгоритмы генерации сложных динамически реализуемых манёвров для автономных транспортных средств, перемещающихся с высокими скоростями на большие расстояния.
  • Искусственный интеллект: современный подход (Стюарт Рассел (Stuart Russel) и Питер Норвиг (Peter Norvig), Prentice Hall, 2010): одна из лучших книг по искусственному интеллекту.
  • Игра в пятнадцать (Джерри Слокум (Jerry Slocum) и Дик Сонневелд (Dic Sonneveld), Slocum Puzzle Foundation, 2006): книга, полностью посвященная истории и математическим основам игры в 15.
  • High Performance Primitive Collections: HPPC представляет собой альтернативную высокопроизводительную инфраструктуру коллекций, которую можно использовать для сохранения значений примитивов вместо JCF.
  • Dynamic programming and sequence alignment (Динамическое программирование и совмещение последовательностей) (Пол Д. Рейнерс (Paul D. Reiners), developerWorks, март 2008 г.): прочтите о задаче MSA и о том, как информатика помогает молекулярной биологии.
  • From Java code to Java heap (От Java-кода к Java-куче) (Крис Бейли (Chris Bailey), developerWorks, февраль 2012 г.): узнайте больше об использовании памяти в Java и JCF.
  • Java theory and practice: Garbage collection and performance (Теория и практика Java: Сборка мусора и производительность) (Брайан Гетц (Brian Goetz), developerWorks, январь 2004 г.): узнайте больше о производительности сборщиков мусора в JVM.
  • Раздел технологий Java на портале developerWorks: сотни статей обо всех аспектах программирования на языке Java.

Получить продукты и технологии

  • HPPC: загрузите HPPC.

Обсудить

  • Сообщество developerWorks: связывайтесь с другими пользователями портала developerWorks и знакомьтесь с блогами, форумами, группами и вики-ресурсами разработчиков.

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=948873
ArticleTitle=Быстрое решение проблем с помощью эвристического поиска на языке Java
publish-date=10182013