Читать реферат по информационному обеспечению, программированию: "Разработка программного комплекса построения оптимального маршрута обхода пациентов" Страница 3


назад (Назад)скачать (Cкачать работу)

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

полученное с помощью приведенных алгоритмов, имеет 100%-ю точность, однако это компенсируется большими вычислительными и временными затратами. Например, сложность алгоритма полного перебора с ростом вершин (пунктов) напрямую зависит от всех возможных решений задачи. Другими словами дляпунктов необходимо рассмотретьвариантов маршрута. Откуда, при очень большом алгоритм может дать результат спустя несколько часов работы. Метод ветвей и границ отчасти решает эту проблему, если расстояния между пунктами различаются, в противном случае, при небольшом разбросе данных нахождение оптимального пути происходить очень медленно. Метод основывается на частичном переборе возможных решений с исключением подмножеств, которые не содержат оптимальных решений. Метод опирается на следующие построения:

· вычисление верхней границы значений целевой функции, либо на множестве, либо на некотором его подмножестве (оценивание);

· постепенное разбиение множества на подмножества (ветвления);

· пересчет оценок при постепенном разбиении множеств;

· нахождение конкретных вариантов решения;

· проверка вариантов на оптимальность;

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

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

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



Интересная статья: Основы написания курсовой работы