8.2.2. Обобщение

8.2.2. Обобщение

Часто бывает полезно обобщить исходную задачу таким образом, чтобы полученная более общая задача допускала рекурсивную формулировку. Исходная задача решается, тогда как частный случай ее более общего варианта. Обобщение отношения обычно требует введения одного или более дополнительных аргументов. Главная проблема состоит в отыскании подходящего обобщения, что может потребовать более тщательного изучения задачи. В качестве примера рассмотрим еще раз задачу о восьми ферзях. Исходная задача состояла в следующем: разместить на доске восемь ферзей так, чтобы обеспечить отсутствие взаимных нападений. Соответствующее отношение назовем

восемьферзей( Поз)

Оно выполняется (истинно), если Поз — представленная тем или иным способом позиция, удовлетворяющая условию задачи. Можно предложить следующую полезную идею: обобщить задачу, перейдя от 8 ферзей к произвольному количеству — N. Количество ферзей станет дополнительным аргументом:

n_ферзей( Поз, N)

Преимущество такого обобщения состоит в том, что отношение n_ферзей допускает непосредственную рекурсивную формулировку:

(1) Граничный случай: N = 0

Разместить 0 ферзей — тривиальная задача.

(2) Общий случай: N > 0

Для "безопасного" размещения N ферзей необходимо:

• получить требуемое размещение для (N - 1) ферзей и

• добавить оставшегося ферзя так, чтобы он не бил ни одного из уже поставленных ферзей.

Как только мы научимся решать более общую задачу, решить исходную уже не составит труда:

восемьферзей( Поз) :- n_ферзей( Поз, 8)