Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Minimizzazione del costo massimo
Forum - C/C++ - Minimizzazione del costo massimo

Avatar
Itachi-Dev (Normal User)
Newbie


Messaggi: 2
Iscritto: 12/02/2014

Segnala al moderatore
Postato alle 22:28
Mercoledì, 12/02/2014
Salve, ragazzi ho urgente bisogno di una mano per la soluzione di questo problema:


PROBLEMA: MINIMIZZAZIONE DEL COSTO MASSIMO


Sia G = (V,E) un grafo indiretto e connesso dove V è l’insieme dei nodi e E l’insieme degli archi;
Sia L una lista ordinata dei nodi V. Il costo di ogni arco è proporzionale alla distanza nella lista tra
i nodi che lo compongono. In questo modo, in base all’ordinamento
dei nodi nella lista, ogni arco potrà avere un costo differente.
Infine, il costo massimo del grafo cG sarà dato dal costo massimo
presente tra gli archi data una lista L.
Esempio:
La lista dei nodi appartenenti al grafo a destra può essere ordinata
in vari modi:
Per queste liste di esempio abbiamo che nel primo caso i costi dei vari collegamenti sono:
1,3,3,3,5,2,3,2 con il costo massimo (e perciò il costo del grafo) pari a 5, dato dall’arco che collega
il nodo c con il nodo h, e altre due liste dove il costo massimo è di 2 e 6 rispettivamente.
Scrivere un programma che dato un grafo G restituisca una lista L dei nodi V, ordinata in modo tale
che sia minimizzato il costo del grafo cG.


INPUT
L’input consiste in una serie di grafi. Ogni
linea conterrà la rappresentazione di un grafo.
La rappresentazione di un grafo avverrà
elencando tutti gli archi. Ogni arco presente
del grafo sarà separato dal simbolo “;”(punto
e virgola) e l’arco verrà rappresentato dai due
nodi (espressi in ordine alfabetico) divisi dal
simbolo “,”(virgola). Ogni linea terminerà
con il simbolo “.”(punto).
L’ultima riga conterrà la stringa “<END>”.
NOTA: Ogni grafo potrà avere massimo 10
nodi.


OUTPUT
L’output dovrà contenere una linea per ogni
linea di grafo dove viene riportata la lista
ordinata che consente di ottenere il costo
minimo del grafo con il relativo costo. Nota:
se esistono più liste che restituiscono un costo
minimo andrà riportata la prima in ordine
lessicografico.
La lista e il suo relativo costo dovranno essere
rappresentati in output riportando i nodi della
lista divisi dal simbolo “,”(virgola), dopo il
simbolo “=”(uguale) e il costo.


ESEMPIO INPUT
a,b;a,j;b,d;b,g;b,k;c,d;c,f;c,k;c,j;d,f;d,g;e,j;f, g;f,k;f,j;h,k;h,j;k,j.
a,b;a,f;a,h;b,d;b,f;c,e;c,f;c,g;e,f;e,g.
a,b;a,c;a,h;b,c;b,d;c,f;c,g;e,f;e,g;f,h.
a,b;a,d;b,c;b,d;b,e;d,e.
a,b;a,c;b,f;c,d;c,e.
a,b;a,e;a,f;b,d;c,e.
a,b;a,d;a,g;c,e;c,h;e,k;e,j;f,k;g,k.
a,b;a,c;a,d;b,d;d,e.
a,b;a,d;a,f;a,g;b,c;b,f;b,g;b,h;d,e;d,f;d,h;e,f;f, h.
a,b;a,f;a,g;b,c;b,d;b,f;d,e.
a,b;b,c;b,e;d,f;e,f.
<END>


ESEMPIO OUTPUT
b,a,g,d,k,j,f,c,h,e=4
d,h,b,a,f,c,e,g=2
a,b,h,c,d,f,g,e=3
a,d,b,e,c=2
b,a,f,c,d,e=2
b,d,a,e,f,c=2
b,a,d,g,f,k,c,e,h,j=2
b,a,d,c,e=2
c,g,a,b,d,f,h,e=3
c,f,b,a,d,g,e=2
a,b,c,e,d,f=2


Io ho provato a risolverlo ma il mio algoritmo funziona solamente per i grafi che abbiano meno di 7 nodi e non funziona neppure sempre.
Se qualcuno fosse interessato posso spiegare l'algoritmo da me generato e postare il relativo codice.


Grazie in anticipo,
Itachi.

Ultima modifica effettuata da pierotofy il 18/02/2014 alle 17:49
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 2:33
Giovedì, 13/02/2014


Il mio blog: https://piero.dev
PM Quote
Avatar
Itachi-Dev (Normal User)
Newbie


Messaggi: 2
Iscritto: 12/02/2014

Segnala al moderatore
Postato alle 14:54
Venerdì, 14/02/2014
EDIT

Ultima modifica effettuata da Itachi-Dev il 17/02/2014 alle 16:08
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 22:42
Venerdì, 14/02/2014
Non e' una soluzione efficente... e' O(|E| log |V|) se implementato con un binary-heap, non so quanto piu' veloce stai cercando di farlo... ma ho l'impressione che probabilmente il tuo approccio generale al problema sia sbagliato.

Testo quotato


(In riferimento all'algoritmo di Dijkstra's): This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.



Forse se ci spieghi per bene tutto il progetto e cosa stai cercando di fare ti si puo' dare soluzioni alternative.


Il mio blog: https://piero.dev
PM Quote
Avatar
nessuno (Normal User)
Guru^2


Messaggi: 6380
Iscritto: 03/01/2010

Segnala al moderatore
Postato alle 23:32
Lunedì, 17/02/2014
Cancellare i post perché non hai ricevuto risposte soddisfacenti non è molto educato ...


Ricorda che nessuno è obbligato a risponderti e che nessuno è perfetto ...
---
Il grande studioso italiano Bruno de Finetti (uno dei padri fondatori del moderno Calcolo delle probabilità) chiamava il gioco del Lotto Tassa sulla stupidità.
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 17:51
Martedì, 18/02/2014
Tie', ripristinato il post originale e bannato.


Il mio blog: https://piero.dev
PM Quote