0

これは学校に関する質問ですが、宿題ではありません。

私はアルゴリズムのコースを受講しており、現在、Cormen の本、アルゴリズム入門の第 15 章に取り組んでいます。私はこの本のほとんどのアルゴリズムのオンラインの例をたくさん見つけることに成功しており、通常、アルゴリズムがどのように機能するかをよく視覚化する Java アプレットやその他のプログラムを見つけることができます。

その例外は、第 15 章 (動的プログラミング) の Assembly-Line スケジューリングです。

Assembly-Line Scheduling アルゴリズムのさらなる例や視覚化を提供するオンライン リソースを知っている人はいますか?

4

2 に答える 2

1

特定の問題ではなく、手法の例/視覚化を検索すると、運が良くなると思います...つまり、動的プログラミングを検索します。

TopCoder の「動的プログラミング サイト:topcoder.com 」には、まともなチュートリアルがいくつかあるかもしれません。

于 2009-12-27T20:39:02.090 に答える
0

解決策が必要な場合は、練習用に書きました。これは動的計画法の例です。これは、ソリューションが反復計算を控えていることを意味します。問題がサブユニットに分割でき、それらのサブユニットがいくつかのシナリオで繰り返される場合、それらを複数回解決する必要はありません。このような場合は、最初に解決策を保存し、後で再利用します。

package com.zafar;

import java.util.Scanner;

public class AssemblyLineProblem {
    public static void main(String arg[]){
        Scanner scanner =new Scanner(System.in);

    int numberOfStations=scanner.nextInt();
    Station firstLine[]=new Station[numberOfStations];
    Station secondLine[]=new Station[numberOfStations];

    for(int i=0;i<numberOfStations;i++){
        firstLine[i]=new Station(i,scanner.nextInt());
        firstLine[i].setIndex(i);
        firstLine[i].setTransferCost(scanner.nextInt());
        firstLine[i].setNameOfLine("line 1");
    }
    for(int i=0;i<numberOfStations;i++){
        secondLine[i]=new Station(i,scanner.nextInt());
        secondLine[i].setIndex(i);
        secondLine[i].setTransferCost(scanner.nextInt());           
        secondLine[i].setNameOfLine("line 2");
    }
    int entryCostLine1=scanner.nextInt();
    int entryCostLine2=scanner.nextInt();
    Station beginStation=findOptimalRoute(numberOfStations, firstLine, secondLine, entryCostLine1, entryCostLine2);
    System.out.println("The optimal route is");
    print(beginStation);
    scanner.close();

}
public static void print(Station station){
    if(station==null)
        return;
    System.out.println(station.getNameOfLine()+", station "+station.getIndex()+", cost from here: "+station.getOptimalCostFromThisStation());       
    print(station.getNextOptimalStation());
}

public static Station findOptimalRoute(int numberOfStations,
        Station[] firstLine, Station[] secondLine, int entryCostLine1,
        int entryCostLine2) {
    for(int i=numberOfStations-1;i>=0;i--){
        if(i==numberOfStations-1)
        {
            firstLine[i].setOptimalCostFromThisStation(firstLine[i].getTransferCost());
            secondLine[i].setOptimalCostFromThisStation(secondLine[i].getTransferCost());
        }else{
            calculateOptimalStation(firstLine, secondLine, i);
            calculateOptimalStation(secondLine, firstLine, i);                          
        }               
    }
    if((entryCostLine1+firstLine[0].getCost()+firstLine[0].getOptimalCostFromThisStation())>= (entryCostLine2+secondLine[0].getCost()+secondLine[0].getOptimalCostFromThisStation())){
        return secondLine[0];
    }else
        return firstLine[0];

}
public static void calculateOptimalStation(Station[] currentLine, Station[] otherLine, int indexOfCurrentStation){

    int costOnContinuingOnSameLine= (currentLine[indexOfCurrentStation+1].getCost()+currentLine[indexOfCurrentStation+1].getOptimalCostFromThisStation());

    int costOnSwitchingLines=(currentLine[indexOfCurrentStation].getTransferCost()+otherLine[indexOfCurrentStation+1].getCost()+otherLine[indexOfCurrentStation+1].getOptimalCostFromThisStation()) ;
    if((costOnContinuingOnSameLine  <= costOnSwitchingLines)){
        currentLine[indexOfCurrentStation].setOptimalCostFromThisStation(costOnContinuingOnSameLine);
        currentLine[indexOfCurrentStation].setNextOptimalStation(currentLine[indexOfCurrentStation+1]);
    }
    else{
        currentLine[indexOfCurrentStation].setOptimalCostFromThisStation(costOnSwitchingLines);
        currentLine[indexOfCurrentStation].setNextOptimalStation(otherLine[indexOfCurrentStation+1]);
    }


}

}

class Station{
    private String nameOfLine;
    private int index;
    private int cost;
    private int transferCost;
    private Station nextOptimalStation;
    private int optimatCostFromThisStation=0;
    public Station(int index, int cost){
        this.index=index;
        this.cost=cost;
    }
    public int getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
    public int getCost() {
        return cost;
    }
    public void setCost(int cost) {
        this.cost = cost;
    }
    public Station getNextOptimalStation() {
        return nextOptimalStation;
    }
    public void setNextOptimalStation(Station nextOptimalStation) {
        this.nextOptimalStation = nextOptimalStation;
    }
    public int getTransferCost() {
        return transferCost;
    }
    public void setTransferCost(int transferCost) {
        this.transferCost = transferCost;
    }
    public int getOptimalCostFromThisStation() {
        return optimatCostFromThisStation;
    }
    public void setOptimalCostFromThisStation(int optimatCostFromThisStation) {
        this.optimatCostFromThisStation = optimatCostFromThisStation;
    }
    public String getNameOfLine() {
        return nameOfLine;
    }
    public void setNameOfLine(String nameOfLine) {
        this.nameOfLine = nameOfLine;
    }

}

入力: 6

7 2 9 3 3 1 4 3 8 4 4 3

8 2 5 1 6 2 4 2 5 1 7 2

2 4

出力：

最適ルートは

路線 1、駅 0、ここからのコスト: 29

ライン 2、駅 1、ここからのコスト: 22

ライン 1、駅 2、ここからのコスト: 18

2 号線、3 駅、ここからの料金: 13

2 号線、4 駅、ここからの料金: 8

1番線、5番駅、ここからの料金: 3

その他のリソース: https://parasol.tamu.edu/~welch/teaching/411.f14/dp.pdf

于 2016-08-05T09:55:16.010 に答える