Диплом (1222543), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

алгоритмом

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

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

2.5 Описание программного модуля

В начале работы программы выполняется импорт исходных данных из текстового и Excel файлов. После импорта исходных данных происходит подготовка переменных, необходимых для расчета, к работе. Производится подсчет числа месторождений из матрицы исследуемой территории путем считывания идентификатора 4 из матрицы исследуемой территории.

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

Для многих форм недоступных участков одного лишь этого условия недостаточно, поскольку программа запишет в матрицу элементы МИТ, не являющиеся граничащими с углами недоступных участков. На рисунке 2.7 красным цветом показаны элементы МИТ, которые программа определит, как граничащие, но не являющиеся таковыми.

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

Рисунок 2.7 – Определение элементов МИТ, не являющимися граничащими

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

– доступен для построения маршрута, идентификатор 0;

– проверен алгоритмом, не использован при построении маршрута, идентификатор 1;

– использован при построении маршрута, идентификатор 2;

– не удовлетворяет условиям построения маршрута, идентификатор 3.

После заполнения матрицы выполняется расчет данных по формулам (2.2-2.4). Рассчитывается длина ЭУ, исходя из данных о размерах исследуемой территории и размерности МИТ.

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

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

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

В начале алгоритма триггер устанавливается в первое положение. В качестве триггера выступает переменная принимающая в начале цикла значение 1. В переменные и записываются координаты месторождения – начальной контрольной точки. Для выхода из алгоритма используется переменная , которая в начале цикла принимает значение 0. Алгоритм заканчивает свою работу, когда принимает значение 1.

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

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

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

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

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

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

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

Характеристики

Список файлов ВКР