5.2.4. Задача классификации объектов

5.2.4. Задача классификации объектов

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

победил( том, джон).

победил( энн, том).

победил( пат, джим).

Мы хотим определить

отношение класс( Игрок, Категория)

которое распределяет игроков по категориям. У нас будет три категории:

 победитель — любой игрок, победивший во всех сыгранных им играх

 боец — любой игрок, в некоторых играх победивший, а в некоторых проигравший

 спортсмен — любой игрок, проигравший во всех сыгранных им партиях

Например, если в нашем распоряжении есть лишь приведенные выше результаты, то ясно, что Энн и Пат — победители. Том — боец и Джим — спортсмен.

Легко сформулировать правило для бойца:

 X — боец, если существует некоторый Y, такой, что X победил Y, и

  существует некоторый Z, такой, что Z победил X.

Теперь правило для победителя:

 X — победитель, если

  X победил некоторого Y и

  X не был побежден никем.

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

 Если X победил кого-либо и X был кем-то побежден,

 то X — боец,

 иначе, если X победил кого-либо,

  то X — победитель, 

  иначе, если X был кем-то побежден,

   то X — спортсмен.

Такую формулировку можно сразу перевести на Пролог. Взаимные исключения трех альтернативных категорий выражаются при помощи отсечений:

класс( X, боец) :-

 победил( X, _ ),

 победил( _, X),  !.

класс( X, победитель) :-

 победил( X, _ ),  !.

класс( X, спортсмен) :-

 победил( _, X).

Заметьте, что использование отсечения в предложении для категории победитель не обязательно, что связано с особенностями наших трех классов.

Упражнения

5.1. Пусть есть программа:

p( 1).

p( 2) :- !.

p( 3).

Напишите все ответы пролог-системы на следующие вопросы:

(a) ?- p( X).

(b) ?- p( X), p(Y).

(c) ?- p( X), !, p(Y).

5.2. Следующие отношения распределяют числа на три класса - положительные, нуль и отрицательные:

класс( Число, положительные) :- Число > 0.

класс( 0, нуль).

класс( Число, отрицательные) :- Число < 0.

Сделайте эту процедуру более эффективной при помощи отсечений.

5.3. Определите процедуру

разбить( Числа, Положительные, Отрицательные)

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

разбить( [3, -1, 0, 5, -2], [3, 0, 5], [-1, -2] )

Предложите две версии: одну с отсечением, другую — без.