algorithm - 重複しない購入の最適な順序

Question

これはスケジュールの問題だと思いますが、それについてはよくわかりません。私が望んでいるのは、それらの価値と将来どのような機会が生まれるかを完全に理解しているときに、重複しない購入決定の最適な順序を見つけることです。

自分の店で買いたい商品を販売している問屋を想像してみてください。いつでも、複数の特別オファーを実行している可能性があります。私は定価で販売するので、彼らの割引は私の利益です。

利益を最大化したいのですが、一度に買えるのは1つだけで、クレジットなどはなく、さらに悪いことに納期が遅れるのが難点です。良いニュースは、商品が配達されたらすぐに販売し、それからまたお金を使うことができるということです。したがって、すべての選択肢の1つの方法は、月曜日に100kgのリンゴを購入し、火曜日に配達されるということです。それから私は日曜日に配達された20の修道女の衣装を購入します。水曜日にフェラーリが大幅に割引されることを知っているので、私は数日スキップします。だから私はそれらの1つを購入します、それは次の火曜日に配達されます。等々。

複利かどうかを検討できます。アルゴリズムは、今日の特別オファーの1つを選択するか、明日より良いものが来るので1日待つか、各段階での決定に帰着します。

それを少し抽象化しましょう。購入と配達はエポックから数日となります。利益は、売り価格を買い価格で割ったものとして書かれます。つまり、1.00は損益分岐点を意味し、1.10は10％の利益を意味し、2.0はお金を2倍にしたことを意味します。

  buy    delivery   profit
    1        2       1.10    Apples
    1        3       1.15    Viagra
    2        3       1.15    Notebooks
    3        7       1.30    Nun costumes
    4        7       1.28    Priest costumes
    6        7       1.09    Oranges
    6        8       1.11    Pears
    7        9       1.16    Yellow shoes
    8       10       1.15    Red shoes
   10       15       1.50    Red Ferrari
   11       15       1.40    Yellow Ferrari
   13       16       1.25    Organic grapes
   14       19       1.30    Organic wine

注：機会は購入日にのみ存在し（たとえば、有機ブドウは誰も購入しないとワインになります！）、配達と同じ日に販売されますが、次のアイテムは翌日まで購入できません。そのため、t = 7で修道女の衣装を販売して、t=7ですぐに黄色い靴を購入することはできません。

既知の最良のアルゴリズムが存在し、そのためのRモジュールがすでに存在することを望んでいましたが、他の言語の他の言語と同様に、アルゴリズムや学術文献も優れています。^{速度は重要ですが、主にデータが大きくなるときなので、O（n 2}）かどうか知りたいです。

ちなみに、配信遅延が最大になる可能性がある場合、最良のアルゴリズムは変更されますか？例：delivery - buy <= 7

上記のデータをCSVとして次に示します。

buy,delivery,profit,item
1,2,1.10,Apples
1,3,1.15,Viagra
2,3,1.15,Notebooks
3,7,1.30,Nun costumes
4,7,1.28,Priest costumes
6,7,1.09,Oranges
6,8,1.11,Pears
7,9,1.16,Yellow shoes
8,10,1.15,Red shoes
10,15,1.50,Red Ferrari
11,15,1.40,Yellow Ferrari
13,16,1.25,Organic grapes
14,19,1.30,Organic wine

またはJSONとして：

{"headers":["buy","delivery","profit","item"],"data":[[1,2,1.1,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.3,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.5,"Red Ferrari"],[11,15,1.4,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.3,"Organic wine"]]}

またはRデータフレームとして：

structure(list(buy = c(1L, 1L, 2L, 3L, 4L, 6L, 6L, 7L, 8L, 10L, 
11L, 13L, 14L), delivery = c(2L, 3L, 3L, 7L, 7L, 7L, 8L, 9L, 
10L, 15L, 15L, 16L, 19L), profit = c(1.1, 1.15, 1.15, 1.3, 1.28, 
1.09, 1.11, 1.16, 1.15, 1.5, 1.4, 1.25, 1.3), item = c("Apples", 
"Viagra", "Notebooks", "Nun costumes", "Priest costumes", "Oranges", 
"Pears", "Yellow shoes", "Red shoes", "Red Ferrari", "Yellow Ferrari", 
"Organic grapes", "Organic wine")), .Names = c("buy", "delivery", 
"profit", "item"), row.names = c(NA, -13L), class = "data.frame")

リンク

グラフ用のRパッケージ（最短経路など）はありますか？ （igraphはshortest.paths関数を提供し、Cライブラリに加えて、RパッケージとPythonインターフェイスを備えています）

Answer 1

この問題を考える最も簡単な方法は、最短経路問題に類似しています（ただし、最大フロー問題として扱う方が技術的にはおそらく優れています）。日番号1...19は、ノード名として使用できます。各ノードjには、重み1のノードj + 1へのリンクがあり、リスト内の各製品（b、d、g、p ）は、重みgの日bから日d+1へのリンクを追加します。パスファインディング時にノードを進むにつれて、各ノードでこれまでに見られた最良の乗算値を追跡します。

以下に示すPythonコードは、時間O（V + E）で実行されます。ここで、Vは頂点（または日数）の数、Eはエッジの数です。この実装では、E =V+販売されている製品の数。 注を追加：enumerate（graf）のi、tのループ：各頂点を1回処理します。そのループでは、エッジのeの場合：現在の頂点からのエッジをそれぞれ1回処理します。したがって、エッジが複数回処理されることはないため、パフォーマンスはO（V + E）になります。

編集された注2： krjampaniは、O（V + E）はO（n log n）よりも遅いと主張しました。ここでnは製品の数です。ただし、考慮される日数について仮定しない限り、2つの注文は比較できません。納期が制限され、製品の日付が重複している場合、日数はO（n）であり、O（V + E）= O（n）であり、O（n log n）よりも高速であることに注意してください。

ただし、与えられた一連の仮定の下では、私のメソッドとkrjampaniの実行時の順序は同じである可能性があります。日数が多い場合は、x[0]とx[の並べ替えられた和集合で日のみグラフノードを作成するようにメソッドを変更します。 1]値、およびi-1とi+1の代わりにday[i-1]とday[i+1]へのリンクを使用します。日数が少ない場合は、krjampaniのメソッドを変更して、O（n）カウントソートを使用します。

プログラムの出力は次のようになります。

 16 :   2.36992 [11, 15, 1.4, 'Yellow Ferrari']
 11 :   1.6928 [8, 10, 1.15, 'Red shoes']
 8 :    1.472 [4, 7, 1.28, 'Priest costumes']
 4 :    1.15 [1, 3, 1.15, 'Viagra']

これは、15日目にイエローフェラーリを販売した後、複合利益2.36992で16日目に到着したことを示しています。赤い靴を売った後、11日目に利益1.6928で到着しました。などなど。製品リストの先頭にあるダミーエントリと、数字の前後の引用符の削除が、JSONデータとの主な違いであることに注意してください。list要素のエントリは、[best-value-so-far、best-from-node＃、best-from-product-key、edge-list]の形式でgraf[j]始まります。[1, j-1, 0, [[j+1,1,0]]]各エッジリストは、[next-node＃、edge-weight、product-key]の形式のリストのリストです。製品0をダミー製品にすると、初期化が簡単になります。

products = [[0,0,0,""],[1,2,1.10,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.30,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.50,"Red Ferrari"],[11,15,1.40,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.30,"Organic wine"]]
hiDay = max([x[1] for x in products])
graf = [[1, i-1, 0, [[i+1,1,0]]] for i in range(2+hiDay)]

for i, x in enumerate(products):
    b, d, g, p = x[:]
    graf[b][3] += [[d+1, g, i]] # Add an edge for each product

for i, t in enumerate(graf):
    if i > hiDay: break
    valu = t[0]                 # Best value of path to current node
    edges = t[3]                # List of edges out of current node
    for e in edges:
        link, gain, prod = e[:]
        v = valu * gain;
        if v > graf[link][0]:
            graf[link][0:3] = [v, i, prod]

day = hiDay
while day > 0:
    if graf[day][2] > 0:
        print day, ":\t", graf[day][0], products[graf[day][2]]
    day = graf[day][1]

Answer 2

この問題は、重み付き間隔のセットの中から重みに依存しない最大間隔を見つけるという問題に自然に対応します。入力セットの各アイテムは、開始点と終了点が購入日と配信日であり、アイテムの利益が間隔の重みを表す間隔に対応します。最大の重みに依存しない区間の問題は、総重みが最大である互いに素な区間のセットを見つけることです。

この問題は次のように解決できO(n log n)ます。間隔を終点で並べ替えます（図を参照）。次に、並べ替えられたリストの各間隔を移動iし、並べ替えられたリストの間隔で構成されるサブ問題の最適解を計算し1...iます。区間の問題の最適な解決策は1...i、次の最大値です。

1. The optimal solution of the problem for intervals `1...(i-1)` in the 
   sorted list or

2. Weight of interval `i` + the optimal solution of the problem for intervals 
   `1...j`, where j is the last interval in the sorted list whose end-point
   is less than the start-point of `i`.

このアルゴリズムが実行されO(n log n)、ソートされたリストのすべてのプレフィックスの最適解の値が計算されることに注意してください。このアルゴリズムを実行した後、ソートされたリストを逆の順序で移動し、各プレフィックスに対して計算された値に基づいて、最適なソリューションに存在する間隔を見つけることができます。

編集：

これが正しく機能するためには、間隔の重みが対応するアイテムの実際の利益である必要があります（つまり、sell_price-buy_priceである必要があります）。

アップデート2：実行時間

V日数とします（jwpat7の表記に従います）。Vがよりもはるかに小さい場合はO(n log n)、カウントソートを使用してO(n + V)時間間隔をソートし、サイズの配列を使用Vしてサブ問題の解決策を記録できます。このアプローチでは、時間計算量がになりO(V + n)ます。したがって、アルゴリズムの実行時間はですmin(O(V+n), O(n log n))。

Answer 3

これは動的計画法の問題です。全体的に最適な選択を行うには、各ステップで最適な選択を行うだけで済みます。前の状態とその状態からさまざまなステップを実行することの利益に基づいて、各ステップでの最適な選択を説明する表を作成できます。明らかに最適ではない可能性を排除することで、大きな可能性のセットを小さなセットにまとめることができます。

あなたの問題では、選択に影響を与える唯一の状態は配達日です。たとえば、初日には3つの選択肢があります。リンゴを購入し、利益を1.10に設定し、配達日を2に設定します。バイアグラを購入し、利益を1.15に設定し、配達日を3に設定します。または、何も購入せず、利益をゼロに設定し、配達日を2に設定します。次のようにこれらの選択肢を表すことができます。

(choices=[apples], delivery=2, profit=1.10) or
(choices=[viagra], delivery=3, profit=1.15) or
(choices=[wait],   delivery=2, profit=0.00)

バイアグラを購入するか、初日に何も購入しないかは、将来の決定を下す限り、何の違いもありません。いずれにせよ、購入できる翌日は2日目なので、利益が少ないので、代わりに待つ必要がなくなります。ただし、リンゴを購入した場合、バイアグラを購入したり待ったりする場合とは異なる方法で将来の決定に影響を与えるため、検討する必要のある別の選択肢です。それは、初日の終わりにこれらの選択肢をあなたに残すだけです。

(choices=[apples], delivery=2, profit=1.10) or 
(choices=[viagra], delivery=3, profit=1.15)

2日目は、1日目の代替案に基づいて代替案を検討する必要があります。これにより、次の3つの可能性が生まれます。

(choices=[apples,notebooks], delivery=3, profit=2.25) or
(choices=[apples,wait],      delivery=3, profit=1.10) or
(choices=[viagra,wait],      delivery=3, profit=1.15)

これらの3つの選択肢はすべて、納期を3に設定しているため、将来の決定を考慮する限り、同じ状態になります。したがって、最大の利益をもたらすものを選択するだけです。

(choices=[apples,notebooks], delivery=3, profit=2.25)

3日目に進むと、2つの選択肢があります

(choices=[apples,notebooks,wait],         delivery=4, profit=2.25)
(choices=[apples,notebooks,nun costumes], delivery=7, profit=3.55)

これらの選択肢は両方とも、将来の決定にさまざまな形で影響を与えるため、維持する必要があります。

納期と利益に基づいて将来の決定を行っているだけであることに注意してください。最後に最良の選択肢を報告できるように、選択肢を追跡します。

今、あなたはパターンを見ることができるかもしれません。選択肢のセットがあり、同じ納期を持つ複数の選択肢がある場合は常に、利益が最大の選択肢を選択し、他の選択肢を排除します。選択肢を折りたたむこのプロセスは、問題が指数関数的に増大するのを防ぎ、効率的に解決できるようにします。

Answer 4

これは線形計画問題として解くことができます。これは、航空会社や企業が直面するような、あなたよりもはるかに大きな問題空間を持つロジスティクスの問題を解決するための標準的なアプローチです。ここでは正式に問題を定義しませんが、大まかに言うと、目的関数は利益の最大化です。購入日と「1日1回の購入のみ」を線形制約として表すことができます。

標準の線形計画法アルゴリズムはシンプレックス法です。指数関数的な最悪の場合の動作がありますが、実際には、実際の問題に対して非常に効率的である傾向があります。自由に利用できる優れた実装がたくさんあります。私のお気に入りはGNU線形計画法キットです。RにはGLPKへのインターフェースがあります。Lp_solveは、もう1つのよく知られたプロジェクトであり、Rインターフェイスもあります。それぞれの場合の基本的なアプローチは、問題を正式に定義し、それをサードパーティのソルバーに渡してその処理を実行することです。

詳細については、アルゴリズム設計マニュアルを参照することをお勧めします。このマニュアルには、オンラインでさらに調査を行うための十分な背景が記載されています。p.412以降は、線形計画法とそのバリエーションの完全な要約です（たとえば、整数計画法がある場合は整数計画法）。

これまで線形計画法について聞いたことがない場合は、線形計画法の使用方法の例をいくつか見てみたいと思うかもしれません。私はPythonのこの単純なチュートリアルの問題のセットが本当に好きです。キャットフードの缶詰の利益を最大化することや、数独の問題を解決することも含まれます。