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

2.6. Пример полного решения задачи

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

“Пусть имеется шахматная доска, каждая сторона которой содержит 100 клеток. Все 10 000 полей доски заняты черными шашками. В нашем случае разрешенными ходами являются “модификации”, т. е. операции замены в каком-то ряду (строке или столбце) всех шашек ряда черного цвета на белые и белых на черные. Спрашивается, можно ли за конечное число ходов получить 1990 белых шашек, начиная с позиции, когда все шашки были черными?”

На обычном языке это условие задачи легко формулируется и понимается. Однако, во-первых, ответ на поставленный вопрос не возникает сам по себе, а во-вторых, “проигрывание ситуации” затруднительно, так как доска размером не является обычной. Чтобы уловить смысл задачи и сделать некоторые первоначальные заключения, т. е. создать очевидные представления условий, естественно рассмотреть задачу с уменьшенными параметрами, например использовать доску размером или в качестве доски использовать абстрактный квадрат со стороной неопределенной длины.

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

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

1. Бхли дважды подряд модифицируют один и тот же ряд, исходная позиция не изменяется.

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

Рис. 2.9. Зоны расположения белых и черных шашек на шахматной доске.

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

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

4. На основании двух первых заключений можно сделать вывод, что порядок ходов в задаче не является существенным и результирующее состояние ряда то же при ходах, что и при одном ходе-модификации. Аналогичным образом, состояние ряда одинаково как при ходах, так и при 0 ходах.

5. На основании третьего вывода можно строки, которые были модифицированы один раз, перенести в верхнюю часть доски, а столбцы, которые также были модифицированы один раз, перенести в левую часть доски. Таким образом, доска окажется разбита на четыре зоны, которые показаны на рис. 2.9. Прямоугольные зоны на доске слева вверху и справа внизу заполнены черными шашками, причем одни из них перевернуты дважды, а другие ни разу. Прямоугольные зоны слева внизу и справа вверху заполнены белыми шашками, причем они все перевернуты по одному разу.

6. Число строк в верхних и число столбцов С в левых прямоугольниках соответствуют рядам шашек, модифицированных один раз.

7. Представленная на доске позиция обладает симметрией относительно строк и столбцов. Если — решение задачи, то и полученное вращением позиции на 90°, также будет решением.

8. Рассматриваемая позиция обладает еще и центральной симметрией. Если — решение, то и также будет решением задачи. Это свойство уже менее очевидно, чем предыдущие.

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

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

Очевидно, что никогда нельзя получить нечетное число белых шашек. На этом этапе для получения нового, более общего представления о задаче целесообразно ее несколько обобщить. Ее можно сформулировать так: путь — середина доски и — число, равное половине заданного числа белых шашек. Тогда, если разделить на 2 обе части равенства (2.1) и использовать для записи обозначения получим

Итак, во-первых, трудности решения задачи связаны с целочисленным характером уравнения (2.2); во-вторых, равенство (2.2) напоминает уравнение конуса: в-третьих, решение этого уравнения затрудняется тем, что в него входят как линейные члены , так и квадратичные —

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

. В результате получим

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

где

Выражение (2.3) определяет представление условий задачи в трехмерном пространстве, причем слева и справа от знака равенства находятся целые числа. Целое число, стоящее в правой части, на самом деле известно:

Для существования решения необходимо, чтобы число 1505 было разложимо на простые множители, сопоставимые с размерами доски. Итак, мы имеем так как

В данном случае существуют два решения, удовлетворяющих этим условиям. Первое решение

Второе решение

Таким образом, имеются два варианта получения на доске 1990 белых шашек.

С другой стороны, существуют такие числа для белых шашек, получение которых невозможно. Например, если , имеем , и тогда одна из двух величин — либо I, либо с — превышает число 50, что недопустимо ни для одного решения задачи.

Наконец, имеется особый случай, когда либо I, либо с равно нулю, т. е. или С равно 50. Это вырожденный случай, и каково бы ни было здесь значение другой неизвестной, единственное число, которое удовлетворяет условиям задачи, будет

Все задачи этого класса могут быть решены одний и тем же методом (включая сюда и задачи не только на квадратной, но и на прямоугольной доске). Что касается других методов решения задач с условиями типа (2.1), т. е. в целых числах, то мы найдем их в гл. 3 и 6.

Следующий раздел главы взят из книги Д. Пойа “Как решать задачу” (George Poiya, How to solve it, 1956).

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