Исследование проблем размещения объектов (FLP), также известное как анализ местоположения, представляет собой раздел исследования операций и вычислительной геометрии, связанный с оптимальным размещением объектов для минимизации транспортных расходов с учетом таких факторов, как недопущение размещения опасных материалов рядом с жилыми домами и конкурентов. удобства.
Рассмотрим следующий сценарий
Сельский район страны решил улучшить свое здоровье и доступ к лекарствам. Решили построить новую больницу и аптеку, но все спорили об оптимальном расположении этих объектов. Одни спорят о населении городов, другие - о расстоянии.
Первый шаг - создать модель сельской местности, чтобы мы могли применить некоторую логику. Используя теорию графов, мы создадим неориентированный граф городов нашей сельской местности. Каждая вершина будет городом / деревней, а ребра - связями между ними. Например, возьмем следующий график.
Прежде чем мы попытаемся найти оптимальное расположение больницы / аптеки, давайте определимся с некоторыми терминами теории графов.
Эксцентриситет
Эксцентриситет - это максимальное расстояние от вершины 𝑣 до любой другой вершины
𝑢 графа. e (v) = max {𝑑 (v, u) | 𝑢 ∈ 𝑉 (𝐺)}. Например, эксцентриситет узла 3 равен 3, если учесть, что каждое ребро имеет вес 1.
Центр графика
Подграф графа, индуцированный вершинами графа с минимальным
эксцентриситетом, называется центром графа G (обозначается центром (𝐺)).
На нашем графике мы ясно видим, что центром графика является узел 3.
Расстояние до вершины
Расстояние между вершинами определяется как сумма расстояний между определенной вершиной
и всеми вершинами графа.
расстояние 𝑣 = SUM (𝑑𝑖𝑠𝑡 (𝑣, 𝑢)) для любого 𝑢 ∈ 𝑉 (𝐺)
Медиана графика
Подграф графа, индуцированный вершинами графа с минимальным
расстоянием, называется медианой графа (обозначается как медиана (𝐺)).
В нашем случае медиана графика - это узел 6.
А как насчет больницы? а как насчет аптеки? Куда их положить?
Больница должна быть рядом с самыми быстрыми маршрутами. Обратите внимание, что скорая помощь должна пройти один и тот же путь дважды: одна отправляет машину к месту, а другая возвращает пациента в больницу.
С другой стороны, аптека просто должна быть доступна для горожан.
Медиана графика может минимизировать время, поскольку она имеет минимальный эксцентриситет. Вот где должна быть размещена больница. Как вы уже представляли, центр диаграммы можно использовать для аптеки, потому что она более доступна для всех.
Давайте запрограммируем это.
Первое, что нужно сделать, это передать график на каком-нибудь компьютерном языке beep boop. Мы будем использовать Java.
Нам нужно использовать алгоритм Дейкстры, чтобы мы могли найти все кратчайшие пути для каждого узла.
Эти две вспомогательные функции будут использоваться алгоритмом Дейкстры для поиска минимального и максимального значения массива.
После построения путей мы можем найти эксцентриситет в центре и медиане следующим образом
Основное из класса будет следующим.
Заключение
Мы проверили упрощенную версию проблемы, которая может быть очень утомительной, если принять во внимание множество факторов и связать ее с теорией графов. Сначала мы сделали модель сельского города с графиком. Используя центр и середину графика, мы создали автоматизированный способ размещения этих двух объектов в оптимальном месте. Теория графов помогает нам моделировать и решать проблемы, используя существующие теоремы и применяя к ним повседневную логику. Каждое применение свойств теории графов зависит исключительно от проблемы, с которой мы сталкиваемся, в нашем случае от расположения больницы и аптек.
Вы можете проверить живую демонстрацию кода здесь
Это сообщение в блоге было создано, чтобы поделиться нашим любопытством в сотрудничестве с Никосом Пантелидисом.
