Wo kann ich Online Beispiele für Cormen Versammlung-Line Scheduling finden? [geschlossen]

Question

Dies ist eine schulbezogene Frage, wenn auch nicht genau Hausaufgaben.

Ich nehme einen Algorithmen Kurs, die derzeit auf Kapitel arbeiten 15 von Cormen der Einführung in Algorithmen Buch. Ich habe viele Online-Beispiele für die meisten der Algorithmen in dem Buch zu finden, erfolgreich gewesen, und ich kann in der Regel eine Art von Java-Applet oder einem anderen Programm, das eine gute Visualisierung bietet, wie die Algorithmen arbeiten.

Eine Ausnahme, dass die Assembly-Line Scheduling in Kapitel 15 (Dynamic Programming).

Weiß jemand, der irgendwelche Online-Ressourcen, die weiteren Beispiele oder Visualisierungen des Assembly-Line Scheduling-Algorithmus zur Verfügung stellen?

Answer 1

Ich denke, Sie werden mehr Glück haben, wenn Sie für Beispiele / Visualisierungen der Technik suchen, anstatt das spezifische Problem ... das heißt für die dynamische Programmierung suchen.

Es kann einige gute Tutorials auf TopCoder sein " dynamische Programmierung Website: topcoder.com “.

Answer 2

Wenn Sie die Lösung wollen, schrieb ich eine für die Praxis. Dies ist ein Beispiel der dynamischen Programmierung. Es bedeutet, dass Ihre Lösung aus repetitiven Berechnungen verzichtet. Wenn ein Problem in Untereinheiten aufgeteilt werden könnte, und diese Untereinheiten in einigen Szenarien wiederholt zu bekommen, dann ist es nicht notwendig, sie mehr zu lösen als einmal. In solchen Fällen speichern Sie die Lösung nach dem ersten Mal und wieder verwenden es später.

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;
    }

}

Input: 6

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

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

2 4

Ausgabe:

Die optimale Route ist

Linie 1, Haltestelle 0, Kosten von hier: 29

Linie 2, Station 1, Kosten von hier: 22

Linie 1, Station 2, die Kosten von hier: 18

Linie 2, Station 3, Kosten von hier: 13

Linie 2, Haltestelle 4, Kosten von hier: 8

Linie 1, Station 5, Kosten von hier: 3

Weitere Informationen: https://parasol.tamu.edu/ ~ walisisch / Lehre / 411.f14 / dp.pdf