Varie

Esercizio

d26.jpg

Per prima cosa analizziamo la soluzione. Una soluzione al problema è una collocazione delle tifoserie in modo tale in ogni settore ci siano tifoserie gemellate tra loro (nel caso in quel settore ci sia più di una tifoseria) in modo completo. Cioè se ci sono le tifoserie A,B,C queste formano un "triangolo" in termini di gemellaggi. Infatti se ad un settore appartesse una tifoseria non gemellata con qualche altra tifoseria nel settore, si potrebbero avere disordini.
Osservazioni:

  • Se una tifoseria A è gemellata con B, si ha anche il viceversa.

algoritmo risolutivo

L'idea seguente si basa sul fatto che dobbiamo considerare lo spazio di ricerca (potrebbero esserci altre soluzioni ma forse sarebbero meno affini alla teoria vista), ovvero tutte le strade possibili, ovvero una sorta di backtraking (perchè alla fine l'analisi dello spazio di ricerca, con algoritmi semplici, è equivalente al backtracking solo che l'approccio è diverso).

Dunque, per generale lo spazio di ricerca (che è un albero) si procede così:
La radice contiene tutti i settori vuoti (le informazioni riguardo le tifoserie sono a parte e sono immutabili).
Dalla radice si può scegliere quale tifoseria sarà assegnata al primo settore, quindi i figli della radice sono tanti quante sono le tifoserie.
Tutti i nodi successivi, non foglia, fanno la seguente operazione:
Esaminano il settore precedentemente riempito con la tifoseria scelta nel nodo genitore. Data questa tifoseria cercano le tifoserie gemellate tra le tifoserie ancora non assegnate ai settori dello stadio.
Preso questo insieme di tifoserie prendono la prima tifoseria (o una scelta a caso nell'insieme) e verificano se è gemellata con le tifoserie rimanenti nell'insieme, così da escludere eventuali tifoserie incompatibili. Questa operazione si ripete per ogni tifoseria che potrebbe stare nel settore.
Fatto questo si ha l'insieme di tifoserie che possono sicuramente stare nel settore assieme alla tifoseria già presente in questo, e quindi si assegnano le tifoserie a questo settore.
Poi si sceglie una tifoseria tra quelle rimanenti e la si assegna ad un nuovo settore, se ne esistono.

Se non esistono più settori ma ci sono tifoserie libere, si ritorna falso.
Se non esistono tifoserie libere si torna vero.

In pseducodice

//efficacia, non efficienza. (quando si ha poco tempo e non si è skilled)
 
//var globali
int settoriRimasti = settori.length;
int indiceSettoreDaAnalizzare = 0;
tifoseria ultimaTifoseriaAssegnata;
array settori;
 
boolean cercaAssegnamento(lista tifoserie){
  if (tifoserie.size() == 0 && settoriRimasti >= 0){
    return true;
  }
  if (tifoserie.size() > 0 && settoriRimasti == 0){
    return false;
  }
  lista tifoserieGemellateRimaste = trovaTifoserieGemellate(ultimaTifoseriaAssegnata, tifoserie);
  settori[indiceSettoreDaAnalizzare] = tifoserieGemellateRimaste;
  settoriRimasti --;
  lista tifoserieRimaste = tifoserie.copia(); //altrimenti modifichiamo la lista ed il for del metodo chiamante impazzisce
  lista tifoserieRimaste = tifoserieRimaste.rimuoviElementi(settore[indiceSettoreDaAnalizzare]);
  indiceSettoreDaAnalizzare++;
  for (int i=0; i<tifoserieRimaste.size(); i++){
    ultimaTifoseriaAssegnata = tifoserieRimaste.get(i); 
    if (cercaAssegnamento(lista tifoserie)){
      return true;
    }
  }
  if (tifoserieRimaste.size() == 0 && settoriRimasti >= 0){
    //potrebbe essere che con le tifoserie gemellate abbiamo consumato tutto
    //ed il for non si esegue
    return true;
  }
  return false;
}
 
lista trovaTifoserieGemellate(tifoseria ultimaTifoseriaAssegnata, lista tifoserie){
  lista result = new lista() ;
  result.add(ultimaTifoseriaAssegnata);
  for (int i=0; i<tifoserie.size(); i++){
    Tifoseria temp = tifoserie.get(i); 
    if (verificaGemellaggi(result, temp)){
      result.add(temp);
    }
  }
  return result;
}
 
boolean verificaGemellaggi(lista listaT, tifoseria t){
  for each tifoseria 'e' in listaT {
     if (!e.gemellata(t)){
      return false;
     }
  }
  return true;  
}

Non so se l'algoritmo funziona, ma per quanto ho pensato non trovo un'istanza, che ammetta almeno un assegnamento, che viene riconosciuta come istanza no dall'algoritmo.

Esercizio

d27.jpg

L'algoritmo è simile a quello dell'esercizio di prima solo che abbiamo due casi.

Algoritmo risolutivo primo caso

Si cerca esattamente il massimo del gradimento, non essendo sicuro che un'eventuale euristica trovi sempre il massimo (richiederebbe tempo per essere provata, almeno per la mia abilità) si procede con il depth first classico.
Lo pseudocodice è il seguente:

1. Se non ci sono più persone da assegnare calcola la somma dei gradimenti "attivi" 
      //cioè i gradimenti efffettivamente in atto data la disposizione delle persone.
      se la somma è maggiore di quelle ottenute in precedenza, segna la somma corrente come somma massima
      e segna la disposizione corrente come migliore disposizione
      dopodichè termina il metodo.
2. altrimenti
     Per ogni persona non seduta ad un tavolo {
       assegnala ad un tavolo libero se ne esistono e richiama il metodo a partire da 1.
         //prima chiamata ricorsiva
       per ogni tavolo occupato {
         assegnala ad un tavolo occupato dove può stare senza generare conflitti
           //una chiamata ricorsiva per ogni tavolo già occupato
       }
     }

In questo modo si ha depth first e backtracking

Algoritmo risolutivo secondo caso

Non si richiede proprio il massimo, ma qualcosa che si avvicini il più possibile al massimo. Visto il tempo a disposizione si procede con un algoritmo greedy. Abbiamo due possibilità, considerare prima le persone con più affinità possibili, oppure quelle con meno. Siccome vogliamo sfruttare al massimo i tavoli, ad occhio ci conviene iniziare con quelle con meno affinità (ad occhio perchè il tempo è limitato e per fare una verifica forse ne impiegheremmo troppo)

1. Se non ci sono più persone da assegnare calcola la somma dei gradimenti "attivi" 
      //cioè i gradimenti efffettivamente in atto data la disposizione delle persone.
      se la somma è maggiore di quelle ottenute in precedenza, segna la somma corrente come somma massima
      e segna la disposizione corrente come migliore disposizione.
      Dopodichè termina il metodo.
2. altrimenti
     ordina le persone non sedute per quantità di affinità, cioè la persona che gradisce il minor numero di persone 
     (non con la somma di gradimento più bassa) sarà la prima della lista delle persone.

     Per ogni persona non seduta ad un tavolo seguendo l'ordine ottenuto{
       se esistono tavoli occupati
         verifica in quale tavoli può sedersi e scegli quello con il massimo indice di gradimento attivo per la persona
         richiama il metodo da 1.
           //nota: in questo modo creiamo tavoli di persone poco sociali in generale ma molto sociali tra loro, anche se
           //non andiamo dietro la somma del gradimento.

       //in ogni caso (2a chiamata ricorsiva)
       assegnala ad un tavolo libero se ne esistono e richiama il metodo a partire da 1.
         //si potrebbe dire di fare questa chiamata solo se la persona non si può sedere
         //ma potrebbe essere il caso che una persona molto socievole si segga ad un tavolo di persone poco
         //socievoli, sprecando un sacco di gradimento. Quindi la seconda chiamata ci vuole almeno per
         //evitare questo caso banale visto che non stiamo seguendo il gradimento in se ma la
         //socievolezza (non come chiede l'esercizio).
       }
     }

Un altro caso ancora sarebbe quello di ordinare, e poi scegliere, le persone per somma di gradimento potenziale massimo.
Dopodichè si fanno sedere cercando di attivare il più possibile questo gradimento potenziale.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License