Ottimizzare ricerca soluzione

di
triack78
il
7 risposte
T
triack78
Pochi posts
Iscritto da
nov, 2016
Messaggi:
12

Ottimizzare ricerca soluzione

Ciao a tutti,

non so se è il gruppo giusto dove postare(il linguaggio usato è java, ma la mia è una domanda teorica).
Se io avessi ad esempio otto vettori numerici e volessi trovare otto numeri(il primo numero appartenente al primo vettore, il secondo numero al secondo vettore, ecc...) che soddisfino tutti insieme una data condizione come potrei fare?

La soluzione più semplice sarebbe calcolare tutte le permutazioni possibili e stampare i numeri che soddisfino la condizione.
Esempio di classe java:

public class Combinazioni {

private long[] p1={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
private long[] p2={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
private long[] p3={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
private long[] p4={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
private long[] p5={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
private long[] p6={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
private long[] p7={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
private long[] p8={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

public void calcola()
{
long prodotto=0;
for(int a=0;a<15;a++)
for(int b=0;b<15;b++)
for(int c=0;c<15;c++)
for(int d=0;d<15;d++)
for(int e=0;e<15;e++)
for(int f=0;f<15;f++)
for(int g=0;g<15;g++)
for(int h=0;h<15;h++)
{
if(p1[a]+p2+p3[c]+p4[d]+p5[e]+p6[f]+p7[g]+p8[h]<10){
System.out.println(p1[a]+" "+p2+" "+p3[c]+" "+p4[d]+" "+p5[e]+ " "+p6[f]+" "+p7[g]+" "+p8[h]);
prodotto++;
}


}
System.out.println(prodotto+ " combinazioni trovate!");
return;
}

public static void main(String[] args){
Combinazioni combinazioni=new Combinazioni();
long inizio=System.currentTimeMillis();
combinazioni.calcola();
long fine=System.currentTimeMillis();
System.out.println("Tempo impiegato: "+(fine-inizio)+ "ms!");
}

}

NB: I vettori hanno valori tutti uguali per comodità, in realtà ai fini della mia richiesta dovrebbero essere formati ad esempio da 15 numeri casuali ciascuno(con ciascun numero compreso tra 1 e 15 ad esempio).

In questo modo testo tutte le combinazioni possibili (che in questo caso sono 15^8=2.562.890.625, corretto?) e ottengo il seguente output:

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 2
1 1 1 1 1 1 2 1
1 1 1 1 1 2 1 1
1 1 1 1 2 1 1 1
1 1 1 2 1 1 1 1
1 1 2 1 1 1 1 1
1 2 1 1 1 1 1 1
2 1 1 1 1 1 1 1
9 combinazioni trovate!
Tempo impiegato: 33651ms!

Il tempo impiegato sul mio supercomputer ( ) è di quasi 34 secondi. Per ottenere 9 risultati. (che rispetto all'insieme considerato è un'inezia).
Questo non mi sembra molto efficiente.
In realtà osservando gli 8 vettori(che, ripeto sono tutti uguali solo per semplificare) mi accorgo che posso non eseguire molte iterazioni:

ad esempio se il primo numero è 15 non occorre fare le rimanenti 15^7 permutazioni(corretto?) perchè già il primo numero è maggiore di 9, se il primo numero è 7, il secondo è 1 e il terzo è 2 non occorre fare le rimanenti 15^5 permutazioni e così via....

Praticamente ipoteticamente ed idealmente dovrei avere 15 alberi n-ari(con ciascuna radice presa dai 15 valori del primo vettore) dove tutti i cammini di profondità 8 rappresentano le soluzioni al problema mentre tutti i cammini con profondità <8 quelli che non soddisfano il problema(scusate per le evetuali "imprecisioni" (per usare un eufemismo) che potrei dire ma ormai l'università è un lontano ricordo).
Innanzitutto quanto ho detto è corretto?
Mi potreste spiegare come fare ad implementare quanto detto(delle linee guida, non chiedo la "pappa pronta") o indicarmi un qualche sito che spieghi in modo semplice come applicare questo modo di procedere?

Grazie mille

7 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6011

    Re: Ottimizzare ricerca soluzione

    Visto che la descrizione del problema ha richiesto un post lungo un kilometro, il problema NON E' semplice e quindi NON PUO' avere una soluzione semplice

    E questo e' un ASSIOMA

    Ora, un problema di ottimizzazione e' un problema che richiede di trovare un massimo o un minimo di una funzione obiettivo, assegnato un certo numero di vincoli per TUTTE le variabili in gioco (prese singolarmente o in qualche forma aggregata, ma per TUTTE !!!)

    Ora, il tuo non e' un problema di ottimizzazione: hai solo un vincolo per un'aggregazione delle variabili e non c'e' una funzione obiettivo da massimizzare/minimizzare.

    Ma, supponiamo di voler ottimizzare il TEMPO DI CALCOLO per il TUO problema.
    Per ridurre i tempi il sistema e' sempre lo stesso: NON ESEGUIRE calcoli/elaborazioni inutili o fare due volte lo stesso calcolo/elaborazione.

    E questo lo si fa utilizzando un APPROCCIO INCREMENTALE, creando soluzioni parziali., oppure cercando SOLUZIONI APPROSSIMATE, che sono degli ottimi locali, non neccessariamente un ottimo globale.

    E qui' si puo' usare un backtracking o un algoritmo greedy, assistiti da funzioni euristiche che permettono di decidere per tempo/in anticipo se conviene continuare da una soluzione parziale per trovarne una migliore oppure no, oppure il minimo/massimo locale puo' ragionevolmente essere usato al posto del mini/max globale.

    In pratica, la soluzione del tuo problema richiese TRE corsi universitari semestrali/annuali: ricerca operativa, algoritmi e strutture dati, introduzione all'intelligenza artificiale.



    Altro ASSIOMA: l'universita' e' solo il viottolo che porta alla superstrada! NON un 'cul de sac'

    Quindi quanto hai detto e' corretto, e NO, NON TI SCUSIAMO per le imprecisioni! Per ovviare alle imprecisioni basta andare a ripassare quanto si aveva studiato: una buona occasione per rinfrescare la memoria
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Ottimizzare ricerca soluzione

    @triack78: hai già postato una cosa praticamente uguale qui:
    https://www.iprogrammatori.it/forum-programmazione/java/velocizzare-operazioni-computer-multiprocessor-t29600.html

    dove ero intervenuto io ma poi non avevi minimamente continuato o risposto.
  • T
    triack78
    Pochi posts
    Iscritto da
    nov, 2016
    Messaggi:
    12

    Re: Ottimizzare ricerca soluzione

    Ciao a tutti e grazie per le risposte.
    Come suggeritomi sto rinfrescando le mie conoscenze ma nel frattempo per risolvere il mio problema ho elaborato una soluzione sporca che volevo condividere.
    Ho aggiunto un metodo ottimizzato oltre a quello che avevo usato.
    Di seguito il codice completo della classe:

    mport java.util.ArrayList;
    import java.util.LinkedHashMap;
    import java.util.List;
    import java.util.Map;

    public class Combinazioni {

    private int[] p1={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    private int[] p2={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    private int[] p3={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    private int[] p4={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    private int[] p5={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    private int[] p6={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    private int[] p7={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    private int[] p8={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

    // private int[] p1={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
    // private int[] p2={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
    // private int[] p3={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
    // private int[] p4={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
    // private int[] p5={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
    // private int[] p6={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
    // private int[] p7={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
    // private int[] p8={15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};

    public void calcola()
    {
    long prodotto=0;
    for(int a=0;a<15;a++)
    for(int b=0;b<15;b++)
    for(int c=0;c<15;c++)
    for(int d=0;d<15;d++)
    for(int e=0;e<15;e++)
    for(int f=0;f<15;f++)
    for(int g=0;g<15;g++)
    for(int h=0;h<15;h++)
    {
    if(p1[a]+p2+p3[c]+p4[d]+p5[e]+p6[f]+p7[g]+p8[h]<10){
    System.out.println(p1[a]+" "+p2+" "+p3[c]+" "+p4[d]+" "+p5[e]+ " "+p6[f]+" "+p7[g]+" "+p8[h]);
    prodotto++;
    }


    }
    System.out.println(prodotto+ " combinazioni trovate!");
    return;
    }

    public void calcolaOttimizzato(){

    long iterazioni=0;

    //Dichiarazione strutture dati
    Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>>>> livello1=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>>>> ();
    Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>>> livello2=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>>> ();
    Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>> livello3=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>> ();
    Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>> livello4=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>> ();
    Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>> livello5=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>> ();
    Map<Integer,Map<Integer,Map<Integer,List<Integer>>>> livello6=new LinkedHashMap<Integer,Map<Integer,Map<Integer,List<Integer>>>> ();
    Map<Integer,Map<Integer,List<Integer>>> livello7=new LinkedHashMap<Integer,Map<Integer,List<Integer>>> ();
    Map<Integer,List<Integer>> livello8=new LinkedHashMap<Integer,List<Integer>> ();

    Map<Integer,Map<Integer,Map<Integer,List<Integer>>>> livello1Temp=new LinkedHashMap<Integer,Map<Integer,Map<Integer,List<Integer>>>> ();
    Map<Integer,Map<Integer,List<Integer>>> livello2Temp=new LinkedHashMap<Integer,Map<Integer,List<Integer>>> ();
    Map<Integer,List<Integer>> livello3Temp=new LinkedHashMap<Integer,List<Integer>> ();

    //Dichiarazione contenitori temporanei
    List<Integer> valoriLivello8=new ArrayList<Integer>();

    long fisso=1;

    //Inizio popolamento struttura dati
    for(int a=0;a<p1.length;a++){
    iterazioni++;
    if(p1[a]<10){
    livello1.put(p1[a],livello2);
    if(!livello2.isEmpty()){
    livello2=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>>> ();
    livello1.put(p1[a],livello2);
    }
    for(int b=0;b<p2.length;b++){
    iterazioni++;
    if(p1[a]+p2<10){
    livello2.put(p2,livello3);
    livello3=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>> ();
    livello2.put(p2,livello3);
    for(int c=0;c<p3.length;c++){
    iterazioni++;
    if(p1[a]+p2+p3[c]<10){
    livello3.put(p3[c],livello4);
    livello4=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>> ();
    livello3.put(p3[c],livello4);

    for(int d=0;d<p4.length;d++){
    iterazioni++;
    if(p1[a]+p2+p3[c]+p4[d]<10){
    livello4.put(p4[d],livello5);
    livello5=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>();
    livello4.put(p4[d],livello5);
    for(int e=0;e<p5.length;e++){
    iterazioni++;
    if(p1[a]+p2+p3[c]+p4[d]+p5[e]<10){
    livello5.put(p5[e],livello6);
    livello6=new LinkedHashMap<Integer,Map<Integer,Map<Integer,List<Integer>>>>();
    livello5.put(p5[e],livello6);
    for(int f=0;f<p6.length;f++){
    iterazioni++;
    if(p1[a]+p2+p3[c]+p4[d]+p5[e]+p6[f]<10){
    livello6.put(p6[f],livello7);
    livello7=new LinkedHashMap<Integer,Map<Integer,List<Integer>>>();
    livello6.put(p6[f],livello7);
    for(int g=0;g<p7.length;g++){
    iterazioni++;
    if(p1[a]+p2+p3[c]+p4[d]+p5[e]+p6[f]+p7[g]<10){
    livello7.put(p7[g],livello8);
    livello8=new LinkedHashMap<Integer,List<Integer>>();
    livello7.put(p7[g],livello8);
    valoriLivello8=new ArrayList<Integer>();
    for(int h=0;h<p8.length;h++){
    iterazioni++;
    if(p1[a]+p2[b]+p3[c]+p4[d]+p5[e]+p6[f]+p7[g]+p8[h]<10){
    valoriLivello8.add(p8[h]);
    livello8.put(10, valoriLivello8);
    System.out.println(p1[a]+" "+p2[b]+" "+p3[c]+" "+p4[d]+" "+p5[e]+ " "+p6[f]+" "+p7[g]+" "+p8[h]);
    }
    }

    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }}

    //System.out.println(livello1);

    }
    System.out.println("Iterazioni="+iterazioni);
    }

    public static void main(String[] args){
    Combinazioni combinazioni=new Combinazioni();
    System.out.println("-------SOLUZIONE OTTIMIZZATA-------");
    long inizio=System.currentTimeMillis();
    combinazioni.calcolaOttimizzato();
    long fine=System.currentTimeMillis();
    System.out.println("Tempo impiegato: "+(fine-inizio)+ "ms!");
    System.out.println("");
    System.out.println("-------SOLUZIONE NON OTTIMIZZATA-------");
    inizio=System.currentTimeMillis();
    combinazioni.calcola();
    fine=System.currentTimeMillis();
    System.out.println("Tempo impiegato: "+(fine-inizio)+ "ms!");


    }
    }
    E i tempi impiegati dalle due routine:

    -------SOLUZIONE OTTIMIZZATA-------
    1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 2
    1 1 1 1 1 1 2 1
    1 1 1 1 1 2 1 1
    1 1 1 1 2 1 1 1
    1 1 1 2 1 1 1 1
    1 1 2 1 1 1 1 1
    1 2 1 1 1 1 1 1
    2 1 1 1 1 1 1 1
    Iterazioni=7530
    Tempo impiegato: 16ms!

    -------SOLUZIONE NON OTTIMIZZATA-------
    1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 2
    1 1 1 1 1 1 2 1
    1 1 1 1 1 2 1 1
    1 1 1 1 2 1 1 1
    1 1 1 2 1 1 1 1
    1 1 2 1 1 1 1 1
    1 2 1 1 1 1 1 1
    2 1 1 1 1 1 1 1
    9 combinazioni trovate!
    Tempo impiegato: 20859ms!

    Ovviamente sono ben accette critiche

    Grazie
  • T
    triack78
    Pochi posts
    Iscritto da
    nov, 2016
    Messaggi:
    12

    Re: Ottimizzare ricerca soluzione

    @andbin: Grazie per la precisazione, in realtà pensavo fossero due argomenti differenti(pur trattando gli stessi argomenti uno era un'ottimizzazione algoritmica, l'altra un'ottimizzazione per parallelizzare i calcoli)
  • T
    triack78
    Pochi posts
    Iscritto da
    nov, 2016
    Messaggi:
    12

    Re: Ottimizzare ricerca soluzione

    @andbin: Grazie per la precisazione, in realtà pensavo fossero due argomenti differenti(pur trattando gli stessi argomenti uno era un'ottimizzazione algoritmica, l'altra un'ottimizzazione per parallelizzare i calcoli)
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6272

    Re: Ottimizzare ricerca soluzione

    triack78 ha scritto:

    Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>>>> livello1=new LinkedHashMap<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,Map<Integer,List<Integer>>>>>>>>> ();
    Ehh????
    Ma scherzi?
  • T
    triack78
    Pochi posts
    Iscritto da
    nov, 2016
    Messaggi:
    12

    Re: Ottimizzare ricerca soluzione

    Boh ci ho provato
    L'ho provato con due set di numeri (quelli commentati) e mi restituisce risultati corretti(anche se molto probabilmente sto dicendo cazzate e ho preso una cantonata gigantesca ). Le hashMap innestate erano anche per vedere se venivano filtrati correttamente i dati.
Devi accedere o registrarti per scrivere nel forum
7 risposte