Классификация с разбивкой по категориям

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

beat (torn, jim!. beat(arm, torn). beat! pat, jim).

Необходимо определить отношение

class!. Player, Category)

которое позволяет разбить игроков на категории. Предусмотрены только три катего­рии, описанные ниже.

Глава 5. Управление перебором с возвратами 127

• winner. Победителем является каждый игрок, который победил во всех по­единках.

• fighter. Боец — это любой игрок, который выиграл в некоторых встречах, а а некоторых проиграл.

• sportsman. Звание спортсмен а-любителя присваивается тому игроку, который уступил во всех поединках.

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

X является бойцом, если

есть некоторый Y, такой, что X побеждает Y, и есть некоторый 2, такой, что Z побеждает X

Теперь сформулируем правило определения победителя:

X является победителем, если X побелил некоторого Y и X не был побежден никем.

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

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

в противном случае, если X кого-то победил, то X - победитель, в противном случае, если х был кем-то побежден,

то

противном случа

 

 

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

beat (_, X), I.

class ( x, winner):-beatt x, _),!.

class (X, sportsman):-

beatt _, x).

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

?- class! ton. С).

С - fighter; I Как и следовало ожидать

по

?- class! torn, sportsman),

yes % Вогреки ожиданиям

Вызов отношения class является безопасным, если второй параметр не конкре­тизирован. В противном случае могут быть получены непредсказуемые результаты.

128 Часть I. Язык Prolog

 

Упражнения

5.1. Рассмотрим следующую программу:
Р(И.

Р(2):-!. Р(3).

Напишите все ответы системы Prolog на приведенные ниже вопросы.

а)?- р(Х).

б)?-р(X), р(Y).

в)?- р(х;,!, р(Y).

5.2. Приведенное ниже отношение классифицирует числа на три категории: поло-
жительные, нуль и отрицательные.

class (Number, positive):- Number > 0.

class! 0, zero).

class (Number, negative):- Number < 0.

Определите эту процедуру более эффективным способом с использованием опе­ратора отсечения.

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

splits Numbers, Positives, Negatives)

которая разбивает список чисел на два списка; положительные (включая нуль)

и отрицательные, например, как показано ниже.

split ([3,-1,0,5,-2], [3,0,5;, -1,-23)

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