algorithm - ロッド切断アルゴリズムは半貪欲なアルゴリズムですか

Question

私の例では、7 インチの長さのロッドは、6 + 1 または 2 + 2 + 3 の方法で分割できます。ここで、私のアルゴリズムが最初のパーティションを選択したと仮定します。

6 + 1

それ以外の

2 + 2 + 3

私はそれが半貪欲なアプローチであると言うべきですか、私が知っているように、ロッド切断問題は動的プログラミング問題です

Answer 1

半貪欲なアルゴリズムのよう な用語はありません。
より多くの価格を検索するため、最初の選択肢を選択します。終了した場合、別のオプションには進みません。それはすべて<=表現のためです。これはロッドカットの組み合わせの最適性を比較するものであり、半貪欲なアルゴリズムだからではありません。
私はそれが今あなたに明らかであると信じています

Answer 2

貪欲なアルゴリズム

半貪欲なアプローチ

貪欲なアルゴリズムは、問題全体をサブ問題に分割し、サブ問題のコンテキストでそれらの問題の最適なソリューションを選択しようとすることによって、問題全体を解決しようとするアルゴリズムです。これは多くの場合、解につながりますが、大域的最適解にはなりません。セミグリーディは意味がありません。そうであるか、そうでないかのどちらかです。

ロッド切断問題

ロッド切断問題は、ロッドを切断するのにかかる費用を示す値の表に基づいて、ロッドを切断する最も効率的な方法です。

そのままのアルゴリズム

ええと..貪欲になる価値がわかりません。できるだけ少数の数に分割しようとしている場合、明らかに、分割する数よりも小さい最大の数に貪欲になります。

貪欲なアルゴリズムには、取り組むための何らかの目標が必要です。単純に「ロッド」を分割するだけでは、暗黙の価値はありません。

コスト マトリックスがある場合のアルゴリズム

コスト マトリックスがあり、アルゴリズムが最も安い値を使用してカットしようとした場合、コストに貪欲であるため、それは貪欲なアルゴリズムになります。