V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
hourui
V2EX  ›  程序员

路径求解问题, 寻找算法大神指点

  •  
  •   hourui ·
    cuber · 2014-05-15 01:48:38 +08:00 · 2981 次点击
    这是一个创建于 3934 天前的主题,其中的信息可能已经有所发展或是发生改变。
    今天做项目遇到了一个棘手的问题, 整理归纳以后大致总结为是一个路径求解问题
    问题如下, 以及经过无数脑细胞过度死亡后, 粗略的尾递归解法一并给出
    <?php
    // --------------------------------------
    // 通往
    // 假设 [begin] -> [end] 之间有 N 个step
    // 每个 step.i 又有 iM 个节点
    // 需要求解 [begin] -> [end] 所有路径组合
    // --------------------------------------
    // ----
    // 示例
    // ----
    $eg = array( // --------
    // [begin]
    array('a1', 'a2' /* ...aM */), // step.1
    array('b1', 'b2', 'b3', 'b4'), // step.2
    array('c1', 'c2') // step.3
    // ...
    // step.N
    // [end]
    ); // -------
    // -----------------------------------------------
    // 求解 step.1 -> step.2 -> step.3 [-> ... step.N]
    // 所有路径组合
    // -----------------------------------------------
    // -------
    // 预期结果
    // -------
    $result = array(
    array('a1', 'b1', 'c1'),
    array('a1', 'b1', 'c2'),
    array('a1', 'b2', 'c1'),
    array('a1', 'b2', 'c2'),
    array('a1', 'b3', 'c1'),
    array('a1', 'b3', 'c2'),
    array('a1', 'b4', 'c1'),
    array('a1', 'b4', 'c2'),
    array('a2', 'b1', 'c1'),
    array('a2', 'b1', 'c2'),
    array('a2', 'b2', 'c1'),
    array('a2', 'b2', 'c2'),
    array('a2', 'b3', 'c1'),
    array('a2', 'b3', 'c2'),
    array('a2', 'b4', 'c1'),
    array('a2', 'b4', 'c2'),
    );
    view raw 1.Q.php hosted with ❤ by GitHub
    <?php
    //
    // 尾递归解法
    //
    $N = count($eg);
    function go($step) {
    global $eg, $r, $N;
    if (!$step) {
    $r = array_map(function ($v) {
    return array($v);
    }, $eg[$step]);
    } else {
    $result = array();
    foreach ($r as $v)
    foreach ($eg[$step] as $ins) {
    $v[$step] = $ins;
    $result[] = $v;
    }
    $r = $result;
    }
    return ++$step < $N ? go($step) : true;
    }
    go(0);
    foreach ($r as $v) echo implode(" -> ", $v), PHP_EOL;
    /*
    程序运行结果如下
    --------------
    a1 -> b1 -> c1
    a1 -> b1 -> c2
    a1 -> b2 -> c1
    a1 -> b2 -> c2
    a1 -> b3 -> c1
    a1 -> b3 -> c2
    a1 -> b4 -> c1
    a1 -> b4 -> c2
    a2 -> b1 -> c1
    a2 -> b1 -> c2
    a2 -> b2 -> c1
    a2 -> b2 -> c2
    a2 -> b3 -> c1
    a2 -> b3 -> c2
    a2 -> b4 -> c1
    a2 -> b4 -> c2
    --------------
    */
    view raw 2.A.php hosted with ❤ by GitHub
    //
    // 非递归的 c++ stl 实现版本
    //
    #include <stdlib.h>
    #include <stdio.h>
    #include <unistd.h>
    #include <stdint.h>
    #include <iostream>
    #include <string>
    #include <map>
    #include <vector>
    using namespace std;
    static const char
    *a[] = {"a1", "a2"},
    *b[] = {"b1", "b2", "b3", "b4"},
    *c[] = {"c1", "c2"};
    static const struct {
    const char **s; int n;
    } e[] = {
    { a, sizeof(a) / sizeof(char *) },
    { b, sizeof(b) / sizeof(char *) },
    { c, sizeof(c) / sizeof(char *) }
    };
    static const int N = 3;
    static void init(vector<vector<string> > & v)
    {
    for (int i = 0; i < N; i++) {
    const char ** s = e[i].s;
    v.push_back(vector<string>(s, s + e[i].n));
    }
    }
    static void multi(vector<vector<string> > & r, vector<string> & v)
    {
    vector<string> item;
    vector<vector<string> > result;
    for (size_t i = 0; i < r.size(); i++) {
    vector<string>(r[i]).swap(item);
    item.push_back("");
    for (size_t j = 0; j < v.size(); j++) {
    item[item.size() - 1] = v[j];
    result.push_back(item);
    }
    }
    result.swap(r);
    }
    int main()
    {
    vector <vector<string> > v, r; init(v);
    vector<string> first(*v.begin());
    for (size_t i = 0; i < first.size(); i++)
    r.push_back(vector<string>(1, first[i]));
    for (size_t i = 1; i < v.size(); i++) multi(r, v[i]);
    for (size_t i = 0; i < r.size(); i++) {
    for (size_t j = 0; j < r[i].size(); j++) {
    if (j) printf(" -> ");
    printf("%s", r[i][j].c_str());
    }
    printf("\n");
    }
    return 0;
    }
    view raw 3.A.cc hosted with ❤ by GitHub

    由于项目是c++的(转换为php仅是为了方便大家阅读)
    此法会导致大量的内存分配和释放, 效率并不是很高!
    想问下v2上的算法大神, 有无更高效的解决方案?
    第 1 条附言  ·  2014-05-15 11:09:09 +08:00
    昨天和基友@napoleonu 思索到深夜...
    找到了一种「矩阵法」求解方式, 简单理解为把结果想象为一个矩阵, 然后做填空题
    代码实现如下:
    <?php
    $e = array(
    array('a1', 'a2'),
    array('b1', 'b2', 'b3', 'b4'),
    array('c1', 'c2'),
    );
    $N = count($e);
    $r = array();
    $n = array_fill(0, $N, 1);
    for ($i = 1; $i < $N; $i++)
    for ($j = $i; $j < $N; $j++) {
    $cnt = count($e[$j]);
    $n[$i - 1] *= $cnt;
    }
    $h = $n[0] * count($e[0]);
    for ($i = 0; $i < $h; $i++)
    for ($j = 0; $j < $N; $j++) {
    $m = intval($i / $n[$j]) % (count($e[$j]));
    $r[$i][$j] = $e[$j][$m];
    }
    echo "n:", PHP_EOL, implode(" -> ", $n), PHP_EOL;
    echo "res:", PHP_EOL;
    foreach ($r as $v) echo implode(" -> ", $v), PHP_EOL;
    /*
    output:
    --------------
    n:
    8 -> 2 -> 1
    --------------
    res:
    a1 -> b1 -> c1
    a1 -> b1 -> c2
    a1 -> b2 -> c1
    a1 -> b2 -> c2
    a1 -> b3 -> c1
    a1 -> b3 -> c2
    a1 -> b4 -> c1
    a1 -> b4 -> c2
    a2 -> b1 -> c1
    a2 -> b1 -> c2
    a2 -> b2 -> c1
    a2 -> b2 -> c2
    a2 -> b3 -> c1
    a2 -> b3 -> c2
    a2 -> b4 -> c1
    a2 -> b4 -> c2
    --------------
    */
    view raw 1.matrix.php hosted with ❤ by GitHub
    #include <stdlib.h>
    #include <stdio.h>
    #include <unistd.h>
    #include <stdint.h>
    #include <iostream>
    #include <string>
    #include <map>
    #include <vector>
    using namespace std;
    static const char
    *a[] = {"a1", "a2"},
    *b[] = {"b1", "b2", "b3", "b4"},
    *c[] = {"c1", "c2"};
    static const struct {
    const char **s; int n;
    } e[] = {
    { a, sizeof(a) / sizeof(char *) },
    { b, sizeof(b) / sizeof(char *) },
    { c, sizeof(c) / sizeof(char *) }
    };
    static const int N = 3;
    static int h = 1;
    static vector<int> n(N, 1);
    static void init(vector<vector<string> > & v)
    {
    for (int i = 0; i < N; i++) {
    int n = e[i].n; h *= n;
    const char ** s = e[i].s;
    v.push_back(vector<string>(s, s + n));
    if (i) for (int j = i; j < N; j++) ::n[i - 1] *= e[j].n;
    }
    }
    int main()
    {
    vector <vector<string> > v; init(v);
    vector <vector<string> > r(h, vector<string>(N, ""));
    for (int i = 0; i < h; i++)
    for (int j = 0; j < N; j++) r[i][j] = e[j].s[i / n[j] % e[j].n];
    for (size_t i = 0; i < r.size(); i++) {
    for (size_t j = 0; j < r[i].size(); j++) {
    if (j) printf(" -> ");
    printf("%s", r[i][j].c_str());
    }
    printf("\n");
    }
    return 0;
    }
    view raw 2.matrix.cc hosted with ❤ by GitHub
    #include <stdlib.h>
    #include <stdio.h>
    #include <unistd.h>
    #include <stdint.h>
    #include <string.h>
    static const char
    *a[] = {"a1", "a2"},
    *b[] = {"b1", "b2", "b3", "b4"},
    *c[] = {"c1", "c2"};
    typedef struct {
    const char **s; int n;
    } vector;
    static vector
    e[] = {
    { a, sizeof(a) / sizeof(char *) },
    { b, sizeof(b) / sizeof(char *) },
    { c, sizeof(c) / sizeof(char *) }
    },
    *r = NULL;
    static const int N = sizeof(e) / sizeof(vector);
    static int h = 1, n[N];
    static void init(void)
    {
    for (int i = 0; i < N; i++) {
    n[i] = 1; if (i) for (int j = i; j < N; j++) n[i - 1] *= e[j].n;
    }
    h = n[0] * e[0].n;
    r = malloc(sizeof(vector) * h);
    for (int i = 0; i < h; i++) {
    r[i].n = N;
    r[i].s = malloc(sizeof(char *) * N);
    }
    }
    static void destroy(void)
    {
    for (int i = 0; i < h; i++) free(r[i].s);
    free(r); r = NULL;
    }
    int main()
    {
    init();
    for (int i = 0; i < h; i++)
    for (int j = 0; j < N; j++) r[i].s[j] = e[j].s[i / n[j] % e[j].n];
    for (size_t i = 0; i < h; i++) {
    for (size_t j = 0; j < N; j++) {
    if (j) printf(" -> ");
    printf("%s", r[i].s[j]);
    }
    printf("\n");
    }
    destroy();
    return 0;
    }
    view raw 3.matrix.c hosted with ❤ by GitHub

    欢迎各路大神交流
    9 条回复    2014-05-16 00:35:51 +08:00
    akfish
        1
    akfish  
       2014-05-15 01:58:21 +08:00
    未细看,如果瓶颈仅仅在于内存的分配和释放的话,尝试一次性分配足够空间,反复重用。
    txx
        2
    txx  
       2014-05-15 02:31:04 +08:00
    數據規模是多大?
    davidli
        3
    davidli  
       2014-05-15 04:05:33 +08:00
    既然是因为a的数量太多导致内存占用, 为什么不把a分割一下再分别处理呢
    iloahz
        4
    iloahz  
       2014-05-15 07:31:33 +08:00
    大概看了一遍,复杂度和空间都是理论下限了。到了常数阶段的话,可以试试:

    1. 少用stl
    2. 不要玩字符串,hash它
    PS3. 个人觉得递归版很合理了,唯一是不要把数组当int玩啊。。
    exch4nge
        5
    exch4nge  
       2014-05-15 10:15:43 +08:00
    字符串上的消耗比较大吧,基本同意 @iloahz 的。
    话说为什么用递归(尾递归)?不是直接可以嵌套循环么?
    尾递归如果编译器没优化的话,不是因为push/pop stack的原因效率会更慢么?
    hourui
        6
    hourui  
    OP
       2014-05-15 11:04:54 +08:00
    @akfish 数据宽度和深度都是未知, 所以无法预估空间消耗...
    @txx 这是跑在一个在线engine上的, 对于性能要求很高, 由于每次轮询都需要重新构建vector, 数据膨胀造成的性能下降不是线性的... 所以我觉得这不是最优解...
    @iloahz 为了方便理解, 直接写成string了, 实际项目中已经做过一次onway hash, string的频繁构建析构是不存在的
    @exch4nge 你可以看下c++的版本, 是一个循环解法, 是php版本尾递归的非递归实现
    napoleonu
        7
    napoleonu  
       2014-05-15 11:47:54 +08:00
    酷。
    fengxx
        8
    fengxx  
       2014-05-15 22:53:52 +08:00
    这个可以看成是一个 Mixed radix numbers, 我们常用的是10进制数,比如3位以内的数字排列是0-999。如果是mixed radix 的话,可以看成第1位最大为X, 第2位最大为Y, 第3位为 Z, 那么所有的排列是
    0 到 ZYX, 例如:
    000
    001
    002
    ....
    00X
    010 (这里产生了进位)
    011
    ...
    01X
    020(这里产生了进位)
    .....
    ....



    所有的排列之和为 X*Y*Z

    java code

    /**
    *
    * @author Ted
    */
    public class MixedRadix {

    public void permutation(String[][] elements) {
    int[] mixedRadix = new int[elements.length + 1];
    int[] number = new int[elements.length + 1];
    //init
    for (int i = 0; i < elements.length; i++) {
    mixedRadix[i] = elements[i].length - 1;
    }
    //sentinel
    number[elements.length] = 1;
    int bits = 0;
    while (bits < elements.length) {
    printChoice(elements, number);
    int j = 0;
    while (number[j] == mixedRadix[j]) {
    number[j] = 0;
    j++;
    }
    number[j] = number[j] + 1;
    bits = j;
    }

    }

    private void printChoice(String[][] elements, int[] choice) {
    for (int i = 0; i < choice.length - 1; i++) {
    System.out.print(elements[i][choice[i]] + " ");
    }
    System.out.println("");
    }

    public static void main(String... args) {
    String[][] elements = {
    {"a1", "a2"}, {"b1", "b2", "b3", "b4"}, {"c1", "c2"}
    };
    MixedRadix mr = new MixedRadix();
    mr.permutation(elements);
    }
    }


    如果对这类问题感兴趣,可以参考 free book <Matters Computational>
    http://www.jjj.de/fxt/fxtpage.html#fxtbook
    hourui
        9
    hourui  
    OP
       2014-05-16 00:35:51 +08:00
    @fengxx 「Mixed radix numbers」这个思路赞. 谢谢指点
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1190 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 23:16 · PVG 07:16 · LAX 15:16 · JFK 18:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.