Главная arrow книги arrow Копия Глава 4. arrow Составление допустимых эвристических функций
Составление допустимых эвристических функций

Выбор фишек 1-2-3-4 является довольно произвольным; можно было бы также создать базы данных для фишек 5-6-7-8, 2-4-6-8 и т.д. По данным каждой базы данных формируется допустимая эвристическая функция, а эти эвристические функции можно составлять в общую эвристическую функцию, как было описано выше, применяя их максимальное значение. Составная эвристическая функция такого вида является намного более точной по сравнению с манхэттенским расстоянием; количество узлов, вырабатываемых при решении сформированных случайным образом экземпляров задачи игры в пятнадцать, может быть уменьшено примерно в 1000 раз.

Представляет интерес вопрос о том, можно ли складывать значения эвристических функций, полученных из баз данных 1-2-3-4 и 5-6-7-8, поскольку очевидно, что соответствующие две подзадачи не перекрываются. Будет ли при этом все еще получена допустимая эвристическая функция? Ответ на этот вопрос является отрицательным, поскольку в решениях подзадачи 1-2-3-4 и подзадачи 5-6-7-8 для данного конкретного состояния должны наверняка присутствовать некоторые общие ходы. Дело в том, что маловероятна ситуация, при которой фишки 1-2-3-4 можно было бы передвинуть на свои места, не трогая фишек 5-6-7-8, и наоборот. Но что будет, если не учитывать эти ходы? Иными словами, допустим, что регистрируется не общая стоимость решения подзадачи 1-2-3-4, а только количество ходов, в которых затрагиваются фишки 1-2-3-4. В таком случае можно легко определить, что сумма этих двух стоимостей все еще представляет собой нижнюю границу стоимости решения всей задачи. Именно эта идея лежит в основе баз данных с непересекающимися шаблонами. Применение таких баз данных позволяет решать случайно выбранные экземпляры задачи игры в пятнадцать за несколько миллисекунд — количество формируемых узлов сокращается примерно в 10 000 раз по сравнению с использованием манхэттенского расстояния. Для задачи игры в 24 может быть достигнуто ускорение приблизительно в миллион раз.

Базы данных с непересекающимися шаблонами успешно применяются для решения головоломок со скользящими фишками, поскольку сама задача может быть разделена таким образом, что каждый ход влияет лишь на одну подзадачу, так как одновременно происходит перемещение только одной фишки. При решении таких задач, как кубик Рубика, подобное разделение не может быть выполнено, поскольку каждый ход влияет на положение 8 или 9 из 26 элементов кубика. В настоящее время нет полного понимания того, как можно определить базы данных с непересекающимися шаблонами для подобных задач.