このアルゴリズムの名前はありますか？

Question

非記述的な質問に対する謝罪。あなたが良いものを考えることができれば、私はすべて耳です。

私はアルゴリズムを実装するためにいくつかのPerlを書いていますが、コードには怪しいものがあります。私はCSのバックグラウンドを持っていないので、私はバックポケットの標準的なアルゴリズムについて多くの知識を持っていませんが、これはそうであるかもしれません。

私はメタファーの方法によって、私がやっていることを記述してみましょう：

• あなたがオレンジのコンベアベルトを持っています。オレンジはあなたを一つずつ通す。あなたはまた、フラットパックボックスの無制限の供給を持っています。
• オレンジ色ごとにチェックしてください。腐っている場合は処分してください
• 良い場合は箱に入れてください。あなたが箱を持っていない場合は、新しい箱をつかんでそれを作ってください。
• 箱に10個のオレンジが入っている場合は、それを閉じてパレットに置きます。 新しいものを作成しないでください。あなたはもうオレンジを持っていないまであなたはそれでいくつかのオレンジと構築ボックスを持っている場合は
• 繰り返し
• 、それをクローズアップし、パレットだから、

の上に置く、我々は内の項目を処理するためのアルゴリズムを持っていますリストには、いくつかの基準を満たしていれば、他の基準を満たしていれば「閉鎖」しなければならない構造に追加する必要があります。また、リストが処理された後、 'オープン'構造があれば、それも '閉鎖'する必要があります。

Naiveでは、アルゴリズムは、リスト要素が構造体に属しているかどうかを調べるための条件付きで、構造体が '閉じられている'必要があるかどうかを確認するための条件付きリストからなるループで構成されていると仮定します。 ループの外側には、未処理の構造を閉じる条件が1つ以上あります。

だから、ここに私の質問は以下のとおりです。

1. これはよく知られているアルゴリズムの説明ですか？もしそうなら、それは名前を持っていますか？
2. 「ボックスを閉じる」アクティビティを、ループの内側とループの外側の1つではなく、1つの場所にまとめる効果的な方法はありますか？

私はPerlishのアプローチが興味深いのでこれを「Perl」とタグ付けしましたが、私はこれに対するすっきりした解決策を持っている他の言語について聞くことに興味があります。

Answer 1

は、機能的アプローチとの素敵なフィット感ですが、私は、これはあなたを助けることを願っています

hereを見つけることができますオレンジ、テスト、グルーピング、およびそれらの操作。

val oranges:Stream[Oranges] = ... // generate a stream of Oranges 

oranges.filter(_.isNotRotten).grouped(10).foreach{ o => {(new Box).fillBox(o)}} 

（groupedが終わり部分のボックスに正しいことをする）

Perlの同等物は、おそらくあります：スカラ座では、それはようなものになるだろう。

Answer 2

あなたが説明している問題では少し複雑すぎるようですが、理論的にはペトリネットの近くに聞こえます。あなたは、ストリームを反復処理している - Petri Nets on wikipedia

チェックperlの実装は、

ジェローム・ワグナー

Answer 3

私はこのアルゴリズムの名前はないと思います。単純な実装では、処理ループ中にフルボックスを検出するテストと、部分的にフルボックスを検出するループの後にテストを行うテストの2つのテストが必要です。 「ボックスを閉じる」ロジックは、複製を避けるためにサブルーチンにすることができます。

use List::MoreUtils qw(part natatime); 

my ($good, $bad) = part { $_->is_rotten() } @oranges; 

$_->dispose() foreach @$bad; 

my $it = natatime 10, @$good; 
while (my @batch = $it->()) { 
    my $box = Box->new(); 
    $box->add(@batch); 
    $box->close(); 
    $box->stack(); 
} 

Answer 4

に一度ループ内で、一度外とは対照的に、単一の場所、 に「箱を手仕舞いの活動を合体するための効果的な方法があります：機能的なアプローチは、その回避する方法を提供することができループの？

はい。単に「...構造体を閉じる必要がありますか」機能に「...またはそれ以上のオレンジはありません」を追加します。これを行うための最も簡単な方法は、DOです/構築物は、（技術的には1のように見えるけれども、それは、Perlでのループではありません話す）ながら：close_container()がある場合

my $current_container; 
my $more_objects; 
do { 
    my $object = get_next_object(); # Easiest implementation returns undef if no more 
    $more_objects = more_objects($object) # Easiest to implement as "defined $object" 
    if (!$more_objects || can_not_pack_more($current_container) { 
     close_container($current_container); 
     $current_container = open_container() if $more_objects; 
    } 
    pack($object, $current_container) if $more_objects; 
} while ($more_objects); 

私見を、これは本当にあなたに何かを獲得していませんメソッドの中にカプセル化されています。ループの内側と外側の両方で呼び出すための技術的またはコード品質の大きなコストはありません。

my $current_container; 
while (my $more_objects = more_objects(my $object = get_next_object())) { 
    if (can_not_pack_more($current_container)) { # false on undef 
     close_container($current_container); 
    } 
    $current_container = open_container_if_closed($current_container); # if defined 
    pack($object, $current_container); 
} 
close_container($current_container); 

Answer 5

アルゴリズムを見てみると、主流CSのものが非常に複雑な状況に対処する傾向がある：実は、私は強く、私は上記のように複雑な回避策は簡単より賢明悪化し、コードの品質であるという意見のです例えば、非常にの複雑なアプローチ（例えば、NP-Completeを参照）を使用します。さらに、アルゴリズムは最適化に集中する傾向があります。このシステムはどのようにしてより効率的になりますか？この生産計画では、どのように少ないステップを使用すればよいですか？私のバーに入ることができる最も多くの情報は何ですか？

私の意見では、複雑なアプローチの例は、再帰がかなり天才的なので、すばやい並べ替えです。私はそれが標準であることを知っていますが、私は本当にそれが好きです。アルゴリズムが好きなら、Simplex Algorithmをチェックしてください。それは非常に影響力があります。

複雑な状況の例は、入り込んだオレンジを5つのオレンジ色のパイルにソートし、次に5つの異なる場所に移動して剥がした後、すべてがオレンジの合計10オレンジ各オレンジを個別にスライスし、のグループで正確に 2ポンドのグループに囲んだ。

例に戻る。あなたの例はflow networkの簡略版です。非常に多くのサイドパスとオプションを持つ代わりに、一度に1オレンジの容量を持つパスは1つだけです。フローネットワークアルゴリズムのうち、Ford-Fulkerson algorithmがおそらく最も影響力があります。

したがって、これらのアルゴリズムのいずれかを、ポーズされた例に当てはめることはできますが、単純化プロセスを使用することになります。基本的には、ここでは最適化が必要なほど複雑ではありません。そして、非効率な時間の複雑さで走る危険がないので、「完璧なアプローチ」を実行する必要はありません。

詳細なアプローチはここでうまくいくはずです。上記の受け入れられた答えは、定義された問題に対する実際の機能的な解決策を示唆しています。アルゴリズムに関する2セントを追加したかっただけです。