Крестьянин, волк, коза и капуста

Второй пример — известная задача о крестьянине, которому необходимо перевезти на другой берег волка, козу и капусту так, чтобы они не съели друг друга (рис. 2.2). В лодку крестьянин может взять с собой не более одного объекта.

Крестьянин, волк, коза и капуста — постановка задачи

Рис. 2.2. Крестьянин, волк, коза и капуста — постановка задачи

Естественно, можно упростить данную задачу. Идея такова — крестьянин и лодка неразличимы и составляют одно целое. Также можно считать любое перемещение с берега на берег мгновенным. Перенумеруем объекты: О — крестьянин, 1 — волк, 2 — коза, 3 — капуста. Присутствие объекта на правом (целевом) берегу обозначим «1», на левом (исходном) — «О». В таком случае, очевидно, что БД D должна иметь вид

D : array [0..3] of 0..1

При этом D [ 0 ] — это положение крестьянина, D [ 1 ] — волка, D [ 2 ] - козы и D [ 3 ] — капусты. Массив D можно записывать в виде четырехзначной битовой шкалы. Например, 0101 означает, что крестьянин с козой находятся на левом берегу, а волк с капустой — на правом. Тогда исходное состояние базы d0 = 0000, а целевое dt = 1111.

Каково должно быть множество правил? Если подойти к решению этой задачи прямолинейно, то можно рассуждать следующим образом. Всего имеется 16 возможных состояний базы[1]. Рассмотрим пары состояний базы такие, что из первого состояние можно перейти во второе за один ход. Например, 1011 —» ООН — крестьянин переплыл с правого берега на левый. Таких пар оказывается 16 • 4 = 64. Заметим, что некоторые состояния базы допустимы, например, 0101, а другие состояния недопустимы, например, ООН — коза съест капусту. Легко проверить, что допустимых состояний 10, а недопустимых — 6. Отбросим те пары состояний, в которых целевое состояние является недопустимым. Оставшиеся пары, а их 40 штук, являются правилами нашей системы.

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

Попробуем подойти к задаче творчески. В данном случае творчество состоит в привлечении общих знаний, которые в исходной постановке задачи не содержались:

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

Заметим, что начальное состояние допустимо (так же, как и конечное). Осталось выделить правила, сохраняющие допустимость. Для этого заметим, что в задаче, по существу, есть всего четыре возможных хода: движение крестьянина без объекта, движение крестьянина с волком, с козой и с капустой. Теперь осталось выписать простые условия допустимости этих ходов и получить множество правил R:

if D[1]<>D[2] & D[2]<>D[3] then D[0] : = 1 - D[0]

if D[2]<>D[3] & D[0]=D[1] then D[0]:= 1 - D[0];

D[1]:= 1 - D[1]

if D[0]=D[2] then D[0]:= 1 - D[0];

D[2]:= 1 - D[2]

if D [ 1 ] <>D [2] & D [ 0 ] =D [ 3] then D [ 0] : = 1 - D [0 ] ;

D[3]:= 1 - D[3]

Таким образом, в данном случае творческий подход к задаче улучшил представление знаний в 10 раз.

  • [1] Множество различных четырехзначных битовых шкал содержит 24 = 16 элементов.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >