Pull to refresh

Comments 8

1. Долго смотрел на картинку… датчиков 13 шт?
2. Почему Монте-Карло, а не Евклид или dekstra?
3. В графовых алгоритмах есть более простые решения по поиску shortest paths.
4. Действительно ли нужно писать алгоритм, когда можно визуально по полю расставить датчики?
  1. "Почему в шапке? Почему без шапки?" Ну да, в коде 13. А что не так? Просто 13.
  2. Можно чуть развернуть вопрос? А то напрашивается ответ "Потому что тема так названа".
  3. Есть. Но надо еще задачу переформулировать так, чтобы граф увидеть. Далеко не всем очевидно в исходной постановке. Непосредственно здесь мы компьютером забиваем гвозди, поэтому Монте-Карло. Касательно библиотек для работы с графами. На больших объемах они киснут, приходится считать самим.
  4. Как указано в начале, нам нужно расставлять датчики так, чтобы между соседями было не более определенного расстояния (Lora mesh), батарейки экономим. Поэтому все это еще в общий цикл по числу датчиков можно завернуть и считать максимальное расстояние для расстановки.

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

1. В «Получаем табличку подобного рода» должно получиться 13 расстояний?
2. Если вы уже нашли расстояния между датчиками, почему затем используете Монте-Карло, почему нельзя просто посчитать прямые линии между ними (Евклидово расстояние)?
3.Так тут речь о 13 датчиках или нет?
Вот, я вам код накидал, правда, на python:
код
# dijkstra.py

from __future__ import annotations
from typing import TypeVar, List, Optional, Tuple, Dict
from dataclasses import dataclass
from mst import WeightedPath, print_weighted_path
from weighted_graph import WeightedGraph
from weighted_edge import WeightedEdge
from priority_queue import PriorityQueue

V = TypeVar('V') # type of the vertices in the graph


@dataclass
class DijkstraNode:
    vertex: int
    distance: float

    def __lt__(self, other: DijkstraNode) -> bool:
        return self.distance < other.distance

    def __eq__(self, other: DijkstraNode) -> bool:
        return self.distance == other.distance


def dijkstra(wg: WeightedGraph[V], root: V) -> Tuple[List[Optional[float]], Dict[int, WeightedEdge]]:
    first: int = wg.index_of(root) # find starting index
    # distances are unknown at first
    distances: List[Optional[float]] = [None] * wg.vertex_count
    distances[first] = 0 # the root is 0 away from the root
    path_dict: Dict[int, WeightedEdge] = {} # how we got to each vertex
    pq: PriorityQueue[DijkstraNode] = PriorityQueue()
    pq.push(DijkstraNode(first, 0))

    while not pq.empty:
        u: int = pq.pop().vertex # explore the next closest vertex
        dist_u: float = distances[u] # should already have seen it
        # look at every edge/vertex from the vertex in question
        for we in wg.edges_for_index(u):
            # the old distance to this vertex
            dist_v: float = distances[we.v]
            # no old distance or found shorter path
            if dist_v is None or dist_v > we.weight + dist_u:
                # update distance to this vertex
                distances[we.v] = we.weight + dist_u
                # update the edge on the shortest path to this vertex
                path_dict[we.v] = we
                # explore it soon
                pq.push(DijkstraNode(we.v, we.weight + dist_u))

    return distances, path_dict


# Helper function to get easier access to dijkstra results
def distance_array_to_vertex_dict(wg: WeightedGraph[V], distances: List[Optional[float]]) -> Dict[V, Optional[float]]:
    distance_dict: Dict[V, Optional[float]] = {}
    for i in range(len(distances)):
        distance_dict[wg.vertex_at(i)] = distances[i]
    return distance_dict


# Takes a dictionary of edges to reach each node and returns a list of
# edges that goes from `start` to `end`
def path_dict_to_path(start: int, end: int, path_dict: Dict[int, WeightedEdge]) -> WeightedPath:
    if len(path_dict) == 0:
        return []
    edge_path: WeightedPath = []
    e: WeightedEdge = path_dict[end]
    edge_path.append(e)
    while e.u != start:
        e = path_dict[e.u]
        edge_path.append(e)
    return list(reversed(edge_path))


if __name__ == "__main__":
    city_graph2: WeightedGraph[str] = WeightedGraph(["датчик1", "датчик2", "датчик3", "датчик4", \
                                                    "датчик5", "датчик6", "датчик7", "датчик8", \
                                                    "датчик9", "датчик10", "датчик11", "датчик12", \
                                                    "датчик13", "датчик14", "датчик15"])

    city_graph2.add_edge_by_vertices("датчик1", "датчик6", 1737)
    city_graph2.add_edge_by_vertices("датчик1", "датчик2", 678)
    city_graph2.add_edge_by_vertices("датчик2", "датчик4", 386)
    city_graph2.add_edge_by_vertices("датчик2", "датчик3", 348)
    city_graph2.add_edge_by_vertices("датчик3", "датчик4", 50)
    city_graph2.add_edge_by_vertices("датчик3", "датчик5", 357)
    city_graph2.add_edge_by_vertices("датчик4", "датчик5", 307)
    city_graph2.add_edge_by_vertices("датчик4", "датчик6", 1704)
    city_graph2.add_edge_by_vertices("датчик5", "датчик11", 887)
    city_graph2.add_edge_by_vertices("датчик5", "датчик12", 1015)
    city_graph2.add_edge_by_vertices("датчик11", "датчик6", 805)
    city_graph2.add_edge_by_vertices("датчик11", "датчик9", 721)
    city_graph2.add_edge_by_vertices("датчик11", "датчик12", 225)
    city_graph2.add_edge_by_vertices("датчик12", "датчик9", 702)
    city_graph2.add_edge_by_vertices("датчик12", "датчик10", 968)
    city_graph2.add_edge_by_vertices("датчик9", "датчик6", 588)
    city_graph2.add_edge_by_vertices("датчик9", "датчик15", 543)
    city_graph2.add_edge_by_vertices("датчик9", "датчик10", 604)
    city_graph2.add_edge_by_vertices("датчик10", "датчик15", 923)
    city_graph2.add_edge_by_vertices("датчик6", "датчик13", 238)
    city_graph2.add_edge_by_vertices("датчик13", "датчик7", 613)
    city_graph2.add_edge_by_vertices("датчик13", "датчик15", 396)
    city_graph2.add_edge_by_vertices("датчик13", "датчик8", 482)
    city_graph2.add_edge_by_vertices("датчик7", "датчик8", 190)
    city_graph2.add_edge_by_vertices("датчик8", "датчик14", 81)
    city_graph2.add_edge_by_vertices("датчик14", "датчик15", 123)

    distances, path_dict = dijkstra(city_graph2, "датчик1")
    name_distance: Dict[str, Optional[int]] = distance_array_to_vertex_dict(city_graph2, distances)
    print("Расстояние от датчик3:")
    for key, value in name_distance.items():
        print(f"{key} : {value}")
    print("") # blank line

    print("Кратчайший путь от датчик3 к датчику15:")
    path: WeightedPath = path_dict_to_path(city_graph2.index_of("датчик1"), city_graph2.index_of("датчик15"), path_dict)
    print_weighted_path(city_graph2, path)


Но, по мне так лучше, в графическом виде все смотреть. Описывал графы здесь — статья. Если немного переработать (датчики вместо КИК), то будет наглядно и интерактивно.

Порой элементарной эвристики достаточно для решения, согласен.
Жаль, что кода нет целиком, чтобы сравнивать R и python.

Спасибо за ценный комментарий.


  1. Табличка — это head(10) маршрутов обходов, отсортированных под общей длине.
  2. Матрица расстояний между датчиками посчитана однократно после их размещения. С помощью Монте-Карло генерируем маршруты обхода.
  3. Тут 13 датчиков, но это совершенно неважно. Это просто число 13.
  4. Мы igraph обычно используем. Еще есть хорошая публикация 'Benchmark of popular graph/network packages v2'. Код в тексте приведен целиком, только на логические блоки побит.
igraph шустрый, судя по benchmarkам, только snap уступает. Жаль там визульный функционал немного страдает (нет отображения направленных графов, весов прямо на картинке).
d3.js еще хорош в плане визуализации-интерактивности, но там свои заморочки с js и не уверен, что он быстрее.

Возможно, для вашей задачи не критично, но так неправильно генерировать равномерно распределённые точки на диске.
angle = runif(n(), min = 0, max = 2pi),
r = runif(n(), min = 0, max = 1),
x = r
cos(angle), y = r * sin(angle)
при таком подходе плотность точек в центре больше, чем по краям.
Вот тут описан правильный способ. https://stats.stackexchange.com/questions/120527/simulate-a-uniform-distribution-on-a-disc

совершенно согласен. но я и не генерирую равномерно распределенные. просто накидал зарядов. мне по сути все равно, знаю, что они застабилизируются.
это опытное знание извне задачи (физика).

Sign up to leave a comment.

Articles