我有一个常规网络N节点连接在一起，我想要生成一个路径，访问n节点只有一次。我还要求路径中存在某种程度的随机性，以便能够在给定相同的起始节点的情况下创建不同的路径。如何通过网络中的节点生成随机路径
我当前的解决方案是选择一个随机开始节点然后随机访问相邻节点，并重复直到我访问Ñ节点。无论何时该路径不允许我访问节点，我都会回溯尝试通过另一个节点。
当节点和连接的数量小，这个工作得很好，但是当这些增加和ñ接近ň需要花费很长的，如果在所有寻找解决办法。
您能否建议保证在合理时间内成功的替代方法？
而不是试图创建一个独特的路径，这将导致你失望许多死胡同，你可以创建单路径作为分支路径的轮廓。这些路径将具有相邻的起点和终点。
这个数字概括了该算法的步骤：
首先，划分网格的一半（一）。如果其中一个维度很奇怪，请忽略最后一行或一列。
现在在粗网格（b）上创建一个分支连接的迷宫。有很多算法， Prim的算法在评论中被提及，但是如果你没有回溯，你也可以使用你的贪婪路径搜索。 Mike Bostock的Visualizing Algorithms展示了一些迷宫生成算法;他们接近长页面的底部。
接下来，创建该迷宫的轮廓。这给你一个简单的路径，如果它的尺寸甚至是（c），就访问原始网格中的所有节点。起点和终点将相邻;路径仅仅是被关闭了一步。
如果原始网格的任何维度都是奇数，则可以拉伸随机行或列以覆盖整个网格（d）。请注意，您必须为每个交点行或列插入一个新段。否则，一些节点将不会被访问。 （当两个尺寸都是奇数并且必须进行调整时可能存在问题，所以这是算法的另一个限制：最多一个维度可以是奇数。）
编辑：概念验证实现（无步骤d）在Javascript下面。这是一个完整的网页，您可以将其保存为html文件并显示在识别canvas元素的浏览器中。
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<title>Simple Path Demo</title>
<script type="text/javascript">
function array2d(w, h, val) {
var arr = [];
for (var y = 0; y < h; y++) {
var row = [];
for (var x = 0; x < w; x++) row.push(val);
arr.push(row);
}
return arr;
}
var dir = {
n: {x: 0, y: -1},
e: {x: 1, y: 0},
s: {x: 0, y: 1},
w: {x: -1, y: 0},
};
var width = 72;
var height = 72;
var node = array2d(width, height, false);
function walk(x, y, from) {
if (x < 0 || x >= width/2) return;
if (y < 0 || y >= height/2) return;
if (node[2*y][2*x]) return;
node[2*y][2*x] = true;
if (from == 'n') node[2*y + 1][2*x] = true;
if (from == 'e') node[2*y][2*x - 1] = true;
if (from == 's') node[2*y - 1][2*x] = true;
if (from == 'w') node[2*y][2*x + 1] = true;
var d = ['n', 'e', 's', 'w'];
while (d.length) {
var pick = (Math.random() * d.length) | 0;
var head = d[pick];
var next = dir[head];
d[pick] = d[d.length - 1];
d.pop();
walk(x + next.x, y + next.y, head);
}
}
function cell(x, y) {
if (y < 0 || y >= height) return false;
if (x < 0 || x >= width) return false;
return node[y][x];
}
function path(x, y) {
var x0 = x;
var y0 = y;
var res = "";
var dir = "s";
var l, r;
y++;
while (x != x0 || y != y0) {
var old = dir;
res += dir;
switch (dir) {
case "n": l = (cell(x - 1, y - 1)) ? 1 : 0;
r = (cell(x, y - 1)) ? 2 : 0;
dir = ["w", "n", "e", "e"][l + r];
break;
case "e": l = (cell(x, y - 1)) ? 1 : 0;
r = (cell(x, y)) ? 2 : 0;
dir = ["n", "e", "s", "s"][l + r];
break;
case "s": l = (cell(x, y)) ? 1 : 0;
r = (cell(x - 1, y)) ? 2 : 0;
dir = ["e", "s", "w", "w"][l + r];
break;
case "w": l = (cell(x - 1, y)) ? 1 : 0;
r = (cell(x - 1, y - 1)) ? 2 : 0;
dir = ["s", "w", "n", "n"][l + r];
break;
}
if (dir == "n") y--;
if (dir == "e") x++;
if (dir == "s") y++;
if (dir == "w") x--;
}
return res;
}
walk(0, 0);
var p = path(0, 0);
window.onload = function() {
var cv = document.getElementById("map");
var cx = cv.getContext("2d");
var s = 8;
cx.translate(2*s, 2*s);
cx.lineWidth = 2;
var x = 0;
var y = 0;
cx.beginPath();
cx.moveTo(s*x, s*y);
for (var i = 0; i < p.length; i++) {
var c = p.charAt(i);
x += dir[c].x;
y += dir[c].y;
cx.lineTo(s*x, s*y);
}
cx.stroke();
}
</script>
</head>
<body>
<canvas id="map" width="608" height="608">Kann nix.</canvas>
</body>
</html>
至于评论，我不知道，你可以找到的东西比你已经有一个无向图中未加权做快。
确保您正在实施Depth-First（或Breadth-first）搜索算法的正确版本并添加您的随机选择的相邻节点。
另一种贪婪的解决方法是随机为每个顶点定义一个权重并应用Dijkstra's algorithm。
Prim的算法和其他设计用于查找[最小生成树]（https://en.wikipedia.org/wiki/Minimum_spanning_tree） –
想找到'解决方案'或'全部'解决方案吗？ – Aravind
@Aravind一个解决方案就足够了 – mpium