2.4. Задачи в замкнутой форме
В наиболее общем виде условия задачи математически могут быть записаны следующим образом:
Найти в заданном множестве X точки х, удовлетворяющие множеству заданных ограничений
Примером такой постановки может служить сформулированная в неявном виде задача Бине: “из множества целых натуральных чисел х выбрать такие числа, которые удовлетворяют уравнению
.
Примечания. 1. Задание пространства X означает в общем случае одновременное (но неявное) задание структуры X и
разрешенных операций над X. Знание X является определяющим в исходных данных.
2. Первоначально полученную замкнутую формулировку задачи можно в общем случае снова перевести в другую форму, чтобы с учетом ограничений
уменьшить пространство X и улучшить таким образом представление задачи. Задача решается именно в процессе последовательных изменений представлений, причем последняя замкнутая формулировка дает непосредственно решение задачи.
Существуют два основных варианта представления задачи в замкнутой форме.
Вариант 1
Пространство содержит исходное состояние
заданы конечное состояние
и конечный перечень операторов
которые позволяют перейти от одного состояния
к другому состоянию
Речь идет о том, чтобы найти путь от 50 к
В качестве примера рассмотрим “игру в пятнадцать”:
Здесь операторы
имеют следующий смысл: переход из одного состояния в другое производится последовательным перемещением занумерованных фишек на пустое место. Замкнутая формулировка задачи в рассматриваемом варианте имеет вид
.
Решение х есть на самом деле определенная последовательность
где
.
Множество ограничений
выражается в правиле следования операторов, причем конечное состояние для оператора является начальным состоянием для последующего.
Вариант 2
Здесь речь идет о классической формулировке задачи на доказательство в математике:
Получить
исходя из
Примером задачи в такой постановке является следующая задача:
Показать, что для всех
Этот вариант сводится к предыдущему, если положить
Существенное отличие состоит, однако, в том, что операторы перехода от одного состояния к другому не заданы. Искусство математика как раз и заключается в том, чтобы отыскать те операторы, которые окажутся полезными для данного условия задачи. Часто конечное состояние
вовсе не задано. Тогда наша задача формулируется следующим образом: “Рассчитать
” и становится совсем неопределенной, так как критерий остановки процесса решения оказывается субъективным. Обычно ожидается, что в процессе решения задачи результатом будет выражение “более простое”, чем начальное. Однако простота выражения также не является строго определенным понятием с математической точки зрения.