Введение в недоопределенность

А.С. Нариньяни

1. Недоопределенность и Н-модели

Специалистов в любой области можно разделить на две категории:

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

Прогрессисты: понимающие, что каждая область — как и наука в целом — развивается по спирали, и что многое, относившееся к «незыблемым устоям» на предыдущем витке, радикально менялось на следующем; такие специалисты готовы к возможности крутых поворотов и относятся к таким возможностям с профессиональным интересом.

Обычно некоторые области находятся на этапе радикальных изменений и поэтому их динамика очевидна для всех. Другие гораздо более стабильны и возможность таких изменений в них вызывает естественное недоверие.

Поскольку вычислительная математика относится сегодня именно к таким внешне стабильным разделам науки, то «качественно новый подход» в ее контексте звучит неправдоподобно, поскольку для таких, казалось бы, уже полностью сложившихся дисциплин, крутые повороты развития представляются невозможными в принципе.

При этом история самой математики представляет собой цепь концептуальных потрясений и качественных скачков. Наверное, тем специалистам, которые когда-то пользовались римскими цифрами, тоже казалось, что известная им арифметика — это те самые устои, которые не изменятся никогда. Даже сложить два больших числа тогда было непростой задачей, а владение умножением вполне можно было приравнять к кандидатской диссертации. Однако с эпохой Возрождения в Европу пришла современная «арабская» позиционная система счисления, предложившая совершенно новое видение числа, при котором не только умножение, но и деление стало настолько простым, что им владеют уже в начальной школе.

За последние века в развитии вычислительных методов произошел не один крутой поворот, выводивший технологию расчетов на очередной уровень решения все более сложных задач. Я уверен, что Н-математика сыграет в этом процессе свою роль в подобном очередном переходе к новому качеству вычислений.

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

1.1. Консилиум

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

• должны быть исключены как недопустимые, поскольку он может квалифицировано представить обоснование их некорректности, и 
• кажутся подходящими, но он в них недостаточно уверен.

Таким образом, точка зрения каждого из присутствующих на решения проблемы может рассматриваться как его личный набор соображений «за» и «против» , причем «за» — дискуссионны, а «против» — бесспорны.

В процессе обсуждения проблемы присутствующие представляют эти свои «за» и «против». По ходу обмена мнениями множество «за» постепенно сокращается из-за их несовместимости с какими-то из «против», а набор «против» у каждого из экспертов накапливается за счет знакомства с мнениями коллег.

Поскольку в конце обсуждения совокупность «против» будет у всех одинаковой (суммарной), то она может:

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

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

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

Отметим, что для данного вводного раздела мы эту метафору упростили. В частности, оставили в стороне тот факт, что у каждого эксперта обычно есть распределение оценок вариантов «за» на тех участках k-мерного пространства проблемы, отвергать которые у него нет оснований. Мы еще вернемся к этому аспекту поиска решения в главе 8, а в основном тексте нам вполне достаточно рассматривать все допускаемые (не отвергнутые) альтернативы как равновозможные.

В следующем разделе мы п ерейдем от метафоры к очень простому примеру, а от него к более формальной постановке проблемы.

1.2. Недоопределенность и Н-переменная

Что же такое Недоопределенность?

Для того, чтобы ответить на этот вопрос, проще всего начать с базового понятия любой формальной системы — с переменной. При этом стоит напомнить, что существует по крайней мере два основных, качественно различных, понятия переменной: алгоритмическая и классическая.

Алгоритмическая переменная, связанная с использованием алгоритмов и появлением языков программирования, является, по сути дела, именем ячейки абстрактной памяти, в которую могут помещаться различные значения, меняющиеся по ходу исполнения соответствующей процедуры. Такая переменная не имеет отношения к нашей теме и исключается поэтому из дальнейшего рассмотрения.

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

Таким образом, традиционная математика оперирует с переменными, находящимися в одном из двух состояний: неопределено или определено.

Но подобное упрощение, к которому мы настолько привыкли, что считаем его само собой разумеющимся, годиться только для абстрактной формальной системы.

Для любого реального параметра реальной задачи:

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

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

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

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

Формально Н-значением переменной является любое непустое подмножество области значений этой переменной. Поскольку обычная (традиционная) переменная, сопоставляемая реальному параметру х, может принимать только точные значения, то в Н-математике ее приходится представлять Н-переменной *х, у которой область значений является совокупностью всех непустых множеств точных значений из области значений х.

При этом выражение *х = *а, где *х  — Н-переменная, а *а - ее текущее Н-значение, получает следующий смысл: точное значение параметра х, представленного Н-переменной *х, принадлежит подобласти значений, представленной Н-значением *а.

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

В частности, если областью значений переменной А является конечное множество А, то такой переменной А будет соответствовать Н-переменная *А с областью значений *А , представляющей собой множество всех подмножеств А без пустого:
*А = 2 А .

Например, как это показано на рис.1, переменной А  с областью значений А, представленной латинским алфавитом {a ,..., z}, сопоставляется Н-переменная *А с областью значений *А , включающей все непустые подмножества множества {a ,..., z}. Т.о. все определенные (однозначные) значения, равно как и все множество {a ,..., z} являются частным случаем Н-значений *А.

Это означает, что Н-значение способно отражать процесс решения реальной задачи, при котором Н-значение реального параметра проходит последовательные фазы доопределения, т.е.

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

Другими словами, текущее Н-значение *а Н-переменной *х, представляющей параметр х, равно подмножеству конкретных значений, любое из которых в процессе решения потенциально может стать точным значением *х и х, остающимся пока неизвестным (вернее, известным с точностью до данного Н-значения *а) ввиду недостатка информации. По ходу решения задачи, включающей параметр х, и\или при добавлении дополнительных данных его Н-значение становится все более определенным и в пределе может доопределиться до точного значения.

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

1.3. Простая сумма: убедитесь в разнице

Выше мы выяснили, что любое текущее Н-значение — это хотя в общем случае и приблизительная, но всегда корректная оценка реального значения соответствующего параметра, которое на данном этапе не определено более точно в контексте имеющейся недостаточно полной информации о результате. Уточнение формулировки задачи и\или продвижение процесса ее решения обеспечивает все большую определенность оценкам значений используемых в ней параметров.

Очевидно, что Н-значение числа (в главе 6 будут рассмотрены примеры и других типов) может быть представлено:

Списком (множеством) значений: {-1.5, 0.31, 2.47, ..., 3.1415}, {4, 5, 7, 8, 9,12}, ...

Интервалом: (0.1, 5.032], [-5, 103], ...

Мульти-интервалом: [-2.3, -0.2; 0.7, 4.6; 7, 31.22; ], {[-2.3, -0.2]; [0.7, 4.6]; [7,31.22];}...

или сочетанием этих представлений.

Например, целый числовой параметр х  имеет недоопределенное значение {3, 4, 5, 8, 9,12}, что означает, что его Н-значением в процессе дальнейшего решения задачи и\или ее доуточнения может стать любое из подмножеств этого множества значений, в том числе и конкретные 3 или 4 или 5 или 8 или 9 или 12. 

Если этот недоопределенный х  связан с целым положительным параметром у  уравнением х  + у  < 7, то отсюда следует, что *х = {3, 4, 5}, а *у = {1, 2, 3}. При добавлении ограничения у  > 1, обе эти Н-переменные уточняются, принимая более определенные Н-значения х  = {3, 4} и у  = {2, 3}.

Ясно, что введением одного понятия Н-переменной проблема аппарата, способного работать с недоопределенными данными, не решается: для этого потребуется создание комплекса операций и отношений, способных адекватно работать с Н-переменными. Мы займемся этим ниже, во второй главе. Но прежде чем переходить к формальным определениям, продолжим обсуждение проблемы на содержательном уровне.

Для этого рассмотрим пример, который позволит очень наглядно — буквально «на пальцах» — показать принципиальное качественное различие между Н-математикой и традиционной математикой, основанной на алгоритме. Для этого достаточно рассмотреть любую простую операцию, например, сумму А = В + С. 

Если А, В и С точные числа, никаких проблем не возникает: любые два из них определяют третье. Но, как уже отмечалось, в реальных задачах аргументами точные числа бывают редко, так что перейдем к параметрам, заданным интервалами: В = [5, 9] и С = [10, 14]. Тогда А определяется как [15, 23], т.е. интервал возможных значений результата равен сумме интервалов возможных значений аргументов. Поскольку алгоритм — это цепочка операций, то с каждой из них ширина интервала промежуточных результатов будет нарастать и приблизительность конечного результата для подавляющего множества задач быстро выйдет за рамки практического смысла.

Более тридцати лет довольно активно разрабатывается интервальная математика [20], оперирующая с интервальными значениями. Однако, несмотря на большую востребованность в интервальных расчетах, она так и не нашла массового применения именно из-за чрезмерной ширины интервалов выходных значений.

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

Если для нашего примера А = В + С заданы интервально любые два параметра, то третий определяется без проблем. Но если заданы все три, то наша сумма перестает быть функцией, а становится отношением (ограничением), влияющим на все три связанные им Н-переменные.

Например, для нашей суммы значение А может быть ограничено интервалом [11, 16]. Легко видеть, что ограничение А = В + С требует, чтобы заданные интервалы всех трех переменных «стянулись» до А = [15, 16], В = [5, 6] и С = [10, 11], поскольку при других значениях исходных интервалов ограничение суммы не выполняется.

Ясно, что в данном случае мы имеем дело уже не с алгоритмом, а с задачей, которая описывается уравнением А = В + С и набором интервальных ограничений на значения параметров А, В и С.

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

Здесь же важно подчеркнуть, что это справедливо не только для интервалов, но и для других типов Н-значений. Например, для нашей суммы переменные А, В и С могли быть не вещественными, а целыми и задаваться в этом случае множествами значений А = {12, 13, 14}, В = {1, 2, 3} и С = {7, 8, 9, 10}, которые должны были бы стянуться во множества А = {12, 13} , В = { 2, 3}, С = {9, 10}.

1.4. Ограничения и модели

Для каждого набора переменных x₁, x₂..., x_k с областями значений соответственно Х₁, Х₂,...,Х_k ограничением C (x₁, x₂, ...,x_k) называется любое подмножество декартова произведения областей Х₁, Х₂,..., Х_k. Ясно, что при таком определении ограничением будет любое отношение на множестве переменных x₁, x₂,...,x_k- уравнение, неравенство, логическое выражение, табличная зависимость и т.п., то есть любое соотношение, определяющее ту или иную подобласть k -мерного пространства значений переменных x₁, x₂,...,x_k.

Напомним, что моделью обычно называется пара Х, C, где Х  есть множество параметров (переменных) x₁, x₂,...,x_k  модели, а С  — неупорядоченная совокупность отношений (ограничений) на Х .

В общем виде постановка задачи в рамках constraint programming формулируется следующим образом:

Для заданной модели М = Х, C  требуется найти область решения , т.е. определить все наборы значений <a₁, a₂,...,a_k> (a_i∈ Х_i), которые бы удовлетворяли всем ограничениям С одновременно, т.е. принадлежали области пересечения всех ограничений в k -мерном пространстве значений переменных Х = {x₁, x₂,...,x_k}.

Таким образом, constraint programming оперирует с максимально декларативным по своей сути определением задачи в форме описания модели , а не алгоритма ее решения [1, 2].

В частности, любые системы уравнений с числовыми параметрами также являются моделями и относятся к проблемам constraint programming , причем для их решения в традиционной математике используются различные численные методы. Однако при решении подавляющего большинства реальных задач эти методы оказываются неприменимыми, особенно если модель включает и нечисловые параметры, а начальные данные могут задаваться приблизительно в виде множеств и интервалов, определяющих допустимые значения параметров.

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

Таким образом, для Н-переменной, вне зависимости от ее типа, можно различать два значения:

• реальное неизвестное нам значение, которое она представляет, и 
• ее текущее Н-значение, являющееся доступной нам в данный момент оценкой этого реального значения.

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

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

Ясно, что основная проблема constraint programming и Н-моделей состоит в том, как организовать процесс решения, т.е. последовательного монотонного уточнения Н-значений параметров модели, сходящихся к Н-значениям, которые определены совокупностью ограничений модели. Каким образом решается эта проблема будет рассмотрено в главе 3. 

Так как совокупность параметров модели задается множеством, то в отличие от алгоритма в модели нет априорного разделения параметров на входные и выходные. Исходная информация о параметрах, равно как и требования к их значениям в рамках решаемой задачи, задается в виде унарных ограничений на множество их возможных значений. В соответствии с требованиями решаемой задачи пользователь определяет, какие из параметров заданы точно, какие не известны совсем, а какие — приблизительно. Используя формулировку задачи в виде модели и исходную информацию о Н-значениях ее параметров, технология Н-моделей обеспечивает автоматическое стягивание пространства Н-значений параметров модели до подпространства, возможно близкого к минимальному из тех, которые содержат все возможные решения модели.

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

Радикальное изменение, внесенное технологией Н-моделей в вычислительную математику, состоит в том, что она делает любую модель активной . Модель становится компьютерной моделью , которая может быть использована для решения различных (в пределе, всех) задач, относящихся к описанному ею объекту. При этом постановка той или иной задачи конкретизируется путем добавления в модель ограничений на допустимые значения части или всех параметров и/или формулирования дополнительных связей между ними.

Реальные методы constraint programming особенно полезно там, где кончаются возможности обычной математики. Среди наиболее известных зарубежных систем, реализующих парадигму программирования в ограничениях, можно отметить Prolog III [3], CLP(R) [4], CLP(BNR) [5], clp(FD) [6], CHIP [7], ILOG Solver [8], Newton [9] и др. 

1.5. Новое качество решения

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

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

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

Более того, полноценная Н-модель может создаваться усилиями одного эксперта, который корректно описывает части, не имея достаточно полного знания о целом. В результате, активные знания Н-модели могут превосходить знания ее создателя (создателей).

Введение | Оглавление | Основные понятия

Перепечатывается с разрешения автора
Статья помещена в музей 29.09.2008 года