V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hourui
V2EX  ›  程序员

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

  •  
  •   hourui ·
    cuber · 2014-05-15 01:48:38 +08:00 · 2932 次点击
    这是一个创建于 3846 天前的主题,其中的信息可能已经有所发展或是发生改变。
    今天做项目遇到了一个棘手的问题, 整理归纳以后大致总结为是一个路径求解问题
    问题如下, 以及经过无数脑细胞过度死亡后, 粗略的尾递归解法一并给出

    由于项目是c++的(转换为php仅是为了方便大家阅读)
    此法会导致大量的内存分配和释放, 效率并不是很高!
    想问下v2上的算法大神, 有无更高效的解决方案?
    第 1 条附言  ·  2014-05-15 11:09:09 +08:00
    昨天和基友@napoleonu 思索到深夜...
    找到了一种「矩阵法」求解方式, 简单理解为把结果想象为一个矩阵, 然后做填空题
    代码实现如下:

    欢迎各路大神交流
    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   ·   实用小工具   ·   2778 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 07:07 · PVG 15:07 · LAX 23:07 · JFK 02:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.