次のケースで欲張りアルゴリズムが失敗する理由

Question

ダイナミックプログラミングのみで解決できると主張された1つの問題を解決しようとしました。次は問題です。 人は全エネルギーをHとし、距離Dをカバーする必要があります。最小距離で最大エネルギーHを使ってこの距離をカバーしたいと考えています。彼は5つのモードで走ることができます。合計距離は、5つのモードの1つに従って各kmを実行することによってカバーされます。 '500万10秒'、6 'のM 11sec'、 '7メートル7sec'、8 'のM 11sec'、9 'のM 11sec'

- ： これらの5つのモードは

時間ソートされた2つのアレイを使用して記載されています

エネルギーが必要：-11,9,8,7,6

をだから私の貪欲なソリューション戦略は

1. 計算最低を取るモードを使用してH/D

2. ラン次キロメートルのX =階です時間とエネルギーが必要です< = X

   &セットH =残距離までモード

   集合D = D-1

3. Gotoステップ1で必要とされるH-エネルギーが0

4. 回答全ての一部であろうとなり各kmの時間。

この解決策はうまくいくと思いますが、実際には失敗します。私はDPを使ってそれを解決する方法を知っていますが、どこで失敗するのか知りたいのです。私は多くの例を試しましたが、感情を得ていません。私は2つの配列の要素の上に正確には想起しませんが、それらは必ずソートされた順序であります。

Answer 1

理由は簡単です。あなたはあなたのアルゴリズムを証明していないので、正しいと主張することはできません。そのような単純な。研究文献のヒューリスティックアルゴリズムがどれほど正確であるかを知っていますが、正しさの証明はありません。なぜ彼らはヒューリスティックなのですか？

解決策はヒューリスティックです。反例の場合。 H=100, D=3とする。時間は[1,2,3,4,5]となり、対応するエネルギーは[35,34,32,32,32]となります。

あなたの最初のxはfloor(100/3)=33です。エネルギーが<=33の最低時間は3です。それを選んでください。 H=67, D=2のようにHとDを更新してください。我々はfloor(67/2)=33を持っています。再度、時間3を選択します。 HとDを更新してH=34, D=1とします。最後にx=floor(34/1)=34時間を選択してください2。したがって、距離をカバーする時間のリストは、合計エネルギーは32+32+34=98、合計時間は8です。

しかし、私はあなたの欲張りな解決策よりも優れた解決策を考え出すことができます。すなわち、時間が8単位であるが、35+32+32=99総エネルギーを有する時間[1,3,4]。あなたの貪欲な解決策を打つ。

ストーリーのモラル？あなたのアルゴリズムを証明できない場合は、間違った、あるいは単純にヒューリスティックを仮定します。