0

更新：rrenaudのすばらしいコメントに基づいて、私はすべての順列を生成していますが、順序は重要ではないことを明確にしたいと思いました（したがって、巡回セールスマン問題とはまったく同じではありませんが、それでも少し似ています）。私が質問に焦点を合わせていた観察（これをスピードアップする方法についての洞察は歓迎されますが）は、結果が互いに構築されており、おそらく以前の結果に基づいて構築するために使用できる方法（動的計画法？）があるということでした多くの計算を繰り返すのとは対照的に。これらの結果を見ると、結果が相互に構築されていることがわかります（これを行うと、アイテムの数が3に変更され、forループの最大数が3に変更されます）。

Grapes = 0
Strawberries = 0
Raspberries = 0
****
Grapes = 1
Strawberries = 0
Raspberries = 0
****
Grapes = 2
Strawberries = 0
Raspberries = 0
****
Grapes = 3
Strawberries = 0
Raspberries = 0
****
Grapes = 0
Strawberries = 1
Raspberries = 0
****
Grapes = 1
Strawberries = 1
Raspberries = 0
****
Grapes = 2
Strawberries = 1
Raspberries = 0
****
Grapes = 3
Strawberries = 1
Raspberries = 0
****
Grapes = 0
Strawberries = 2
Raspberries = 0
****
Grapes = 1
Strawberries = 2
Raspberries = 0
****
Grapes = 2
Strawberries = 2
Raspberries = 0
****
Grapes = 3
Strawberries = 2
Raspberries = 0
****
Grapes = 0
Strawberries = 3
Raspberries = 0
****
Grapes = 1
Strawberries = 3
Raspberries = 0
****
Grapes = 2
Strawberries = 3
Raspberries = 0
****
Grapes = 3
Strawberries = 3
Raspberries = 0
****
Grapes = 0
Strawberries = 0
Raspberries = 1
****
Grapes = 1
Strawberries = 0
Raspberries = 1
****
Grapes = 2
Strawberries = 0
Raspberries = 1
****
Grapes = 3
Strawberries = 0
Raspberries = 1
****
Grapes = 0
Strawberries = 1
Raspberries = 1
****
Grapes = 1
Strawberries = 1
Raspberries = 1
****
Grapes = 2
Strawberries = 1
Raspberries = 1
****
Grapes = 3
Strawberries = 1
Raspberries = 1
****
Grapes = 0
Strawberries = 2
Raspberries = 1
****
Grapes = 1
Strawberries = 2
Raspberries = 1
****
Grapes = 2
Strawberries = 2
Raspberries = 1
****
Grapes = 3
Strawberries = 2
Raspberries = 1
****
Grapes = 0
Strawberries = 3
Raspberries = 1
****
Grapes = 1
Strawberries = 3
Raspberries = 1
****
Grapes = 2
Strawberries = 3
Raspberries = 1
****
Grapes = 3
Strawberries = 3
Raspberries = 1
****
Grapes = 0
Strawberries = 0
Raspberries = 2
****
Grapes = 1
Strawberries = 0
Raspberries = 2
****
Grapes = 2
Strawberries = 0
Raspberries = 2
****
Grapes = 3
Strawberries = 0
Raspberries = 2
****
Grapes = 0
Strawberries = 1
Raspberries = 2
****
Grapes = 1
Strawberries = 1
Raspberries = 2
****
Grapes = 2
Strawberries = 1
Raspberries = 2
****
Grapes = 3
Strawberries = 1
Raspberries = 2
****
Grapes = 0
Strawberries = 2
Raspberries = 2
****
Grapes = 1
Strawberries = 2
Raspberries = 2
****
Grapes = 2
Strawberries = 2
Raspberries = 2
****
Grapes = 3
Strawberries = 2
Raspberries = 2
****
Grapes = 0
Strawberries = 3
Raspberries = 2
****
Grapes = 1
Strawberries = 3
Raspberries = 2
****
Grapes = 2
Strawberries = 3
Raspberries = 2
****
Grapes = 3
Strawberries = 3
Raspberries = 2
****
Grapes = 0
Strawberries = 0
Raspberries = 3
****
Grapes = 1
Strawberries = 0
Raspberries = 3
****
Grapes = 2
Strawberries = 0
Raspberries = 3
****
Grapes = 3
Strawberries = 0
Raspberries = 3
****
Grapes = 0
Strawberries = 1
Raspberries = 3
****
Grapes = 1
Strawberries = 1
Raspberries = 3
****
Grapes = 2
Strawberries = 1
Raspberries = 3
****
Grapes = 3
Strawberries = 1
Raspberries = 3
****
Grapes = 0
Strawberries = 2
Raspberries = 3
****
Grapes = 1
Strawberries = 2
Raspberries = 3
****
Grapes = 2
Strawberries = 2
Raspberries = 3
****
Grapes = 3
Strawberries = 2
Raspberries = 3
****
Grapes = 0
Strawberries = 3
Raspberries = 3
****
Grapes = 1
Strawberries = 3
Raspberries = 3
****
Grapes = 2
Strawberries = 3
Raspberries = 3
****
Grapes = 3
Strawberries = 3
Raspberries = 3
****

私はまだアルゴリズムを学んでいるので、知識の蓄積は少し限られています。基本的に、入力を追加するにつれて指数関数的に成長し続ける再帰がありますが、それを行わないようにするために使用できるものがあるかどうか疑問に思っています。

これは、基本的にアイテムのリストを取得し、0〜n個の数量を使用して各アイテムのすべての組み合わせを計算する再帰のサンプル（Javaコード）です（簡単にするために、私のコードには2つのアイテムがあり、各アイテムの数量は0〜5です。 .variablesはループ内で変更できます）。これをさらに面白くするために、ランダム処理を実行し、その値をリストと照合して続行するQという変数があります。私はコードにコメントしたので、うまくいけば簡単に読めるようになりました。

import java.util.Arrays;
import java.util.List;
//learning playground safe to delete

public class main {

    public static void main(String[] args) {
        System.out.println("Starting..");
        Integer number_of_items = 2; //how many items should we test with, over 7 or 8 takes a long time MAX is 11(based on the number of names we have below)
        long startTime = System.currentTimeMillis(); //start timer
        Integer[] integers_temp = new Integer[number_of_items]; // create a list with exactly the number of items specified above
        Arrays.fill(integers_temp, 0); // populate list with zeros 
        List<Integer> list_to_start = Arrays.asList(integers_temp); //set it as a list
        String[] name_of_list_to_start = new String[] {"Grapes", "Strawberries", "Raspberries", "Blackberries", "Pineapples", "Oranges", "Prunes", "Pears", "cherries", "Peaches", "Apples"};       
        List<Integer> numbers_to_choose_from = Arrays.asList(new Integer[] {0, 1,2,3,4,5,6,7,8,9,10}); //list of numbers program can choose from(could be anything,just learning)
        counter(list_to_start.size(), list_to_start, name_of_list_to_start, numbers_to_choose_from);
        long endTime = System.currentTimeMillis(); 
        System.out.println("Total execution time: " + (endTime-startTime));
    }

    private static void counter(int length, List<Integer> list_to_start, String[] name_of_list_to_start, List<Integer> numbers_to_choose_from) {
        // If we've gone through everything then return the results
        if (length == 0) {
            for (int i = 0; i<list_to_start.size(); i++) {
                System.out.println(name_of_list_to_start[i] + " = " + list_to_start.get(i));
            }
            System.out.println("****");
            return;
        }   
        //This part basically increments list_to_start and then the above part displays it.
        for (int i = 0; i<=5; i++) {
            int q = i +2;  //do anything here..random just for example, right now just takes the number in the loop and adds by 10
            //System.out.println(q);  // this area is looped as many times as i^items, yet seems like after the first run work is duplicated.
            if (length != 0 && numbers_to_choose_from.contains(q)) {
                list_to_start.set((length-1), q);
                counter((length-1), list_to_start, name_of_list_to_start, numbers_to_choose_from);
                list_to_start.set((length-1), 0);
            }
        }
    }
}

数量を0〜10に、アイテムを10に変更すると、（10 ^ 10、つまり10000000000ループ）になります。コードをプロファイリングすると、ほとんどの時間がイテレーターに費やされていることがわかります。これは理にかなっているので、反復に費やす時間をなんとかして減らす必要があります（すべての再帰ではなく、アイテムごとに1回反復する方法があるといいのですが）。 。

私の観察では、最初のforループはリストに対して値を計算してチェックするために必要と思われますが、それが実行されると、ループは同じプロセスを繰り返します。私はすべてのアルゴリズムに精通していないので（ただし、現在アルゴリズムの概要を読んでいます）、これを指数関数的にしないで、より多くの変数を処理できるようにする方法があるかどうか疑問に思っています（これは私のプログラムの一部であり、はるかに大きいです） 、しかし理想的には、できるだけ多くの100アイテムを処理する必要がありますが、少なくとも0〜100個の100アイテムを処理し、1時間以内に処理する必要があります。そうしないと、他のジョブが失敗します。100^ 100でこれを達成する方法はないので、私はアイデアのために苦労しています）。

誰かがヒントを持っているか、同様の問題を解決するアルゴリズムを見たことがあれば、私は彼らが使用するロジックを研究し、それが適用されるかどうかを確認できるので、それは素晴らしいことです。誰かが直接的な解決策を持っているなら、それも素晴らしいです！

この質問が長すぎず、理にかなっていることを願っています（できるだけ詳しく説明しようとしました）

4

2 に答える 2

0

可能なすべての順列を生成したい場合、これはEXPTIMEのような-completeクラスに属します。これはtowers of Hanoi、NP完全問題よりも困難です（すべてがに属しているためPSPACE）。100^100より速くなることは期待できません。ただし、元の問題にはいくつかのヒューリスティックがある可能性があるため、それを言う方がよいでしょう。また、元々の問題がこれである場合は、上司と言うことができます。世界中の誰もこれを行うことはできません。また、並列化することもできますが、非常に強力なメインフレームを使用する場合を除いて、結果を得る機会はありません。

于 2012-04-06T18:51:06.433 に答える
0

現在、コードはすべての組み合わせを繰り返し処理しています。n = 100の場合、妥当な時間で実行できる方法はありません。内部ループを最適化しても、指数関数的になるのを止めることはできません。

それを実現可能にするためには、別のアプローチが必要になります。これを行う方法は、解決したい問題の詳細によって異なります。一部の最適化問題は、動的計画法、線形計画法、最大フロー、または二分探索などで解決できます。他の問題は、近似解を見つけることによって解決されます。

于 2012-04-06T19:01:04.497 に答える