Направленный граф вероятности — алгоритм сокращения циклов?

{{0, 1/2, 0, 1/14, 1/14, 0, 5/14},
{0, 0, 1/9, 1/2, 0, 7/18, 0},
{1/8, 7/16, 0, 3/16, 1/8, 0, 1/8},
{0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0}}

{{1/14, {1, 5}}, {5/14, {1, 7}}, {7/36, {1, 2, 6}},
{1/144, {1, 2, 3, 5}}, {1/144, {1, 2, 3, 7}},
{1/36, {1, 4, 2, 6}}, {1/1008, {1, 4, 2, 3, 5}}, {1/1008, {1, 4, 2, 3, 7}}}

{{1/144, {2, 3, 1}}, {7/144, {3, 2}}, {1/2, {4, 2}},
{1/48, {3, 4, 2}}, {1/1008, {4, 2, 3, 1}}}

Разъяснение проблемы

Входные данные представляют собой набор из m строк из n столбцов вероятностей, по сути, матрицы m на n, где m = n = количество вершин в ориентированном графе. Строки — это начало, а столбцы — это назначение. На основании упоминания циклов в вопросе мы будем считать, что граф циклический, что в нем существует хотя бы один цикл.

Давайте определим начальную вершину как s. Давайте также определим терминальную вершину как вершину, для которой нет выходящих ребер, и набор их как набор T с размером z. Поэтому у нас есть z наборов маршрутов от s до вершины в T, и размеры наборов могут быть бесконечными из-за циклов ¹. При таком сценарии нельзя сделать вывод, что конечная вершина будет достигнута за сколь угодно большое количество шагов.

Во входных данных вероятности для строк, которые соответствуют вершинам, не принадлежащим T, нормализованы до общего значения 1,0. Предположим свойство Маркова, что вероятности в каждой вершине не меняются со временем. Это исключает использование вероятности для определения приоритетности маршрутов при поиске в графике. ².

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

Применение вероятности к маршрутам

Вероятность достижения конечной вершины может быть выражена как сумма произведений бесконечной серии.

п_T = лим _{s -> ∞} Σ ∏ P_{я, дж},

где s — индекс шага, t — индекс терминальной вершины, i ∈ [1 .. m] и j ∈ [1 .. n]

снижение

Когда два или более цикла пересекаются (разделяя одну или несколько вершин), анализ усложняется бесконечным набором паттернов, включающих их. Похоже, после некоторого анализа и обзора соответствующая академическая работа, что достижение точного набора вероятностей прибытия конечных вершин с помощью современных математических инструментов может быть лучше всего достигнуто с помощью сходящегося алгоритма.

Возможно несколько первоначальных сокращений.

1. Первое соображение состоит в том, чтобы перечислить целевую вершину, что легко, поскольку соответствующие строки имеют вероятности ноль.

2. Следующее соображение состоит в том, чтобы дифференцировать любые дальнейшие сокращения от того, что академическая литература называет неприводимыми подграфами. Алгоритм ниже по глубине запоминает, какие вершины уже были посещены при построении потенциального маршрута, поэтому его можно легко модифицировать, чтобы определить, какие вершины участвуют в циклах. Тем не менее, рекомендуется использовать существующие хорошо проверенные и проверенные библиотеки графов, чтобы идентифицировать и охарактеризовать подграфы как неприводимые.

Математическое уменьшение неприводимых частей графика может быть или не быть правдоподобным. Рассмотрим начальную вершину A и единственную завершающую вершину B в графе, представленном как {A-> C, C-> A, A-> D, D-> A, C-> D, D-> C, C-> B, D-> B}.

Хотя можно свести граф к отношениям вероятностей, отсутствующим в циклах, через вершину A, вершину A нельзя удалить для дальнейшего сокращения, не изменив ни вероятности вершин, выходящих из C и D, ни допустив, чтобы обе суммы вероятностей ребер, выходящих из C и D, были меньше чем 1.0.

Конвергентная ширина Первый обход

Первый обход в ширину, который игнорирует повторное посещение и позволяет циклам выполнять итерации с индексом шага s, а не с некоторыми фиксированными s_{Максимум} но до некоторой достаточно устойчивой и точной точки в сходящемся тренде. Этот подход особенно необходим, если циклы перекрываются, создавая бифуркации в более простой периодичности, вызванной одним циклом.

Σ P_s^{Δ s}.

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

1. Для каждой вершины вероятность схождения тренда вероятности вершины
2. Средняя вероятность схождения тренда дельта
3. Сходимость полной вероятности на единицу
4. Общее количество шагов (чтобы ограничить глубину по практическим соображениям)

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

Пример цикла, устойчивый к глубине Первый алгоритм

Существуют более эффективные алгоритмы, чем следующий, но он достаточно понятен, он компилируется без предупреждения с помощью C ++ -Wall и выдает желаемый результат для всех конечных и допустимых ориентированных графов и возможных начальных и конечных вершин. ⁴. Матрицу в форме, указанной в вопросе, легко загрузить с помощью метода addEdge. ⁵.

#include <iostream>
#include <list>

class DirectedGraph {

private:
int miNodes;
std::list<int> * mnpEdges;
bool * mpVisitedFlags;

private:
void initAlreadyVisited() {
for (int i = 0; i < miNodes; ++ i)
mpVisitedFlags[i] = false;
}

void recurse(int iCurrent, int iDestination,
int route[], int index,
std::list<std::list<int> *> * pnai) {

mpVisitedFlags[iCurrent] = true;
route[index ++] = iCurrent;

if (iCurrent == iDestination) {
auto pni = new std::list<int>;
for (int i = 0; i < index; ++ i)
pni->push_back(route[i]);
pnai->push_back(pni);

} else {
auto it = mnpEdges[iCurrent].begin();
auto itBeyond = mnpEdges[iCurrent].end();
while (it != itBeyond) {
if (! mpVisitedFlags[* it])
recurse(* it, iDestination,
route, index, pnai);
++ it;
}
}

-- index;
mpVisitedFlags[iCurrent] = false;
}

public:
DirectedGraph(int iNodes) {
miNodes = iNodes;
mnpEdges = new std::list<int>[iNodes];
mpVisitedFlags = new bool[iNodes];
}

~DirectedGraph() {
delete mpVisitedFlags;
}

void addEdge(int u, int v) {
mnpEdges[u].push_back(v);
}

std::list<std::list<int> *> * findRoutes(int iStart,
int iDestination) {
initAlreadyVisited();
auto route = new int[miNodes];
auto pnpi = new std::list<std::list<int> *>();
recurse(iStart, iDestination, route, 0, pnpi);
delete route;
return pnpi;
}
};

int main() {

DirectedGraph dg(5);

dg.addEdge(0, 1);
dg.addEdge(0, 2);
dg.addEdge(0, 3);
dg.addEdge(1, 3);
dg.addEdge(1, 4);
dg.addEdge(2, 0);
dg.addEdge(2, 1);
dg.addEdge(4, 1);
dg.addEdge(4, 3);

int startingNode = 2;
int destinationNode = 3;

auto pnai = dg.findRoutes(startingNode, destinationNode);

std::cout
<< "Unique routes from "<< startingNode
<< " to "<< destinationNode
<< std::endl
<< std::endl;

bool bFirst;
std::list<int> * pi;
auto it = pnai->begin();
auto itBeyond = pnai->end();
std::list<int>::iterator itInner;
std::list<int>::iterator itInnerBeyond;
while (it != itBeyond) {
bFirst = true;
pi = * it ++;
itInner = pi->begin();
itInnerBeyond = pi->end();
while (itInner != itInnerBeyond) {
if (bFirst)
bFirst = false;
else
std::cout << ' ';
std::cout << (* itInner ++);
}
std::cout << std::endl;
delete pi;
}

delete pnai;

return 0;
}

---

Заметки

[1] Неправильно обработанные циклы в алгоритме ориентированного графа будут зависать в бесконечном цикле. (Обратите внимание на тривиальный случай, когда число маршрутов от A до B для ориентированного графа, представленного как {A-> B, B-> A}, равно бесконечности.)

[2] Вероятности иногда используются, чтобы уменьшить стоимость цикла ЦП поиска. Вероятности, в этой стратегии, являются входными значениями для мета-правил в очереди приоритетов, чтобы уменьшить трудоемкие поиски вычислительной задачи (даже для компьютера). Ранняя литература по производственным системам называлась экспоненциальным характером неуправляемых масштабных поисков «Комбинаторные взрывы».

[3] Может быть практически необходимо определить ширину первого вероятностного тренда в каждой вершине и указать удовлетворительную сходимость в терминах четырех критериев.

1. Δ (ΣΠP)_T <= Δ_{Максимум} ∀ т
2. Σ_{т = 0}^T Δ (ΣΠP)_T / T <= Δ_пр
3. | Σ Σ∏P — 1 | <= ты_{Максимум}, где u — максимально допустимое отклонение от единицы для суммы конечных вероятностей
4. s < S_{Максимум}

[4] При условии, что имеется достаточно вычислительных ресурсов для поддержки структур данных и достаточно времени, чтобы прийти к ответу для данной скорости вычислительной системы.

[5] Вы можете загрузить DirectedGraph dg (7) с входными данными, используя два цикла, вложенных для перебора строк и столбцов, перечисленных в вопросе. Тело внутреннего цикла будет просто условным добавлением ребра.

if (prob != 0) dg.addEdge(i, j);

Переменная проблема п _{м, п}. Наличие маршрута связано только с нулевым / ненулевым статусом.

Я понимаю это как следующую проблему:

Учитывая начальное распределение, которое должно быть на каждом узле как вектор b, и матрицу A, в которой хранится вероятность перехода с узла i на узел j на каждом временном шаге, что несколько напоминает матрицу смежности.

Тогда распределение b_1 после одного временного шага равно A x b. Распределение b_2 после двух временных шагов составляет A x b_1. Аналогично, распределение b_n является A ^ n x b.

Для приближения b_infinite мы можем сделать следующее:

Vector final_probability(Matrix A, Vector b,
Function Vector x Vector -> Scalar distance, Scalar threshold){
b_old = b
b_current = A x b
while(distance(b_old,b_current) < threshold){
b_old = b_current
b_current = A x b_current
}
return b_current
}

(Я использовал математические имена переменных для удобства)

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

Возможно, вы захотите добавить к этому максимальное количество итераций.

Евклидово расстояние должно хорошо работать как расстояние.

(Это использует концепцию Марковская цепь но это скорее прагматичное решение)