什么是快速而稳定的算法在节点图随机路径？ [英] What's a fast and stable algorithm for a random path in a node graph?

问题描述

我有一个曲线图包括节点，我需要一个快速的算法，生成两个节点之间的随机路径。我设计了几种算法从头此想，但似乎无法得到它的权利。

i have a graph which consists of nodes, and i need a fast algorithm that generates a random path between two nodes. i designed several algorithms from scratch for this want but can't seem to get it right.

无论是算法陷在循环中，或者当我把访问节点记录它有时会卡住访问节点之间。另一个问题我遇到的是，我的算法是太不稳定的表现。

either the algorithm gets stuck in loops, or when i keep record of the visited nodes it sometimes gets stuck between visited nodes. another problem i encountered is that my algorithm was too unstable in performance.

所以我的问题是;没有人知道在无向图一个快速，稳定的算法两个可达节点之间的一个随机路径？的

推荐答案

让你的曲线是 G =（V，E）。创建一个子集 U 的 V ，使得 U = {U |有目标从u路径} 。

Let your graph be G=(V,E). Create a subset U of V such that U = { u | there is a path from u to the target }.

• 注意要找到这个子集 U 很容易 - 并且可以在线完成 一次使用 DFS 或的 BFS 目标。

• Note that finding this subset U is easy - and can be done in linear time using DFS or BFS on the reversed edges from the target.

使用这个子集，创建一个图 G'=（U，E'），其中 U 定义如上和 E'= E [交集] UxU [相同的边缘，但只适用于在顶点 U 。

Using this subset, create a graph G'=(U,E') where U is defined above and E' = E [intersection] UxU [The same edges, but applied only on vertices in U].

运行随机（选择哪些顶点到下一个随机探索） DFS 上 G'，直到你达到目标。

Run randomized (choosing which vertex to explore next on random) DFS on G' until you reach the target.

• 注 - 这个想法是要找到一个路径 - 不necesseraly简单，所以你不应该保持一个访问设置
。
• 您可以添加一个破规矩，如果你达到一定深度时，你会寻求的目标 - unrandomised，以避免在圈子无限循环
• Perofrmance有望被改变，因为它是线性​​的发现路径的长度，这可能是很长或非常短...

• Note - the idea is to find a path - not necesseraly simple, and thus you shouldn't maintain a visited set.
• You might add a "break rule" that if you reach a certain depth, you will seek the target - unrandomised, to avoid infinite loops in circles.
• Perofrmance is expected to be varying, since it is linear in the length of the found path, which might be very long or very short...

这篇关于什么是快速而稳定的算法在节点图随机路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！