优化算法Java

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了优化算法Java，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2965字，纯文字阅读大概需要5分钟。

内容图文

嗨,我有以下方法.它所做的是找到从N x M矩阵的左上角到右下角的所有可能路径.我想知道优化速度的最佳方法是什么,因为它现在有点慢.然后将生成的路径存储在一组中.

编辑我忘了澄清一下,您只能向下或向右移动到相邻的地点,而从当前位置开始没有对角线

For example
ABC
DEF
GHI

从左上方到右下方的路径为ADEFI

static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) {
    String newString = tempString + arr[i][j];
    if (i == m -1 && j == n-1) {
        palindrome.add(newString);
        return;
    }
    //right
    if (j+1 < n) {
        printPaths (newString, i, j+1, m, n, arr, palindrome);
    }
    //down
    if (i+1 < m) {
        printPaths (newString, i+1, j, m, n, arr, palindrome);          
    }
}

编辑这是完整的代码

public class palpath {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("palpath.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("palpath.out")));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int d = Integer.parseInt(st.nextToken());


        char[][] grid = new char [d][d];

        String index = null;

        for(int i = 0; i < d; i++)
        {
            String temp = br.readLine();
            index = index + temp;
            for(int j = 0; j < d; j++)
            {
                grid[i][j] = temp.charAt(j);
            }
        }

        br.close();

        int counter = 0;

        HashSet<String> set = new HashSet<String>();
        printPaths ("", 0, 0, grid.length, grid[0].length, grid, set);

        Iterator<String> it = set.iterator();
        while(it.hasNext()){
            String temp =  it.next();
            StringBuilder sb = new StringBuilder(temp).reverse();
            if(temp.equals(sb.toString()))  {
                counter++;
            }

        }




        pw.println(counter);
        pw.close();

    }


        static public void printPaths (String tempString, int i, int j, int m, int n, char [][] arr, HashSet<String> palindrome) {
            String newString = tempString + arr[i][j];
            if (i == m -1 && j == n-1) {
                palindrome.add(newString);
                return;
            }
            //right
            if (j+1 < n) {
                printPaths (newString, i, j+1, m, n, arr, palindrome);
            }
            //down
            if (i+1 < m) {
                printPaths (newString, i+1, j, m, n, arr, palindrome);          
            }
        }

解决方法:

给定一个长度为M x N的图,从(0,0)到(M-1,N-1)的所有路径仅涉及向右和向下移动,可以保证完全包含M-1向右移动,而N-1向下移动.

这为我们提供了一个有趣的属性：我们可以将(0,0)到(M-1,N-1)的路径表示为二进制字符串(0表示向右移动,1表示向下移动).

因此,问题就变成了：我们可以多快打印出该位字符串的排列列表？

相当快.

public static void printPaths(char[][] arr) {
    /* Get Smallest Bitstring (e.g. 0000...111) */
    long current = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        current <<= 1;
        current |= 1;
    }

    /* Get Largest Bitstring (e.g. 111...0000) */
    long last = current;
    for (int i = 0; i < arr[0].length - 1; i++) {
        last <<= 1;
    }

    while (current <= last) {
        /* Print Path */
        int x = 0, y = 0;
        long tmp = current;
        StringBuilder sb = new StringBuilder(arr.length + arr[0].length);
        while (x < arr.length && y < arr[0].length) {
            sb.append(arr[x][y]);
            if ((tmp & 1) == 1) {
                x++;
            } else {
                y++;
            }
            tmp >>= 1;
        }
        System.out.println(sb.toString());

        /* Get Next Permutation */
        tmp = (current | (current - 1)) + 1;
        current = tmp | ((((tmp & -tmp) / (current & -current)) >> 1) - 1);
    }
}

内容总结

以上是互联网集市为您收集整理的优化算法Java全部内容，希望文章能够帮你解决优化算法Java所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---