Главная > Интеллектуальные системы > Системы искусственного интеллекта
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.11. Изменение представлений

Поиск хорошего представления в ходе решения задачи является почти всегда необходимым этапом на пути к решению. Существует множество задач, когда мы пользуемся прежде всего зрением и руками для выработки единственного “сиюминутного” (непосредственного) представления об окружающем мире, таком, каким мы его воспринимаем непосредственно в данный момент. В этом случае нет необходимости ни в какой абстрактной модели задачи, но в свою очередь это ведет к бесполезным попыткам и поискам “на ощупь” обобщения идеи, решения, которое могло бы быть использовано при решении других задач.

Задача о четырех шахматных конях

Шахматная доска и передвижение фигур на ней зачаровывало многих авторов. На основе шахмат созданы многочисленные головоломки. В данном случае речь идет о том, чтобы за минимальное число ходов изменить на противоположное положение двух черных и двух белых коней. В задаче используется шахматная доска размером . Исходная позиция задачи о четырех конях представлена на рис. 2.19 а. Кони “ходят” (перемещаются но доске) привычным образом: на одно поле горизонтально и на два — вертикально за ход либо, наоборот, на два поля горизонтально и на одно — вертикально.

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

Рис. 2.19 а. Исходная позиция в задаче о четырех копях.

Рис. 2.19 б. Обозначение позиций и ходоц коня, начиная с поля А.

Пытаясь промоделировать условия задачи на уровне какого-то более общего представления, первое о чем мы вспоминаем, это декартова система координат. Однако такое представление имеет существенный недостаток, связанный с трудностью записи перемещения фигур на величины, равные, большие или меньшие единицы или большие или меньшие двух. Однако такие перемещения очень важны в нашем случае и именно они то и должны быть представлены в удобной форме. Сама по себе шахматная доска почти не играет в задаче существенной роли; и ее физическое представление является только внешней поддержкой решения задачи, так как на самом деле единственно существенным является учет, связей между ходами, сделанными при переходе от позиции к позиции (вспомним, например, кубик Рубика). Отсюда вытекает, что следует дать имена, т. е. свои обозначения различным

позициям, как, например, на рис. 2.196. Теперь мы знаем, что черный конь может переместиться на поле за один ход с поля или поля F. В свою очередь на поле конь сможет попасть либо с того же поля А, либо с поля С, на поле С — с поля на него — с поля на поле с поля В, на него — с поля , наконец, на — с поля начиная с которого конь сможет вновь попасть на поле А.

Рис. 2.20. Путь коня с поля А.

Рис. 2.21. Решение задачи о четырех конях.

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

Новая формулировка задачи теперь состоит в том, что нужно так переместить по этой окружности черных коней на А и С, а белых коней на и чтобы за один ход конь перемещался на одну позицию справа или слева по окружности. Решение задачи теперь практически очевидно: достаточно лишь повернуть на полоборота по окружности весь ансамбль фигур так, чтобы С попало на — на — на С и С — на А. Это вращение, которое соответствует четырем ходам каждого коня, или шестнадцати ходам всех фигур, дает решение задачи — минимальное число ходов для изменения исходной позиции на противоположную (рис. 2.21).

<< Предыдущий параграф Следующий параграф >>
Оглавление