个人中心
gpt4 book ai didi

algorithm - 如何通过网络中的节点生成随机路径

转载 作者：塔克拉玛干 更新时间：2023-11-03 03:13:44 24 4
gpt4 key购买 nike

我有一个由 N 个节点连接在一起的常规网络，我想生成一条仅访问 n 个节点一次的路径。我还要求路径具有一定程度的随机性，以便我能够在给定相同起始节点的情况下创建不同的路径。

See the problem illustration here.

我目前的解决方案是随机选择一个起始节点，然后随机访问一个相邻节点，如此重复直到我访问了n 个节点。每当路径不允许我访问 n 个节点时，我就会回溯以尝试通过另一个节点。

当节点和连接的数量较小时，这工作正常，但是当这些增加并且 n 接近 N 时，如果有的话，需要很长时间才能找到解决方案.

您能否建议保证在合理时间内成功的替代方法？

最佳答案

与其尝试创建一条独特的路径，这会导致您陷入许多死胡同，您可以创建一条路径作为分支路径的轮廓。这样的路径将有相邻的起点和终点。

下图概述了所提出算法的步骤:

Four steps of the proposed algorithm

首先，将您的网格分成两半 (a)。如果您的其中一个维度是奇数，请忽略最后一行或最后一列。

现在在粗网格 (b) 上创建一个分支的、连接的迷宫。有很多算法；评论中提到了 Prim 的算法，但如果不考虑回溯，也可以使用贪心路径搜索。迈克博斯托克的 Visualizing Algorithms展示了一些迷宫生成算法；它们位于长页面的底部附近。

接下来，创建迷宫的轮廓。这为您提供了一个简单的路径，如果其尺寸为偶数 (c)，则该路径可以访问原始网格中的所有节点。起点和终点将相邻；距离关闭仅一步之遥。

如果原始网格的任何维度是奇数，您可以拉伸(stretch)随机行或列以覆盖整个网格 (d)。请注意，您必须为每个 intersectiong 行或列插入一个新段。否则，将不会访问某些节点。 (当两个维度都是奇数时，可能会出现问题，必须调整，所以这是算法的另一个限制:最多一个维度可以是奇数。)

编辑:下面是 Javascript 中的概念验证实现(没有步骤 d)。这是一个完整的网页，您可以将其另存为 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>

关于algorithm - 如何通过网络中的节点生成随机路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35138905/

24 4 0
文章推荐： java - 用于 Web 服务开发的 Sun Metro 和 Apache CXF 之间的比较？
文章推荐： java - 检测 API 变化/演变
文章推荐： java - 如何解决 swing 监听器内存泄漏？
文章推荐： java - 在 Ubuntu 中正确设置 java 类路径和 java_home
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com