Постановка задачи и интерфейс взаимодействия с приложением - Godis715/Krasnodar-Road-Network GitHub Wiki

Источник: Задание по курсу “Теория графов и ее приложения” v.2020

«Оценка удобства размещения объектов инфраструктуры города».

  • M - фиксированное множество объектов инфраструктуры города. В качестве M можно брать больницы, пожарные части, крупные торговые центры.
  • m = |M| - количество объектов инфраструктуры.
  • N - переменное множество узлов графа - домов. Можно брать жилые дома в качестве элементов N.
  • n = |N| - количество домов.

Расстояние Lij между вершинами Xi, Xj вычисляется по формуле Wi * Dij, где Wi - вес вершины, Dij - наименьшее время пути между вершинами.

Ограничения:

  • Wi = 1, если это вес дома
  • Wi - произвольное число в отрезке [1, 2], если это вес объекта инфраструктуры
  • m = 10
  • n = 100
  • Скорость движения по городу v = 40 км/ч

Расстояние между двумя вершинами может отличаться, поэтому для вершины Xi можно ввести три вида расстояния до вершины Xj: "туда", "обратно", "туда-обратно".

  1. Для каждого дома найти 3 объекта инфраструктуры, соответствующие расстоянию "туда", "обратно", "туда-обратно" такие, что эти расстояния для каждого объекта уникальны.

    По сути найти ближайший объект; объект, от которого до дома доехать быстрее; объект, до которого туда и обратно смотаться будет быстрее.

    Вход: дома N = { X1, ..., Xn }, скорость v.

    Выход: n троек (Xi1, Xi2, Xi3) - ближайшие дома к Xi по трем расстояниям, i = [1...n].

  2. Для каждого дома найти объекты, расположенные на расстоянии не большем, чем Y по каждому из трех расстояний.

    Вход: дома N = { X1, ..., Xn }, скорость v, максимальное расстояние Y.

    Выход: множества Mi = { Xj ∈ M | расстояние Lij <= Y }, i = [1...n].

  3. Найти такой объект инфраструктуры, для которого расстояние до самого дальнего дома минимально.

    Вход: дома N = { X1, ..., Xn }, скорость v.

    Выход: Xj ∈ M - наиболее оптимально расположенный по расстоянию до самого дальнего дома объект.

  4. Найти такой объект инфраструктуры, для которого сумма кратчайших расстояний до всех домов минимальна.

    Вход: дома N = { X1, ..., Xn }, скорость v.

    Выход: Xj ∈ M - наиболее оптимально расположенный по сумме минимальных расстояний до домов объект.

  5. Найти такой объект инфраструктуры, для которого дерево кратчайших путей до домов имеет минимальный вес.

    Вход: дома N = { X1, ..., Xn }, скорость v.

    Выход: Xj ∈ M - наиболее оптимально расположенный по весу дерева кратчайших путей до домов объект.

Интерфейс ввода/вывода

Первые две задачи представляют собой поиск оптимального объекта инфраструктуры по отношению к отдельно взятому дому. Эти две задачи можно выделить в отдельную функциональность "Ближайшие объекты инфраструктуры" с двумя оцпиями: "по кратчайшему расстоянию", "на расстоянии не более чем Y".

  • "по кратчайшему расстоянию" - имеет три опции "туда", "обратно", "туда-обратно"
  • "на расстоянии не более чем Y" - имеет настраиваемый параметр Y

Интерфейс ввода - либо кликами по отдельным домам, либо опцией "случайные n домов".

Следующие три задачи также можно выделить в отдельную функциональность "Поиск оптимально расположенного объекта инфраструктуры (в целом)" со следующими опциями:

  • по расстоянию до самого дальнего дома
  • по сумме минимальных расстояний до домов
  • по весу дерева кратчайших путей до домов

«Планирование новых объектов»

  1. Вход: дома N = { X1, ..., Xn }, Xj ∈ M - объект инфраструктуры, скорость v.

    Выход: дерево кратчайших путей от Xj до Xi ∈ N, i = [1...n]. Вес дерева, сумма кратчайших путей от Xj до домов.

  2. Требуется кластеризовать множество домов N по методу полной связи.

    Вход: дома N = { X1, ..., Xn }, скорость v, количество кластеров k.

    Выход: иерархия кластеров - дендрограмма.

  3. Вход: дома N = { X1, ..., Xn }, Xj ∈ M - объект инфраструктуры, скорость v, k - количество кластеров.

    Выход:

    • k кластеров домов из N.
    • { C1, ..., Ck } - центроиды кластеров.
    • дерево кратчайших путей от Xj до { C1, ..., Ck }.
    • k деревьев кратчайших путей от Ci до вершин i-го кластера, i = [1...k].
    • вес полученного дерева и сумма длин путей от объекта Xj до домов по этому дереву.

  4. Сравнить найденные величины для дерева кратчайших путей и дерева кратчайших путей по кластерам при разбиении на 3, 4, 5 кластеров. (Это, я думаю, не обязательно в интерфейс программы засовывать)

Интерфейс ввода/вывода

Кратчайшие пути можно визуализировать прямо на карте. Дендрограмму можно визуализировать в виде дерева кластеров. Числовые параметры можно выводить как есть.

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