Рациональный алгоритм проверки гипотез пространственного исторического исследования на базе геохронологического трекинга в ГИС

Ивакин Ян Альбертович доктор технических наук ведущий научный сотрудник, Санкт-Петербургский институт информатики и автоматизации, Российская академия наук 198207, Россия, г. Санкт-Петербург, линия 14-Я в.о., 39, оф. СПИИРАН Ivakin Yan Al'bertovich Doctor of Technical Science Leading researcher, Saint-Petersburg Institue for Informatics and Automation of the Russian Academy of Sciences of. SPIIRAN, 39, 198207, liniya 14-Ya v.o., g. Saint Petersburg, Russia, ivakin@oogis.ru Другие публикации этого автора     Потапычев Сергей Николаевич кандидат технических наук старший научный сотрудник, Санкт-Петербургский институт информатики и автоматизации, Российская академия наук 196000, Россия, г. Санкт-Петербург, линия 14-џ, 39, оф. СПИИРАН Potapychev Sergei Nikolaevich PhD in Technical Science Senior researcher, Saint-Petersburg Institue for Informatics and Automation of the Russian Academy of Sciences of. SPIIRAN, 39, liniya 14-Ya,  g. Saint Petersburg, Russia, 196000 potapichev@oogis.ru Другие публикации этого автора

Ивакин Владислав Янович бакалавр, кафедра Исторической информатики, Московский государственный университет имени М.В.Ломоносова 119991, Россия, г. Москва, ул. Ломоносовский Проспект, 27, корп.4, Исторический факультет МГУ Ivakin Vladislav Yanovich Bachelor, Historical Information Science Department, Lomonosov Moscow State University 119991, Russia, g. Moscow, ul. Lomonosovskii Prospekt, 27, korp.4, Istoricheskii fakul'tet MGU ivakin-11@mail.ru

Работа выполнена при поддержке РФФИ (проект №19-07-00006).

1. ВВЕДЕНИЕ

Процесс геохронологического трекинга представляет собой совокупность способов сбора первичной биографической, хронологической информации и последовательности приемов обобщения геохронологических треков исторических личностей (объектов, артефактов или их совокупностей) на электронной карте (в ГИС). Соответственно геохронологический трек есть интеграция хронологических и географических данных о пространственных перемещениях в виде графа, соединяющего географические точки нахождения указанных исторических сущностей (Вершины трека имеют строгое историко-географическое определение, дуги носят характер условно-логической связи). В статьях ^[1,2] дано комплексное описание узкоспециализированой программной технологии геохронологического трекинга, а в работе ^[3] показаны возможности применения аналитического аппарата теории графов и статистических исследований на базе геохронологического трекинга.

Выполнение разработки апробационных примеров построения геохронологических треков по данным из ^[4,5] для различных групп исторических личностей позволило прейти к выводу, что финишная версия графа для достаточно представительной выборки исторических сущностей (личностей, объектов и пр.), как правило, имеет высокосложную и полно - / высоко- связную структуру. Такая структура может быть строго упорядочена. Этот тезис иллюстрирует пример трека, показанный на Рисунке 1, который построен по результатам геохронологического трекинга данных послужных списков офицеров Главного штаба Военного министерства Российской Армии в период с 1870 по 1910. Именно на основе такого итогового графа геохронологического трекинга становится возможным исследование различных миграционных процессов, выявления некоторых частных исторических закономерностей в перемещении социальных групп, статистически подтвержденная проверка исследовательских гипотез о характере миграций. Существо, концептуальная модель и методологический аппарат таких исследований детально описаны в статье ^[6].

Концептуальная идея проверки исследовательских гипотез заключается в следующем: итоговый граф геохронотрекинга представляется как граф-базис в структуре которого выявляется подграф изоморфный заданному, т.е. устанавливается наличие взаимно однозначного отображения одного графа на подграф другого, при котором сохраняется отношение инцидентности ^[7]. Граф, на изоморфность к которому в составе базового графа геохронологического трекинга определяется подграф, топологически описывает ту или иную определенную гипотезу исследования об устойчивой особенности в перемещениях исторических личностей, объектов или других сущностей в географическом пространстве. При этом изоморфность понимается как структурное равенство (подобие до совпадения вершин графов, при единых принципах их нумерации). Более детально изоморфность графов определена в ^[8].

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

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

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

2. КОНКРЕТИЗАЦИЯ ГРАФОВОЙ МОДЕЛИ ПРОВЕРКИ ИССЛЕДОВАТЕЛЬСКИХ ГИПОТЕЗ НА БАЗЕ ГЕОХРОНОТРЕКИНГА

Итогом реализации трекинга, как специализированного программного процесса в ГИС, является географически привязанный граф, обобщающий геохронологические треки отдельных исторических сущностей или артефактов, информация о миграциях которых занесена в соответствующую базу данных ^[1]. Именно этот граф является базисом проверки исследовательских гипотез, т.е. в его составе выявляются подграфы изоморфные графам-гипотезам.

Рисунок 1. – Рассмотрение геохронологического трека в ГИС в качестве упорядоченного графа (по материалам РГВИА; данные послужных списков офицеров русской армии, XIXв.)

Представленный на Рисунке 1 пример обобщающего геохронотрека дает возможность понять всю сложность и комбинаторную вариабельность решения частной задачи рационального выделения подграфа изоморфного заданному. Существо указанного выделения заключается в следующем: два графа изоморфны, если между парами множеств их вершин, рёбер и дуг существуют взаимно однозначных соответствия, сохраняющие смежность и ориентацию для дуг ^[8]. Значение попарно изоморфных графов с заданным значением вершин и заданным значением рёбер конечно. Изоморфное отображение графа на граф задаётся перестановкой называемой изоморфной, т.е. при распознавании изоморфизма графов и необходимо определить факт изоморфности указанных графов. В случае установления изоморфизма необходимо указать изоморфную подстановку. В виду того, что в теории графов не определены граничные условия и условия оптимальности решения задачи определения строгого соответствия графов, то правомерно применение целого ряда математических методов установления изоморфизма в качестве методологического базиса разработки искомого алгоритма для случая проверки гипотез исследования на базе геохронологического трекинга.

Условно все множество математических методов установления изоморфизма графов, они же методы решения задачи распознавания изоморфизма графа заданному, можно классифицировать как это показано на Рисунке 2 ^[7]. Очевидно, что доминирующими математическими методами в определении изоморфизма графов являются методы, использующие инварианты. (Инвариант графа — это некоторая функция, сопоставляющая графу соответствующий элемент из множества,элементами которого выступают числа или системы чисел, векторы, многочлены, матрицы и другие алгебраические структуры. Для изоморфных графов значения этой функции совпадают. ^[8]) В соответствии с разнообразием выбора однотипных фрагментов графа различают три класса инвариантов: локальные, квазиглобальные и глобальные.

Рисунок 2 -Классификации математических методов установления изоморфизма графов

При решении задачи поиска изоморфизма графов при различных условиях (размерность графов, их регулярность, однородность и пр.), определяется функция временной сложности самой задачи. Именно эта функция позволяет конкретизировать математический метод решения задачи до прикладного алгоритма, адаптированного к граничным условиям геохронологического трекинга (Упорядоченный граф, количество вершин n от 20 до 100 и пр.). Как правило, это полиномиальный или экспоненциальный алгоритм поиска изоморфизма. Различие между двумя указанными типами алгоритмов особенно заметны при решении задач большой размерности. Данные из Таблицы 1 позволяют увидеть причины, по которым полиномиальные алгоритмы более предпочтительны для поиска изоморфизма на геохронотреке по сравнению с экспоненциальными: большинство экспоненциальных алгоритмов – это варианты полного перебора, в то время как полиномиальные алгоритмы возможно построить лишь тогда, когда удаётся строго формализовать предметную суть решаемой задачи. Иными словами, задача строго формализована, если для её решения получен полиномиальный алгоритм ^[7]. В свою очередь, необходимо показать, что линейное установление изоморфизма графов алгоритмически отличается от более сложной задачи: распознания изоморфного вложения в составе граф-базиса. Изоморфное вложение или изоморфизм подграфу: Граф изоморфно вложим в другой граф, если во втором графе существует подграф, изоморфный начальному графу ^[7]. Эта задача отличается от задачи распознавания графов: в частности, чтобы решить задачу изоморфизма подграфа с использованием известных алгоритмов распознавания изоморфизма графов, необходимо реализовать процедуру выявления в графе-базисе подмножества вершин, равномощного с множеством вершин изначального графа. Эта процедура реализуется как многократное и итеративное применение алгоритма распознавания изоморфизма графов как некоторой частной функции в составе более общего алгоритма.

Таблица 1- Временная сложность экспоненциальных алгоритмов решения задачи поиска изоморфизма графов

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

3. РАЦИОНАЛИЗАЦИЯ ПРОЦЕДУРЫ РАСПОЗНАНИЯ ИЗОМОРФНОГО ВЛОЖЕНИЯ ПОДГРАФА-ГИПОТЕЗЫ В СОСТАВЕ ГРАФ-БАЗИСА

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

Это делает возможным предложить конкретизированный алгоритм распознавания изоморфного вложения подграфа-гипотезы в составе граф-базиса, соответствующий ограничениям и условиям предметной области геохронотрекинга. В соответствии с приведенной выше классификацией методов решения такой задачи математический метод, который реализован в алгоритме, является комбинированным методом направленного перебора. Он объединяет в себе основные преимущества, которые дают методы направленного перебора, использующие локальные, квазиглобальные и глобальные инварианты. В разработанном в ходе исследования алгоритме используются инварианты, такие как: число вершин, число рёбер, вектор степеней, полустепень исхода, полустепень захода, матрица смежности ^[7].

При синтезе указанного алгоритма были приняты следующие допущения и ограничения:

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

- все вершины должны быть пронумерованы;

- рассматриваются только ориентированные графы, т.е. при анализе неориентированных графов необходимо задавать одно ребро как два, связывающих вершины в обоих направлениях;

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

Методологическим базисом предлагаемого алгоритма решения задачи определения изоморфного вложения графа в граф-базис является тезис о том, что логические схемы структурирования граф-базиса и графа-гипотезы создают в совокупности систему ограничений, которая воздействует на множество гипотетически возможных вариантов решения и существенно его сокращает. Т.е. производится не перебор вариантов решения, что привело бы к N-факториальным переборам, а производится наложение системы ограничений по определённому алгоритму на специально созданное поле и на этом поле в результате последовательности действий, направленных на удовлетворение требований этой системы ограничений, формируется уже готовый вариант решения. Этот вариант может выглядеть для графов одинаковой размерности как матрица подстановок. Является допустимым: поле с множеством гипотетически возможных подстановок представить в виде матрицы размерностью n*m, гдеn и m– число вершин графов соответственно. Такая матрица далее а называется матрицей возможных подстановок.

Логико-математическое существо матрицы возможных подстановок заключается в том, что на этой матрице отражено всё поле возможных решений текущей задачи изоморфизма графов. Так при решении этой задачи для графов одинаковой размерности путем прямого перебора считается, что каждой вершине графа 1 может быть сопоставлена любая из вершин графа 2. Количество возможных подстановок на матрице размерностью n*n будет равным n!. Эта матрица является удобным средством для фильтрации всех невозможных подстановок. Такая фильтрация имеет два этапа. На этапе номер один производится устранение с поля возможных решений тех вариантов подстановок, которые невозможны принципиально по условию задачи (используя как фильтры глобальные, квазиглобальные и локальные инварианты, а также веса дуг или вершин и др.). На этапе номер два фильтрация вариантов имеет место для выдвигаемых гипотез о той или иной подстановке.

Существо работы предлагаемого алгоритма распознавания изоморфного вложения подграфа-гипотезы в составе граф-базиса, применительно к задаче проверки исследовательских гипотез в ГИС можно эффективно проиллюстрировать на примере решения рассматриваемой задачи для графов, показанных на Рисунке 3. Матрицы смежности и матрица возможных подстановок для этой пары графов приведены на Рисунке 4. В матрице возможных подстановок С в первом столбце перечислены все вершины графа В, а в первой строке – все вершины графа А. В столбце N+1 записывается количество возможных подстановок.

Рисунок 3 – Пример распознания изоморфного вложения графа-гипотезы в составе граф-базиса

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

Матрица смежности графа А

Матрица смежности графа В

Матрица возможных подстановок (матрица С)

Рисунок 4 - Матрицы смежности графов и возможных подстановок

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

I. Графы не могут быть изоморфными, если в столбце матрицы "Количество возможных подстановок" имеется хотя бы одна нулевая строка;

II. При однозначном соответствии вершины Bi вершине Aj (Bi↔Aj), в столбцеj матрицы возможных подстановок (С) не должно быть других символов ‘1’. Для удовлетворения требований этого ограничения необходимо исключить из матрицы в столбце j т.н. лишние символы ‘1’. В связи с тем, что найденное соответствие для какой-либо вершины может оказаться ложным, исключение символов ‘1’ из матрицы необходимо производить таким образом, чтобы оставалась возможность восстановления матрицы на определённом шаге. С этой целью введена переменная Mirage, значение которой изменяется после каждого цикла наложения системы ограничений на матрицу возможных подстановок. Из сказанного следуют действия, которые математически можно представить так: если C[N+1,i]=1 и C[j,i]=’1’то элементу C[k,i],имеющему значение ’1’(для k=1..m; k≠i), присвоить текущее значение переменной Mirage. Если все значения столбца матрицы «количество возможных подстановок» больше 1, то для скорейшего нахождения решения, очевидно, необходимо взять для работы строку с наименьшим значением. А первой, из неиспользованных ранее ячеек соответствующей строки, присваивается т.н. фокус, т.е. назначается активная ячейка (определяются координаты вершин подстановки C[FocB,FocA]). Остальные символы ‘1’ необходимо «закрыть» переменной Mirage.

III. При Bi↔Aj, вершинам Bk (k=1..m), смежным с Bj,могут соответствовать только те вершины Al (l=1..n), которые смежны с вершиной Ai. Для удовлетворения этого требования необходимо т.н. лишние символы ’1’ в матрице возможных подстановок «закрыть» переменной Mirage. Математически это можно записать следующим образом:

a. Если C[j,i]=’1’ и B[j,FocB]=’1’ и A[j,FocA]¹’1’ то C[j,i]=Mirage;

b. Если C[j,i]=’1’ и B[FocB,i]=’1’ и A[FocA,i]¹’1’ то C[j,i]=Mirage,

где А,В – исходные матрицы смежности, а С – матрица возможных подстановок.

IV. Другие частные ограничения, учитывающие специфику распознания подграфа-гипотезы в составе граф-базиса, применительно к задаче проверки исследовательских гипотез в ГИС.

Приведенный перечень ограничений не является полный и закрытым. В данном случае, ограничения выполняют роль логического фильтра. В зависимости от специфики структуры подграфа, описывающего гипотезу, на структуре граф-базиса могут вводиться т.н. дополнительные фильтры-требования. Тогда текстуальное описание работы алгоритма распознавания изоморфного вложения подграфа-гипотезы в составе граф-базиса, применительно к задаче проверки исследовательских гипотез в ГИС, как работы программы решения задачи нахождения изоморфного вложения графов представимо, как показано ниже (Для примера графов, показанных на Рисунке 3):

=> Начало

1. Выполнена процедура Prov_0_str. Pr_0 = 0 переход на Prov_1_str;

2. Prov_1_str => Pr_1 = 0 переход на Prioritet;

3. Prioritet (c наименьшим числом подстановок две строки (1-я и 2-я). Выбор первой строки и присвоение ей первого приоритета). PrTab^[1] = 1; Mirage =’2’; PrEnd = 0; переход на Mirage1;

4. Mirage1. Определена активная ячейка C^[1,2], т.е. выдвинута гипотеза, что B1↔A2. На основании этой гипотезы получается: C^[1,3],C^[4,2],C^[5,2] = ‘2’; PrExit = 0; Pr_0 = 0. Переход на Mirage3.

5. Mirage3. В связи с тем, что B1 имеет исходы в B3,B4,B6 (B1àB3,B4,B6), а A2 àA3,A6,A8, то, следовательно, и вершинам B3,B4,B6 могут соответствовать только вершины из множества A3,A6,A8. В таком случае в матрице С получается: C^[3,4],C^[3,7],C^[4,2],C^[4,5],C^[6,4],C^[6,7] = ‘2’; аналогично для BßB5 и для A2ßA1, т.е. B5↔A1, а C^[5,3],C^[5,5] = ‘2’; переход на Mirage2;

6. Mirage2. C^[2,6],C^[6,6] = ‘2’. Переход на Prov_1_str =>ZapolnMatrCM => ProvEnd. PrExit = 1. (Найденная перестановочная матрица оказалась неверной) => Nvar = 0 => ExitToHome(восстановление матрицы С в прежнем виде) => Mirage1;

7. Mirage1. Определена активная ячейка C^[1,3], т.е. выдвинута гипотеза, что B1↔A3. На основании этой гипотезы получается: C^[1,2],C^[4,3],C^[5,3] = ‘2’; PrExit = 0; Pr_0 = 0. Переход на Mirage3;

8. Mirage3.В связи с тем, что B1 àB3,B4,B6, а A3 àA4,A5,A7, то, следовательно, и вершинам B3,B4,B6 могут соответствовать только вершины из множества A4,A5,A7. В таком случае в матрице С получается: C^[3,6],C^[4,2],C^[6,6],C^[6,8] = ‘2’; аналогично для B1ßB5 и для A3ßA2, т.е. B5↔A2, а C^[5,1],C^[5,5] = ‘2’; переход на Mirage2;

9. Mirage2. Изменений матрицы С не происходит, переход на Prioritet;

10. Prioritet. Активной выбирается строка 4. Pr = 2; (PrTab^[4]=2); Mirage = ‘3’. Переход на Mirage1;

11. Mirage1. Определена активная ячейка C^[4,5], т.е. выдвинута гипотеза, что B4↔A5. … Переход на Mirage3;

12. Mirage3. В связи с тем, что B4 àB2,B3, а A5 àA4,A6, то, следовательно, и вершинам B2,B3 могут соответствовать только вершины из множества A4,A6. В таком случае в матрице С получается: C^[2,7],C^[3,7] = ‘3’; аналогично для B4ßB1 и для A5ßA3, т.е. B1↔A3, изменений матрицы не происходит; переход на Mirage2;

13. Mirage2. C^[6,4] = ‘3’. Переход на Prov_1_str =>ZapolnMatrCM => ProvEnd. PrExit = 1. (решение найдено) => Nvar = 1 => Prioritet (попытка поиска автоморфизмов) => ProvEnd = 1;

=> Конец.

При этом матрица возможных подстановок будет в процессе выполнения программы в соответствии с описанным алгоритмом принимать вид, последовательно представленный на Рисунке 5.

а.)

б.)

в.)

Рисунок 5 - Динамика изменений вида матрицы возможных подстановок

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

4. ЗАКЛЮЧЕНИЕ

Использование алгоритмов и вычислительных процедур теории графов применительно к исследовательскому аппарату геохронологического трекинга дает принципиально новые потенциальные возможности для внедрения строгих математических и расчетных методик в сфере ГИС-задач для гуманитарных наук. Также очевидна и перспективность дальнейшей адаптации расчетных методов, моделей и методик «мягких» вычислений (использование нечетких множеств и нечетких чисел, функций лингвистической переменной и пр.) для ГИС-приложений, применяемых в ходе реализации исторических, этнографических, антропологических и других гуманитарных исследовательских проектов. Данный подход уже сегодня является предметом интереса специалистов в области вычислительной математики, современной алгоритмики и Digital Humanities (в более строгой версии этого направления), что подтверждается такими публикациями как ^[3,9-16].

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

Поддержка исследований.Работа выполнена при поддержке РФФИ (проект №19-07-00006).