Проблема Осветление
ввода данных представляет собой набор из т строк из п столбцов вероятностей, по существу т на п матрицы, где т = п = число вершин на ориентированного графа. Строки являются краевыми источниками, а столбцы - пограничными. Мы будем на основании упоминания циклов в вопросе, что граф является циклическим, что по крайней мере один цикл существует в графе.
Определим стартовую вершину как s. Давайте также определим терминальную вершину как вершину, для которой нет выходящих ребер, а множество из них задано T с размером z. Поэтому мы имеем z наборов маршрутов от s до вершины в T, а размеры множества могут быть бесконечными из-за циклов . В таком сценарии нельзя сделать вывод, что конечная вершина будет достигнута на сколь угодно большом числе шагов.
Во входных данных вероятности для строк, которые соответствуют вершинам, не входящим в T, нормированы на общую величину до 1,0. Будем считать свойство Маркова, что вероятности в каждой вершине не меняются со временем. Это исключает использование вероятности для определения приоритетов маршрутов в графическом поиске .
Конечные математические тексты иногда называют пример проблемы, подобные этому вопросу, как Drunken блуждания подчеркнуть тот факт, что ходунки забывает прошлое, со ссылкой на памяти свободной природы марковских цепей.
Применение Вероятность Маршруты
Вероятность прибытия в терминальной вершине может быть выражена в виде бесконечной серии суммы произведений.
Р т = Пт с -> ∞ Σ ∏ Р I, J,
, где s является индексом шаг, т является индексом конечной вершиной, я ∈ [1. м.] и J ∈ [1 .. п]
Снижение
Когда два или более цикла пересекаются (разделяя одну или несколько вершин), анализ осложняется бесконечным набором шаблонов, связанных с ними. По-видимому, после некоторого анализа и обзора relevant academic work, что получение точного набора вероятностей прибытия конечных вершин с помощью современных математических инструментов лучше всего выполнить с помощью сходящегося алгоритма.
Возможны несколько первоначальных сокращений.
Первое соображение состоит в том, чтобы перечислить конечную вершину, что легко, так как соответствующие строки имеют вероятности нуля.
Следующее соображение состоит в том, чтобы отличить любые дальнейшие сокращения от того, что академическая литература называет неприводимыми субграфами. Первый алгоритм глубины глубины запоминает, какие вершины уже были посещены при построении потенциального маршрута, поэтому его можно легко модифицировать, чтобы определить, какие вершины задействованы в циклах. Однако рекомендуется использовать существующие проверенные, проверенные коллегами библиотеки графов, чтобы идентифицировать и характеризовать субграфы как неприводимые.
Математическое сокращение неприводимых частей графика может быть или не быть правдоподобным. Рассмотрим начальную вершину A и единственную конечную вершину B в графе, представленную в виде {A-> C, C-> A, A-> D, D-> A, C-> D, D-> C, C-> B, D-> B}.
Хотя можно уменьшить график до вероятностных отношений, отсутствующих в циклах через вершину А, вершина А не может быть удалена для дальнейшего восстановления без изменения вероятностей вершин, выходящих из С и D, или допускающих как общие суммы вероятностей ребер, выходящих из С и D меньше 1,0.
конвергентной Ширина первого Прослеживание
широта первого обхода, который игнорирует пересматривает и позволяет циклы могут итерации шаг индекс s, а не к некоторым фиксированному с макс, но в какую-то достаточно стабильную и точную точку в сходящемся тренде , Этот подход особенно называется, если циклы перекрываются, создавая бифуркации в более простой периодичности, вызванной одним циклом.
Σ Р сΔ с.
Для создания разумной сходимости в ы возрастает, необходимо определить требуемую точность в качестве критериев для завершения алгоритма сходимости и метрик для измерения точности, глядя на долгосрочные тенденциях в результатах на все терминальные вершины. Возможно, важно предоставить критерии, в которых сумма вероятностей конечных вершин близка к единице в сочетании с метрикой сходимости тренда, как как проверка на соответствие, так и критерии точности. Практически могут потребоваться четыре критерия конвергенции .
- на терминал вершины вероятности тенденция конвергенции дельту
- Средняя тенденция вероятности сходимость дельта
- Сходимости полной вероятности на единстве
- Общего числа шагов (с колпачком глубины для практических вычислений причин)
Даже за этими четырьмя программами может потребоваться ловушка для прерывания, которая позволяет писать и последующую проверку вывода после долгого ожидания без satis сражаясь со всеми четырьмя критериями.
Пример Цикл Устойчива Глубина первого алгоритм
Существуют более эффективные алгоритмы, чем следующие один, но это довольно приемлемо, он компилирует без предупреждения с 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] Вероятности иногда используются для уменьшения CPU циклическая стоимость поиска. Вероятности, в этой стратегии, являются входными значениями мета-правил в очереди приоритетов, чтобы уменьшить вычислительную проблему очень утомительных поисков (даже для компьютера). Ранняя литература в производственных системах назвала экспоненциальный характер неуправляемых крупных поисков комбинационных взрывов.
[3] Это может быть практически необходимо, чтобы обнаружить ширину первой вероятности тенденции в каждой вершине и указать удовлетворительную сходимость в терминах четырех критериев
- Δ (Σ ∏ Р) т < = Δ макс & forall; т
- Σ т = 0Т Δ (Σ ∏ Р) т/Т = < Δ просп
- | Σ Σ ∏ P - 1 | < = и макс, где и максимальное допустимое отклонение от единицы на сумму финальных вероятностей
- сек < S макс
[4] При условии, имеется достаточное количество вычислительных ресурсов, доступных для поддержки структуры данных и достаточное время для получения ответа на заданную скорость вычислительной системы.
[5] Вы можете загрузить DirectedGraph dg (7) с входными данными, используя два цикла, вложенные в итерацию по строкам и столбцам, перечисленным в вопросе. Тело внутреннего цикла было бы просто добавлением условного края.
if (prob != 0) dg.addEdge(i, j);
Переменный проб является Р т, п. Существование маршрута связано только с нулевым/ненулевым статусом.
Вы избегаете бесконечных циклов, блокируя уже посещенный узел. Ничего неприятного в этом нет, используете ли вы рекурсивное решение или что-то вроде алгоритма Дейкстры. –
@WeatherVane Вы говорите, что восемь разных путей, перечисленных мной, уже являются окончательным результатом? Я считаю, что на самом деле допускается бесконечное число циклов, так как оно становится своего рода геометрическим рядом в вероятности прохождения цикла (в простейшем случае из 1 цикла), который сходится к конечному числу. Моя проблема в том, что есть много циклов и несколько пересекающихся. Тогда я не вижу, как обобщить геометрический ряд. – Kagaratsch
Вы спросили, как удалить циклы. –