1

次の質問の解決策を見つけるのに苦労しています。

会社が次の5年間に機械を持っている必要があると仮定します。新しいマシン1台あたりのコストは$100,000です。i番目の運用年におけるマシンの運用の年間コストは次のように与えられます：C1 = $ 6000、C2 = $ 8000、C3 =$12,000。機械は下取りされるまで最大3年間保管される場合があります。つまり、機械は最初の2年間は保管または交換でき、3歳になると交換する必要があります。i年後の下取り価格は、t1 = $ 80,000、t2 = $ 60,000、t3 =$50,000です。会社が0年目に新しいマシンを購入する場合、会社は5年間（0年目から5年目）のコストをどのように最小限に抑えることができますか？
動的計画法に基づいて最適なソリューションを考案します。

この問題は、ツリーを使用して表すことができます。これが図です。 ツリー表現

さて、上のツリーで最短経路を見つけることが最適な解決策になると思います。しかし、私はそれをどのように行うのか分かりません。これが私の質問です、

他の提案も歓迎します。

みんな、私はこの質問のためにいくつかのガイダンスと助けが欲しいです。（これをあなたからの宿題を終わらせるための要求とは思わないでください。）私はこの質問の完全なJava実装をここで見つけました。しかし、問題を解決するために動的計画法を使用していません。前もって感謝します。

4

6 に答える 6

3

同社は、5年間でコストを最小限に抑えたいと考えています。0年目に、彼らは機械を購入する予定であり、毎年、機械を保管するか取引するかを決定する必要があります。最適なソリューションに到達するために、年末ごとに一連の選択を行う必要があります。私たちがそれぞれの選択をするとき、同じもののサブ問題がしばしば発生します。したがって、特定のサブ問題が複数の部分的な選択肢のセットから発生する可能性がある位置に到達します。動的計画法に基づいて最適な解を考案する場合、サブ問題の解を組み合わせることで問題を解決できます。

ステージを毎年対応させます。状態は、その年のマシンの年齢です。決定は、マシンを維持するか、新しいマシンと交換するかです。マシンが時間tでx年経過している場合、Ft（x）を時間tから時間5までに発生する最小コストとします。 基本ケース：

5年の終わりに機械を取引しなければならないのでF5（x）=-S [x]

  • 0年目に、新しいマシンF0（1）= N + M [1] + F1（0）を購入します。
  • 5歳から最大3歳までの範囲：0

  • 既存のマシンを最大3年間保持します：Ft（3）= N + M [0] + Ft + 1（0）; t≠0,1,2

    def Fxy（self、time、age）：

        if self.Matrix[time][age]==None: <- Overlaping subproblems avoided
        if(time>5 or age>2):
            return 0
        if time==5:
            self.Matrix[time][age]=T=self.S[age]
            self.Flag[time][age]='TRADE'                
        elif time==0: 
       self.Matrix[time][age]=K=self.N+self.M[0]+self.Fxy(time+1,time)
            self.Flag[time][age]='KEEP'             
        elif time==3 and age==2: 
       self.Matrix[time][age]=T=self.S[age]+self.N+self.M[0]+self.Fxy(time+1,0)

            self.Flag[time][age]='TRADE'                
        else:
            T=self.S[age]+self.N+self.M[0]+self.Fxy(time+1,0)                   
            if age+1<len(self.Matrix[0]):
                K=self.M[age+1]+self.Fxy(time+1,age+1)  
            else:
                K=self.M[age+1]
            self.Matrix[time][age]=min(T,K)             
            if(self.Matrix[time][age]==T and self.Matrix[time][age]==K):
                self.Flag[time][age]='TRADE OR KEEP'
            elif(self.Matrix[time][age]==T):
                self.Flag[time][age]='TRADE'
            else:
                self.Flag[time][age]='KEEP'
        return self.Matrix[time][age]
    else:           
        return self.Matrix[time][age]

最適なソリューションは、すべての可能なパスを含み、最小コストのパスを採用する決定木を描画することで実現できます。各ツリーレベルをトラバースし、現在の決定ポイントが発生するパスを作成する再帰アルゴリズムを使用します。例：F1（0）をトラバースすると、「TRADEORKEEP」決定がバインドされます。次に、2つの可能なパスをトラバースできます。F2（1）をトラバースする場合、「KEEP」の決定があるため、再帰的に、右の子であるF3（2）をトラバースします。'TRADE'が出会ったとき、左の子供は葉に達するまで続けます。

def recursePath(self,x,y):
    if(x==5):           
        self.dic[x].append(self.Flag[x][y])         
        return self.Flag[x][y]

    else:   
        if(self.Flag[x][y]=='TRADE OR KEEP'):
            self.recursePath(x+1,y)             
            self.recursePath(x+1,y+1)               

        if(self.Flag[x][y]=='KEEP'):
            self.recursePath(x+1,y+1)               

        if(self.Flag[x][y]=='TRADE'):
            self.recursePath(x+1,y)         

        self.dic[x].append(self.Flag[x][y])         
        return self.Flag[x][y]
于 2012-11-10T04:04:49.603 に答える
1

ダイクストラのようなものが必要な場合は、ダイクストラをやってみませんか？グラフの解釈でいくつか変更する必要がありますが、それは非常に実行可能のようです。

ダイクストラは、最小コスト基準に従ってノードを決済します。その基準を「会社が失ったお金」に設定します。また、ダイクストラでノードを決済し、ノードが正確に何になるかを決定する必要があります。ノードを時間とプロパティの状態と見なします。たとえば、x年前のマシンが稼働している4年目です。0年目には、失われるお金は0になり、マシンはなくなります。次に、可能なすべてのエッジ/選択/状態遷移を追加します。ここでは「マシンを購入する」です。最終的に、ダイクストラPQ [1年目、1歳の稼働中のマシン]に一定のコストで新しいノードができあがります。

そこから、いつでもマシンを販売する（[1年目、マシンなし]ノードを生成する）、新しいマシンを購入する[1年目、新しいマシン]）、または同じものを続行する（[2年目、2歳のマシン]）ことができます。 。5年目（またはそれ以上）に必要なものがすべて揃うまで、最短経路ツリーを開発し続けます。

次に、ノードのセット[i年、j歳のマシン]があります。i年目にあなたの会社に最適なものを見つけるには、その可能性をすべて調べて（[i年目、機械なし]になると思います）、答えを見つけてください。

ダイクストラは全ペア最短経路アルゴリズムであるため、すべての年へのすべての最良の経路を提供します

編集：最初にJavaの擬似コードを作成して、ノード情報を保持するノードオブジェクト/クラスを作成する必要があります。

Node{
int cost;
int year;
int ageOfMachine;
}

次に、ノードを追加して解決するだけです。PQがコストフィールドに基づいてノードをソートしていることを確認してください。ルートから開始：

PQ<Node> PQ=new PriorityQueue<Node>();
Node root= new Root(0,0,-1);//0 cost, year 0 and no machine) 
PQ.offer(root); 
int [] best= new int[years+1];
//set best[0..years] equal to a very large negative number
while(!PQ.isEmpty()){
   Node n=PQ.poll();
   int y=n.year;
   int a=n.ageOfMachine;
   int c=n.cost;
   if(already have a cost for year y and machine of age a)continue;
   else{
      add [year y, age a, cost c] to list of settled nodes;
      //examine all possible further actions
      //add nodes for keeping a machine and trading a machine
      PQ.offer(new Node(cost+profit selling current-cost of new machine,year+1,1));
      PQ.offer(new Node(cost,year+1,age+1);//only if your machine can last an extra year
      //check to see if you've found the best way of business in year i
      if(cost+profit selling current>best[i])best[i]=cost+profit selling current;
   }
}

それらの線に沿った何かがあなたに最高のコストでi年に到達するためのベストプラクティスを与えるでしょう[i]

于 2012-11-05T08:04:19.233 に答える
1

より単純な動的プログラムソリューションを見つけたと思います。

提案コスト（n）は、n年目に販売する場合の全体のコストです。また、マシンを1、2、3年間維持するコストは、cost1、cost2、cost3（この問題では26000、54000、76000）です。

次に、問題を次のようなサブ問題に分割できます。

**Cost(n)= MIN( Cost(n-1)+cost1, Cost(n-2)+cost2, Cost(n-3)+cost3 );**

したがって、O（n）である「ボトムアップ方式」で計算できます。

私はCを使用してそれを実装してテストしました：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct costAndSell_S{
    int lastSellYear;
    int cost;
};

int operatCost[3]={6000,8000,12000};
int sellGain[3]={80000,60000,50000};
int newMachinValue=100000;
int sellCost[3];
struct costAndSell_S costAndSell[20];

void initSellCost(){

    memset( costAndSell, 0, sizeof(costAndSell));
    sellCost[0]=operatCost[0]+newMachinValue-sellGain[0];
    sellCost[1]=operatCost[0]+operatCost[1]+newMachinValue-sellGain[1];
    sellCost[2]=operatCost[0]+operatCost[1]+operatCost[2]+newMachinValue-sellGain[2];

    costAndSell[0].cost=100000;
    return;
}

int sellAt( int year ){
    if ( year<0){
        return(costAndSell[0].cost );
    }
    return costAndSell[year].cost;
}

int minCost( int i1, int i2, int i3 ){
    if ( (i1<=i2) && (i1<=i3) ){
        return(0);
    }else if ( (i2<=i1) && (i2<=i3) ){
        return(1);
    }else if ( (i3<=i1) && (i3<=i2) ){
        return(2);
    }
}
void findBestPath( int lastYear ){
    int i;
    int rtn;
    int sellYear;
    for( i=1; i<=lastYear; i++ ){
        rtn=minCost( sellAt(i-1)+sellCost[0], sellAt(i-2)+sellCost[1], sellAt(i-3)+sellCost[2]);
        switch (rtn){
            case 0:
                costAndSell[i].cost=costAndSell[i-1].cost+sellCost[0];
                costAndSell[i].lastSellYear=i-1;
                break;
            case 1:
                costAndSell[i].cost=costAndSell[i-2].cost+sellCost[1];
                costAndSell[i].lastSellYear=i-2;
                break;
            case 2:
                costAndSell[i].cost=costAndSell[i-3].cost+sellCost[2];
                costAndSell[i].lastSellYear=i-3;
                break;
        }
    }
    sellYear=costAndSell[lastYear].lastSellYear;
    printf("sellAt[%d], cost[%d]\n", lastYear, costAndSell[lastYear].cost );

    do{
            sellYear=costAndSell[sellYear].lastSellYear;
            printf("sellAt[%d], cost[%d]\n", sellYear, costAndSell[sellYear].cost );
    } while( sellYear>0 );
}

void main(int argc, char * argv[]){
    int lastYear;
    initSellCost();
    lastYear=atoi(argv[1]);
    findBestPath(lastYear);
}

出力は次のとおりです。

sellAt[5], cost[228000]
sellAt[3], cost[176000]
sellAt[0], cost[100000]
于 2012-11-19T04:50:31.000 に答える
0

あなたが提供したリンクは動的計画法です-そしてコードは非常に読みやすいです。コードをよく見て、コードが何をしているのかを確認することをお勧めします。

于 2012-11-05T00:59:04.763 に答える
0

次の方法が機能する可能性があります。

毎年の終わりに、2つの選択肢があります。取引を選択するか、別の年の維持費を支払うことを選択できます。選択の余地がない3年目を除いて。あなたは確かに取引しなければなりません。

これは、特定の年に取引するのではなく、取引する中で最小コストを選択する再帰方式によって解決できます。

テーブルはオフセット、n年目（取引なし）で維持できるため、値を再計算する必要はありません

于 2012-11-05T08:01:58.120 に答える
0

最適な部分構造と重複する部分問題を見つけることができないため、動的計画法を使用できないと思います。N年のコストは、N-1、N-2、およびN-3年の動作によって異なります。最適な下部構造を見つけることは困難です。

于 2012-11-05T08:26:23.443 に答える