在哪里可以找到 Cormen 装配线调度的在线示例？[关闭]

Question

这是一个与学校相关的问题，尽管不完全是家庭作业。

我正在学习算法课程，目前正在学习《算法》的第 15 章 Cormen 的算法导论 书。我已经成功地找到了本书中大多数算法的大量在线示例，并且通常可以找到某种类型的 Java 小程序或其他程序，它们可以很好地可视化算法的工作原理。

一个例外是第 15 章（动态编程）中的装配线调度。

有人知道有任何在线资源可以提供装配线调度算法的进一步示例或可视化吗？

Answer 1

我认为如果您搜索该技术的示例/可视化而不是具体问题，您会运气更好......IE。搜索动态规划。

TopCoder 上可能有一些不错的教程”动态规划网站：topcoder.com".

Answer 2

如果你想解决方案，我写了一个练习。这是动态编程的一个例子。这意味着，您的解决方案从重复计算不闻不问。如果一个问题可能在某些情况下可分为亚单位，这些亚单位得到重复的，那么就没有必要来解决这些问题不止一次。在这样的情况下，你存储在第一时间之后该溶液中，以后重新使用。

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/ 〜韦尔奇/教学/ 411.f14 / dp.pdf