Используемые методы и алгоритмы

Условия и ограничения

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

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

• · В-третьих, графы в основном будут задаваться в виде некоторого описания:, где порядковый номер параметров равен номеру узла, — количество узлов, с которыми i-тый узел имеет связи причем. К тому же каждое значение в описание указывает не уникальное количество связей, а общее. Это значит, что значения в описании полностью соответствуют узлам и их связям. Это значит, что каждая связь в описании указывается дважды. А значит, сумма всех значения должна быть четной, чтобы граф можно было построить, следуя инструкции S. Эти условия необходимо учесть при разработке проверок формата описания, введенного пользователем.
• · В-четвертых, по описанию S можно построить большое количество разных графов и с каждым из них нужно провести определенное количество экспериментов. Объемы этих выборок нельзя выбирать случайно, по желанию. Для этого необходимо прибегнуть к методам теории вероятностей по поиску оптимального объема выборок графов для описания S и оптимального количество необходимых прогонов каждого графа по алгоритму удаления ребер. Это предоставляет нам возможность выдавать достоверные статистические данные с точностью, которую пожелает указать сам пользователь.

Проблема вычисления стохастической степени связности неориентированных графов включает в себя несколько подзадач. Рассмотрим их в порядке прохождения в программе.

Первая подзадача

Первая подзадача заключается в нахождении оптимального объема выборки графов для описания S. Выборочная совокупность (или выборка) — это отобранное по особому строго заданному правилу определенное число элементов генеральной совокупности. Это число обеспечивает некоторую достоверность и надёжность результатов того явления, которое мы рассматриваем. Объем выборки может быть вычислен по формуле [6], где N — объем выборки; д — найденное среднее квадратичное отклонение; д² — дисперсия; t — t-критерий, зависящий от числа планируемых опытов (определяется по стандартной таблице значений t-критерия Стьюдента); Д — ожидаемое значение предельной ошибки выборки. Такой параметр как относительная погрешность в программе будет указываться пользователем в настройках для регулировки подходящей точности, которая будет необходима пользователю. Однако необходимо понимать, что уменьшение значения погрешности приведет к дополнительным временным затратам. В то же время, в этом случае статистические данные будут более точными. В дальнейшем, используя эту же методологию, необходимо найти оптимальное количество проводимых экспериментов для каждого сгенерированного графа. Тогда можно будет гарантировать точность результата.

Проблема представления графов

Чтобы работать с графами их необходимо как-то представлять в программе. «Есть два стандартных способа представить граф G = (V, E): как набор списков смежности или как матрицу смежности. Оба способа применимы как к ориентированным, так и к неориентированным графам» [7] (стр. 527−531). Однако только с матрицей смежности можно быстро сказать, что существует связь, соединяющая две вершины. К тому же возможно использовать треугольную матрицу смежности по причине отсутствия ориентации в связях графов. В этом случае матрица будет симметричной относительно главной диагонали. Это позволит ускорить работу алгоритмов, работающих непосредственно с графами.

Вторая подзадача

Следующий этап — случайное удаление ребер и проверка связности графов при каждой итерации. Необходимость случайного удаления была пояснена выше в начале главы (Глава 2) и в главе «Определения, обозначения, сокращения». После того, как связь между двумя любыми узлами, которые имели эту связь ранее, была потеряна, необходимо проверить граф на критерий связности, чтобы узнать, не распался ли он на две части. В связи с тем, что оба звена графа, потерявшие связь, известны, проверка связности сводится к поиску пути в графе от первого узла ко второму. Это значит, что алгоритм освобождается от необходимости искать путь к каждому узлу и проверять все пути. Можно отказаться от тяжелых алгоритмов, таких как поиски в глубину и в ширину. Теперь можно обратить внимание на такие алгоритмы как: алгоритмы Дейкстры, Флойда, поиска А*. Это значительно увеличивает общую эффективность и скорость работы модуля по поиску стохастической связности в группе графов, описываемых через S.

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

Дополнительные задачи

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

При всем при этом в локальную базу данных будут записываться несколько последних (объем пользователь сможет указать в настройках) созданных описаний графов S и самих графов для демонстрационного модуля. Сообщение с БД производится с помощью библиотек SQLite на языке SQL-запросов.