Problema catena di montaggio (algoritmo)

[daVinco]

Salve ragazzi,
Ho bisogno di un aiutino per fare un algoritmo di una catena di montaggio.
Il problema è creare una catena di montaggio. Ci sono x pezzi e per ogni postazione ci possono essere al massimo y pezzi.
x e y sono presi da input.
Determinare la catena di montaggio minima possibile.
Sia P un insieme di x Pezzi e l'insieme D i pezzi che servono ad un pezzo per essere costruito.
Per creare P nella catena di montaggio deve essere presente l'intero insieme D.

P={A,B,C,D,E}
Per ogni pezzo i suoi pezzi precedenti.

D(A) = insieme vuoto Ø
D(B) = A
D(C) = B
D(D) = B
D(E) = D

Esempio 1:
Supponiamo che x è 5 e y è 2.
1) Il Pezzo A è un pezzo base.
2) Per costruire B serve A.
3) Per costruire C serve B.
4) Per costruire D serve B.
5) Per costruire E serve D.
In questo caso l'ordine sarebbe A - B - C&D- E.
C&D non sono dipendenti da loro ed entrambi possono essere costruiti insieme.
La lunghezza della catena è 4.

Esempio 2:
Supponiamo che x è 6 e y è 2.
1) A è il pezzo base.
2) Per B serve A.
3) Per S serve A B e D.
4) Per C serve A.
5) Per D serve A.
6) Per X serve S.
In questo caso l'ordine sarebbe A - B&D - C&S - X. La catena è lunga 4.
Da notare che le istruzioni non sono in ordine quindi se avrei messo B&C al posto di B&D la catena
di montaggio era lunga 5 perché: A - B&C - D - S - X.

Grazie in anticipo ragazzi.

[Scara95]

Costruisci il grafo orientato dei componenti e parti a costruire la catena dalla fine scegliendo sempre il numero massimo che puoi scegliere di componenti che non hanno archi in uscita e rimuovendo gli archi entranti in esso (se lavori contemporaneamente sul grafo e sul suo trasposto fai prima)
Esce una catena diversa da quella da te proposta ma dovrebbe essere sempre di lunghezza minima, anche se non mi sono posto il problema di dimostrarlo...

Esempio

A -> B C A S
B -> S
C ->
D -> S
S -> X
X ->

X&C

A -> B D S
B -> S
D -> S
S ->

S X&C

A -> B D
B ->
D ->

B&D S X&C

A ->

A B&D S X&C

[daVinco]

Salve grazie mille per la risposta,
C'è un particolare che ho dimenticato.
La catena di montaggio parte da un pezzo unico e termina con un pezzo unico. Quindi non ci possono essere 2 pezzi nella prima e nell'ultima cella ma solo sulle successive.

A -> B C A S

E un pezzo non può dipendere da se stesso.
Mi sa che così cambia un po il problema..

[Scara95]

Quello era un errore di battitura, era evidentemente una D.
L'algoritmo funziona uguale, io l'ho solo applicato a uno dei tuoi esempi dove c'erano più pezzi finali, ovvero nodi che non avevano archi uscenti. Non ho fatto altro che costruire il grado che mi hai dato...

[daVinco]

Il problema sorge in questo esempio:

Pezzi sono 7 e i posti sono 2
F -> X
X -> P
B -> X F D S
D -> A
S -> A
A ->
P -> A

Il numero di pezzi che si possono costruire contemporaneamente è uguale a 2.

D -> A
S -> A
P -> A

Questi 3 pezzi possono essere costruiti allo stesso tempo, però nella catena di montaggio ci sono 2 posti. In base a quale si inserisce prima cambia la soluzione successiva, perché se dopo A inserisco prima D & S allora poi segue P X F B, quindi il cammino è 5.
Invece se inserisco P prima diventa così: A D&P S&X F ed il cammino è 4.

Non so se mi sono spiegato..

[Scara95]

Pesa ogni nodo con la sua distanza massima dall'origine e scegli sempre i nodi con peso maggiore.

[daVinco]

Ho risolto in un altro modo. Grazie, potete chiudere la discussione.