Постановка задачи.

Данный алгоритм рассмотрим на конкретном примере.

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

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

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

Априорные предположения для рассматриваемой задачи сформулируем, опираясь на следующие условия:

1) количество участков, относящихся к месторождениям, значительно меньше количества пустых участков;

2) описания участков и меры сходства между ними выбираются таким образом, что участки, отвечающие месторождениям, значительно отличаются от пустых участков; пустые участки сходны между собой. Обозначим через — среднюю меру сходства между пустыми участками, — среднюю меру сходства между полезными участками, — среднюю меру сходства между полезными и пустыми участками.

Тогда формально априорные предположения можно записать в виде следующих неравенств:

.

Решение задачи направления опробования возможно и при других априорных предположениях (табл. 13, где мера сходства обозначена символом ). В данном случае мы ограничимся только выбранной ситуацией и сформулированными выше априорными предположениями.

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

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

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