Изменение представлений
Поиск хорошего представления знаний в ходе решения задачи является почти всегда необходимым этапом на пути к решению.
Задача о четырех шахматных конях
 |
Как за минимальное число ходов изменить на противоположное положение двух черных и двух белых коней? В задаче используется шахматная доска 3´3. Исходная позиция задачи о четырех конях представлена на рис. 1.3. Кони ходят (перемещаются по доске) привычным образом. Центральная клетка имеет метку E.
Рис. 1.3. Исходная позиция в задаче о 4 конях
При знакомстве с задачей нашим первым побуждением является сделать несколько попыток по перемещению коней на настоящей шахматной доске, но интуитивно мы понимаем, что, что имеется слишком много вариантов получения конечной позиции, причем при таком подходе плохо используется симметрия, присущая этой задаче. Пытаясь промоделировать условия задачи на уровне какого-то более общего представления, первое, о чем мы вспоминаем, это декартова система координат. Однако такое представление имеет существенный недостаток, связанный с трудностью записи перемещения фигур "ходом коня". Однако такие перемещения очень важны в нашем случае и именно они-то и должны быть представлены в удобной форме. Сама по себе шахматная доска почти не играет в задаче существенной роли, и ее физическое представление является только внешней поддержкой решения задачи, так как на самом деле единственно существенным является учет связей между ходами, сделанными при переходе от позиции к позиции. Мы знаем, что черный конь может переместиться на поле A за один ход с поля H или поля F. В свою очередь на поле H конь сможет попасть либо с того же поля A, либо с поля C, на поле C - с поля D, на него - с поля I, на поле I - с поля B, на него - с поля G и, наконец, на G - с поля F, начиная с которого конь сможет вновь попасть на поле A. Этот маршрут в виде окружности, проходящей в указанном порядке через все позиции, изображен на рис. 1.4.
 |
Рис. 1.4.
Решение задачи о 4 конях
Представление, получаемое с помощью этой диаграммы, наглядно и удобно для использования. На рисунке не представлено поле E, но это соответствует реальной ситуации - ни при каком ходе коня ни в одной позиции оно недостижимо. Все другие ситуации отражены, и это позволяет использовать ту же кольцевую диаграмму и для других коней.
Новая формулировка задачи теперь состоит в том, что нужно так переместить по этой окружности черных коней на A и C, а белых коней на G и I, чтобы за один ход конь перемещался на одну позицию справа или слева по окружности. Решение задачи теперь практически очевидно: достаточно лишь повернуть на пол-оборота весь ансамбль фигур так, чтобы C попало на G, A - на I, G - на C и I - на A. Это вращение, которое соответствует четырем ходам каждого коня, или шестнадцати ходам всех фигур, дает решение задачи - минимальное число ходов для изменения исходной позиции на противоположную.
Изменения представления знаний во время решения задачи - основной путь ее решения.
В представлении знаний при решении математических задач существенным является то, о чем не говорится в учебниках по математике и на лекциях, а именно каким образом и как находят доказательство.
На самом деле способ действия математика включает три различные фазы:
1. Понять теорему, заданную на формальном языке, т.е. перевести ее в некоторое внутреннее представление.
2. Доказать теорему в этом внутреннем представлении, используя для этого все накопленные и адаптированные к этому внутреннему представлению знания.
3. Перевести найденное еще не полное доказательство в строгое математическое доказательство, вновь введя символическую формализацию обычного математического языка.
Мы будем использовать логический подход в изучении ИИ, хотя он и имеет большие ограничения (см. раздел 1.4. Психологическая теория интеллекта). Представлять знания мы будем с помощью формул логики предикатов первого порядка, и использовать логический вывод.Конкретным инструментом для программирования будет язык SWI-prolog (см. курс лекций по логическому программированию). Наш выбор логического подхода определяется достаточно быстрым получением реальных результатов для хорошо формализуемых задач.
