私は、一見矛盾するように見える 2 つのアイデアを調整しようとしています。
- 無限ナップザック最適化問題は NP 困難であることが知られています。
- 私の同僚と私は、A* を使用して、多項式時間でその小さな変化を解くことができると思います
クレイジーですね。そう思います！
問題のバリエーションは、積載量を飛行機の能力まで減らすために貨物の一部を降ろさなければならない貨物飛行機の観点から説明されます。したがって、それぞれに重量と値、および荷を下さなければならない目標重量を持つアイテムのセットがあります。荷を下す商品を最適化して、少なくとも W の重量が取り除かれ、商品の合計値が最小になるようにします。N 個の異なるタイプのそれぞれに利用可能な任意の数のアイテムがある無限の問題を考えてみましょう。
提案されたソリューションは、何もアンロードされていないことを表すノード (頂点) から始まるグラフを使用します。各アンロード操作はエッジを表すため、荷を下す可能性のある商品のすべての組み合わせで、グラフは開始点から指数関数的に成長します。宛先ノードは、合計重み >= ターゲットのすべての組み合わせがターゲット ノードと見なされるという点で、仮想集約です。これまでに降ろされた総重量が各ノードに保存され、目標に到達したかどうかを判断するために使用されます。各エッジのコストは、アンロードされるアイテムの値です。したがって、Dijkstra や A* などの最短経路アルゴリズムは、最適な商品セットを見つけます。
Dijkstra は可能なすべての組み合わせを探索しているため、明らかに指数関数的な時間がかかります。しかし、許容できるヒューリスティックを使用すると、A* は多項式時間で実行する必要があると思います。そして、次のヒューリスティックが機能するはずだと思います。すべての商品について、重量に対する価値の比率である「特定の価値」を計算します。特定の値が最も高い商品を選択します。特定のノードのヒューリスティックとして、まだアンロードする必要がある重みに特定の最大値を掛けた値を計算します。これは、整数個の最適な商品によって目標重量を達成できる場合は正確に正確な見積もりを提供するか、実際の商品の数を四捨五入する必要があるため、残りの距離 (重量) を過小評価する他のすべての場合のいずれかです。上。したがって、ヒューリスティックは許容されます。
ランタイムの複雑さを厳密な方法で証明したことはありません。しかし、A* が機能する方法では、目標に向かって貪欲に項目を追加し、最適なオプションをすばやく探索します。これは、N の多項式時間で実行する必要があるように直感的に感じられます。また、適切に許容できるヒューリスティックを使用すると、ソリューションが最適であることが保証されます。
では、このソリューションの何が問題なのですか? よく知られているアルゴリズムを適用することによって、よく研究された問題に対する新しい解決策を発見したとは絶対に信じていません。しかし、これはうまくいくようです。