Об информационном подходе к решению переборных задач

Об информационном подходе к решению переборных задач

А.А. Борисенко, профессор, Сумской государственный университет.

Переборные задачи - это особый класс дискретных задач, решаемых перебором дискретных объектов различной природы.

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

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

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

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

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

Рисунок 1 - Структурная схема решения переборной задачи

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

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

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

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

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

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

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

В работе [1] была проведена информационная оценка простейшей переборной задачи для случая, когда вероятности , равны . Это значит, что в задаче отсутствует какая-либо предварительная информация об искомом объекте. Соответственно энтропия выбора объекта из заданных N

(1)

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

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

Как показано в [1], количество частной информации

(2)

где - вероятность того, что выбранный -й объект является искомым.

Известно, что функция имеет максимум при , т.е. при , и при , и соответственно при , минимум

(3)

При остальных значениях функция будет монотонно возрастать.

Следовательно, на начальных шагах перебора вырабатывается минимальное количество частной информации , начиная с (3), которое постепенно увеличивается и достигает максимального значения, равного 1-му биту.

Последний -й объект при переборе не анализируется, так как информация, полученная на _м шаге при тестировании -го объекта, однозначно определяет состояние -го объекта: если на _м шаге перебора тест вырабатывает положительный ответ, то искомым является -й объект, если отрицательный, то искомым будет нетестируемый -й объект.

Если найти среднее значение всех частных информаций на -м шаге, то будет получена общая информация -го шага, которая, как следует из [1], равна

(4)

(5)

(6)

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

В отличие от общая информация имеет тенденцию к уменьшению, и наименьшего значения она достигает при :

(7)

а максимального - при :

(8)

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

Суммирование по всем образует информацию объединения

(9)

В [1] показано, что

(10)

и соответственно, так как

(11)

В свою очередь,

(12)

где - энтропия решающего переборную задачу алгоритма. Соответственно

(13)

Полученное равенство определяется как принцип равенства энтропий [1].

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

Если же по каким-либо причинам переборный алгоритм имеет энтропию , например, какие-то из объектов он не может подать на тестирование, то тогда в решении задачи появляется остаточная энтропия

(14)

и соответственно искомый объект в процессе решения задачи уверенно не может быть обнаружен.

Однако если не будет протестирован только один объект, то и в соответствии с принципом равенства энтропий задача в конечном итоге будет решена.

, (15)

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

В реальной жизни вследствие возможных ошибок алгоритма и теста .

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

Ошибки теста состоят в том, что вместо сигнала “да” он выдает сигнал “нет” и наоборот.

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

Таким образом, любая дискретная задача представляет собой приемник генерируемой тестом информации с энтропией .

Устранение, частичное или полное, этой энтропии происходит алгоритмом, выполняющим с помощью заданной последовательности действий тестирование задачи.

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

СПИСОК ЛИТЕРАТУРЫ

Борисенко А.А. Об информационной оценке эффективности решения переборных задач // Вестник СумГУ, 2002. - №13(46); - С. 177-184.