#path #shortest
#путь #кратчайший
Вопрос:
В принципе, я хочу найти кратчайшие пути для всех (s, t) пар, но с учетом нескольких соображений. Например, сеть содержит несколько кластеров / сообществ или группу узлов. Эти группы будут предопределены и могут быть относительно большими по количеству узлов.
Я хочу найти кратчайшие пути для всех пар s, t, которые пересекают хотя бы один узел, например, из gourp1. В общем случае, если у меня есть только одна группа узлов, проблема сводится к традиционной центральности между ними. Позже я хотел бы найти для всех пар s, t кратчайших путей, которые пересекают хотя бы один узел из gourp1 и group2.
Есть предложения?
Спасибо! 🙂
Ответ №1:
Согласно вашему описанию, мне кажется, что вы готовы получить кратчайшие пути для отдельной группы узлов. Если вы готовы это сделать, я думаю, вы движетесь в правильном направлении.
Будет надежнее, если вы сможете найти кратчайшие пути отдельных групп, а затем объединить узлы разных групп вместе. Это должно сэкономить время.
Я думаю, вы можете использовать алгоритм оптимизации роя частиц для решения проблемы. Это может помочь вам с помощью нескольких роев получить кратчайший путь из разных групп. Затем вы можете объединить узлы из разных групп.
Надеюсь, это поможет. 🙂
Комментарии:
1. Большое вам спасибо за ваш ответ. Я просмотрел пару статей и увидел, что PSO используется для идентификации кратчайших путей, однако я немного обеспокоен его временной сложностью. Я знаю, что идентификация коротких путей, проходящих через определенные узлы, является дорогостоящей, однако, даст ли PSO приемлемое время вычислений для крупномасштабных сетей?
2. Поскольку у вас есть несколько групп, кажется, что PSO будет более эффективным, чем другие, поскольку основная рабочая процедура PSO соответствует вашим требованиям. И это очень эффективно для больших масштабов (хотя иногда это может быть проблемой). Если вы можете найти лучшие решения отдельных групп с меньшей сложностью, то общая сложность должна уменьшиться.