Я пытаюсь смоделировать сеть узлов беспроводных датчиков, чтобы исследовать надежность сети. Я столкнулся со следующей проблемой:
У меня есть сеть узлов с некоторыми граничными мощностями. Это эквивалентно проблеме сетевого потока в алгоритмах. Есть исходный узел (который обнаруживает определенные события) и приемный узел (моя базовая станция). Теперь я хочу найти минимальное значение s-t в сети, чтобы минимизировать размер исходного набора. Под набором источников здесь понимается набор узлов, разделенных отрезком min s-t, который содержит источник.
например. если первый разрез, C = {S, T}
, то есть набор ребер, которые можно удалить, чтобы разделить сеть на два набора, S
и T
и набор S
содержит источник, а T
содержит сток. Разрез минимален, когда сумма мощностей кромок в разрезе минимальна среди всех возможных разрезов s-t. Таких минимальных разрезов может быть несколько. Мне нужно найти минимальный разрез, который имеет наименьшее количество элементов в наборе S
Обратите внимание, что это не исходная проблема, но я попытался упростить ее, чтобы выразить ее в терминах алгоритмов.