Статья 'Рациональный алгоритм проверки гипотез пространственного исторического исследования на базе геохронологического трекинга в ГИС' - журнал 'Историческая информатика' - NotaBene.ru
по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > О журнале > Требования к статьям > Порядок рецензирования статей > Ретракция статей > Этические принципы > Политика открытого доступа > Оплата за публикации в открытом доступе > Публикация за 72 часа: что это? > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат > Редакция > Редакционный совет
Журналы индексируются
Реквизиты журнала

Публикация за 72 часа - теперь это реальность!
При необходимости издательство предоставляет авторам услугу сверхсрочной полноценной публикации. Уже через 72 часа статья появляется в числе опубликованных на сайте издательства с DOI и номерами страниц.
По первому требованию предоставляем все подтверждающие публикацию документы!
ГЛАВНАЯ > Вернуться к содержанию
Историческая информатика
Правильная ссылка на статью:

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

Ивакин Ян Альбертович

доктор технических наук

ведущий научный сотрудник, Санкт-Петербургский институт информатики и автоматизации, Российская академия наук

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

DOI:

10.7256/2585-7797.2019.2.28612

Дата направления статьи в редакцию:

09-01-2019


Дата публикации:

17-07-2019


Аннотация.

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

Ключевые слова: Географические информационные системы, ГИС технологии, геохронологический трек, геохронологический трекинг, исторические исследования, изоморфизм графов, информационная технология, программный аппарат, географические данные, биографические данные

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

Abstract.

Information technology of geochronological tracking in history is a combination of processes which accumulate and integrate data about geographic relocation of historical figures for a given time interval and present the results as a generalizing graph in GIS. Hypotheses on stable migration trends are sub-graphs of this graph. To test such trends is to search and evaluate statistical significance of isomorphism (structural similarity) of corresponding graphs. Rationalization of algorithm is achieved by means of a reasonably chosen basic method searching for isomorphic embedding into geochronotrack graph basis. The basic methodological approach is a combination of representative and analytical methods of modern geoinformatics and graph theory. Full-featured development of computer interpretation of graph theory methods based on geochronological tracking provides for new quality of historical studies using modern GIS-tools. Namely, a researcher can use quantitative methods of a corresponding logical-analytical apparatus. The article addresses qualitatively new possibilities of such an approach and a corresponding algorithmic apparatus.
.

Keywords:

information technology, graphs’ isomorphism, history researches, geochronological tracking, geochronological track, GIS technologies, Geographic information system, program apparatus, geographic data, biographical data

1. ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

1

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

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

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

2

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

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

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

Функция временной сложности

Размер граф-базиса (Количество вершин n )

10

20

30

40

50

n

0,00001 с

0,00002 с

0,00003 с

0,00004 с

0,00005 с

n2

0,0001 с

0,0004 с

0,0009 с

0,0016 с

0,0025 с

n3

0,001 с

0,008 с

0,027 с

0,064 с

0,125 с

n5

0,1 с

3,2 с

24,3 с

1,7 мин.

5,2 мин.

2 n

0,001 с

1,0 с

17,9 мин.

12,7 дней

35,7 лет

3 n

0,059 с

58 с

6,5 лет

3855 столетий

2*108 столетий

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

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

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

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

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

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

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

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

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

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

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

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

3

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

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

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

1

2

3

4

5

6

7

8

S-(x)

1

0

1

0

0

0

0

1

0

2

2

0

0

1

0

0

1

0

1

3

3

0

0

0

1

1

0

1

0

3

4

0

0

0

0

0

1

0

0

1

5

0

0

0

1

0

1

0

0

2

6

0

0

0

0

0

0

1

0

1

7

0

0

0

0

0

0

0

1

1

8

0

0

0

0

0

0

0

0

0

S+(x)

0

1

1

2

1

3

3

2

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

1

2

3

4

5

6

S-(x)

1

0

0

1

1

0

1

3

2

0

0

0

0

0

1

1

3

0

1

0

0

0

0

1

4

0

1

1

0

0

0

2

5

1

1

0

0

0

0

2

6

0

0

0

0

0

0

0

S+(x)

1

3

2

1

0

2

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

А1

А2

А3

А4

А5

А6

А7

А8

Количество подстановок

В1

0

1

1

0

0

0

0

0

2

В2

0

0

0

0

0

1

1

0

2

В3

0

0

0

1

0

1

1

0

3

В4

0

1

1

0

1

0

0

0

3

В5

1

1

1

0

1

0

0

0

4

В6

0

0

0

1

0

1

1

1

4

Рисунок 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 ; переход на Mirage 1 ;

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

5. Mirage3 . В связи с тем, что B 1 имеет исходы в B 3, B 4, B 6 ( B 1 à B 3, B 4, B 6), а A 2 à A 3, A 6, A 8 , то, следовательно, и вершинам B 3, B 4, B 6 могут соответствовать только вершины из множества A 3, A 6, A 8 . В таком случае в матрице С получается: C [3,4], C [3,7], C [4,2], C [4,5], C [6,4], C [6,7] = ‘2’ ; аналогично для B ß B 5 и для A2ßA1, т.е. B 5↔ A 1, а 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 (восстановление матрицы С в прежнем виде) => Mirage 1 ;

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

8. Mirage3. В связи с тем, что B 1 à B 3, B 4, B 6, а A 3 à A 4, A 5, A 7 , то, следовательно, и вершинам B 3, B 4, B 6 могут соответствовать только вершины из множества A 4, A 5, A 7 . В таком случае в матрице С получается: C [3,6], C [4,2], C [6,6], C [6,8] = ‘2’ ; аналогично для B 1 ß B 5 и для A 3 ß A 2 , т.е. B 5↔ A 2, а C [5,1], C [5,5] = ‘2’ ; переход на Mirage2;

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

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

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

12. Mirage3 . В связи с тем, что B 4 à B 2, B 3 , а A 5 à A 4, A 6 , то, следовательно, и вершинам B 2, B 3 могут соответствовать только вершины из множества A 4, A 6 . В таком случае в матрице С получается: C [2,7], C [3,7] = ‘3’ ; аналогично для B 4 ß B 1 и для A 5 ß A 3 , т.е. B 1↔ A 3 , изменений матрицы не происходит; переход на Mirage2;

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

=> Конец.

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

а.)

А1

А2

А3

А4

А5

А6

А7

А8

Количество подстановок

В1

1

2

1

В2

2

1

1

В3

2

1

2

1

В4

2

1

2

1

В5

1

2

2

2

1

В6

2

2

2

1

1

б.)

А1

А2

А3

А4

А5

А6

А7

А8

Количество подстановок

В1

2

1

1

В2

1

1

2

В3

1

2

1

2

В4

2

2

1

1

В5

2

1

2

2

1

В6

1

2

1

2

2

в.)

А1

А2

А3

А4

А5

А6

А7

А8

Количество подстановок

В1

2

1

1

В2

1

3

1

В3

1

2

3

1

В4

2

2

1

1

В5

2

1

2

2

1

В6

3

2

1

2

1

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

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

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

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

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

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

Библиография
1.
Ивакин Я.А., Потапычев С.Н. Развитие информационной технологии геохронологического трекинга для исторических исследований в ГИС // Историческая информатика. — 2017.-№ 2.-С.85-94. DOI: 10.7256/2585-7797.2017.2.23083. URL: http://e-notabene.ru/istinf/article_23083.html
2.
Потапычев, С.Н. Геохронологический трекинг – специализированный ГИС-инструментарий исторического исследования [Текст] // Ивакин Я.А., Потапычев С.Н. – Журнал «Историческая информатика», № 1-2-2016; с. 3-11.
3.
Нечепуренко М. И., Попков В. К., Майнагашев С. М., Кауль С. Б., Проскуряков В. А., Кохов В. А., Грызунов А. Б. Алгоритмы и программы решения задач на графах и сетях — Новосибирск: Наука. Сиб. отд-ние, 1990. — 515 с.
4.
РГВИА-фонд Ф.400 Главного штаба Военного министерства.
5.
РГВИА – фонд Ф.409 "Послужные списки, аттестации и наградные листы офицеров русской армии".
6.
Ивакин Я.А., Потапычев С.Н., Ивакин В.Я. Проверка гипотез исторического исследования на базе геохронологического трекинга // Историческая информатика. — 2018.-№ 2.-С.96-102. DOI: 10.7256/2585-7797.0.0.25344. URL: http://e-notabene.ru/istinf/article_25344.html
7.
Зыков А.А. Основы теории графов.-М: Вузовская книга, 2004.-664 с.
8.
Печенкин В.В., Королев М.С., Дмитров Л.В. Прикладные аспекты использования алгоритмов ранжирования для ориентированных взвешенных графов// Труды СПИИРАН.-2018.-№6(61) – С.94-119. DOI:10.15622/sp61.4
9.
Дюваль П.М. Непрерывная интеграция. Улучшение качества программного обеспечения и снижение риска [Текст] Дюваль П.М., Матиас С., Гловер Э. – СПб.: Символ, 2016.-240с.
10.
ДеМарко Т. Вальсируя с медведями. Управление рисками в проектах по разработке программного обеспечения[Текст] / ДеМарко Т., Листер Т. – М., Издательский дом DH, 2005.-196с.
11.
ДеМарко Т. Deadline. Роман об управлении проектами [Текст] / ДеМарко Т. – М., Издательство «Манн-Иванов-Фербер», 2016.-352с.
12.
Воротников В.И., Вохмянина А.В. Метод линеаризующей обратной связи в задаче управления по части переменных при неконтролируемых помехах// Труды СПИИРАН.-2018.-№6(61) – С.61-93. DOI:10.15622/sp61.3
13.
Курейчик В.В., Жиленков М.А. Муравьиный алгоритм для решения оптимизационных задач с явно выраженной целевой функцией // Информатика, вычислительная техника и инженерное образование. 2015. № 2. С. 1–12.
14.
Deepak А., Tobias F. Average-Case Analysis of Incremental Topological Ordering //Discrete Applied Mathematics. 2010. vol. 158. no. 4. pp. 240–250.
15.
Ammar A.B. Query optimization techniques in graph Databases // International Journalof Database Management Systems (IJDMS). 2016. vol. 8. no. 4. 14 p.
16.
Sarma A.D., Molla A.R., Pandurangan G., Upfal E. Fast distributed pagerank computation // Theoretical Computer Science. 2015. vol. 561. pp. 113–121.
References (transliterated)
1.
Ivakin Ya.A., Potapychev S.N. Razvitie informatsionnoi tekhnologii geokhronologicheskogo trekinga dlya istoricheskikh issledovanii v GIS // Istoricheskaya informatika. — 2017.-№ 2.-S.85-94. DOI: 10.7256/2585-7797.2017.2.23083. URL: http://e-notabene.ru/istinf/article_23083.html
2.
Potapychev, S.N. Geokhronologicheskii treking – spetsializirovannyi GIS-instrumentarii istoricheskogo issledovaniya [Tekst] // Ivakin Ya.A., Potapychev S.N. – Zhurnal «Istoricheskaya informatika», № 1-2-2016; s. 3-11.
3.
Nechepurenko M. I., Popkov V. K., Mainagashev S. M., Kaul' S. B., Proskuryakov V. A., Kokhov V. A., Gryzunov A. B. Algoritmy i programmy resheniya zadach na grafakh i setyakh — Novosibirsk: Nauka. Sib. otd-nie, 1990. — 515 s.
4.
RGVIA-fond F.400 Glavnogo shtaba Voennogo ministerstva.
5.
RGVIA – fond F.409 "Posluzhnye spiski, attestatsii i nagradnye listy ofitserov russkoi armii".
6.
Ivakin Ya.A., Potapychev S.N., Ivakin V.Ya. Proverka gipotez istoricheskogo issledovaniya na baze geokhronologicheskogo trekinga // Istoricheskaya informatika. — 2018.-№ 2.-S.96-102. DOI: 10.7256/2585-7797.0.0.25344. URL: http://e-notabene.ru/istinf/article_25344.html
7.
Zykov A.A. Osnovy teorii grafov.-M: Vuzovskaya kniga, 2004.-664 s.
8.
Pechenkin V.V., Korolev M.S., Dmitrov L.V. Prikladnye aspekty ispol'zovaniya algoritmov ranzhirovaniya dlya orientirovannykh vzveshennykh grafov// Trudy SPIIRAN.-2018.-№6(61) – S.94-119. DOI:10.15622/sp61.4
9.
Dyuval' P.M. Nepreryvnaya integratsiya. Uluchshenie kachestva programmnogo obespecheniya i snizhenie riska [Tekst] Dyuval' P.M., Matias S., Glover E. – SPb.: Simvol, 2016.-240s.
10.
DeMarko T. Val'siruya s medvedyami. Upravlenie riskami v proektakh po razrabotke programmnogo obespecheniya[Tekst] / DeMarko T., Lister T. – M., Izdatel'skii dom DH, 2005.-196s.
11.
DeMarko T. Deadline. Roman ob upravlenii proektami [Tekst] / DeMarko T. – M., Izdatel'stvo «Mann-Ivanov-Ferber», 2016.-352s.
12.
Vorotnikov V.I., Vokhmyanina A.V. Metod linearizuyushchei obratnoi svyazi v zadache upravleniya po chasti peremennykh pri nekontroliruemykh pomekhakh// Trudy SPIIRAN.-2018.-№6(61) – S.61-93. DOI:10.15622/sp61.3
13.
Kureichik V.V., Zhilenkov M.A. Murav'inyi algoritm dlya resheniya optimizatsionnykh zadach s yavno vyrazhennoi tselevoi funktsiei // Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie. 2015. № 2. S. 1–12.
14.
Deepak A., Tobias F. Average-Case Analysis of Incremental Topological Ordering //Discrete Applied Mathematics. 2010. vol. 158. no. 4. pp. 240–250.
15.
Ammar A.B. Query optimization techniques in graph Databases // International Journalof Database Management Systems (IJDMS). 2016. vol. 8. no. 4. 14 p.
16.
Sarma A.D., Molla A.R., Pandurangan G., Upfal E. Fast distributed pagerank computation // Theoretical Computer Science. 2015. vol. 561. pp. 113–121.

Результаты процедуры рецензирования статьи

В связи с политикой двойного слепого рецензирования личность рецензента не раскрывается.
Со списком рецензентов издательства можно ознакомиться здесь.

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

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.
Сайт исторического журнала "History Illustrated"