Зонирование территории по степени риска цунами

курсовая работа

1.1 Постановка задачи

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

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

Как можно характеризовать исследуемую область? Традиционный подход заключается в сопоставлении каждой точки территории некоторого набора измеримых либо экспертно оцененных параметров. Далее будем называть этот набор вектором параметров. Однако возможность определения вектора параметров в каждой точке исследуемой области сомнительна. Во-первых, произвести измерения (оценку) в каждой точке физически затруднительно, во-вторых, задание многих параметров в точке лишено смысла - так, если высота над уровнем моря принципиально может характеризовать каждую точку территории, то, например, тип экосистемы характеризует некоторую окрестность точки. Также, следует заметить, что не требуется слишком большая точность определения маршрута (рис.1.1).

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

Рис.1.1 Представление в виде графа

Геометрия пикселей может влиять на точность решения, но принципиальной роли не играет. Нами были выбраны квадратные пиксели. Соседями пикселя считалась его окрестность фон Неймана (рис.1.2).

Рис.1.2 Пример недоминируемых маршрутов

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

Рассмотрим два пути в графе - p и q. Пусть стоимость маршрута p равна s1 а стоимость маршрута q - s2, риск маршрута p равен r1 а риск маршрута q - r2.

Будем говорить, что маршрут p доминирует маршрут q, если выполняются следующие условия:

s1 <= s2 и r1 <= r2 причем s1! = s2 или r1! = r2 (1.1)

т.е. маршрут p доминирует маршрут q если он лучше по одному из параметров и не хуже по другому параметру.

Введённое определение проиллюстрировано на рис.1.2 На рисунке показаны оценки четырёх маршрутов в пространстве стоимость-риск. Путь c доминирует маршрут b т.к. он дешевле и безопаснее, маршрут c доминирует маршрут a т.к. при равной стоимость он безопасней, но маршруты a и d не доминирует друг друга - маршрут a дешёвый, но опасный, а маршрут d безопасный, но дорогой.

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

Делись добром ;)