Newsgroup: it.comp.ia
Titolo: Algoritmo

Ciao a tutti.
Spero che qualcuno mi possa aiutare. Devo scrivere un programma 
per creare i calendari di un campionato. Mi potete mica dare 
qualche dritta per un algoritmo che creai gli accoppiamenti di 
un girone all'italiana (andata e ritorno).
Ringrazio anticipatamente
Kenshirov
-- 
Inviato da Virgilio 
http://newsgroup.virgilio.it
Filtra gli antipatici, segnala le risposte, segue i thread, e lo fa da web

 Kenshirov
Così come lo hai esposto non ha nulla a che vedere con l'AI; se non ci
sono vincoli sugli accoppiamenti, la soluzione è ovviamente un generatore
random:
inizializza_generatore_random()
for each giornata {
   while (ci sono squadre libere) {
       squadra_A = random(lunghezza_lista_squadre_libere)
       squadra_B = random(lunghezza_lista_squadre_libere)
       partita_andata[giornata][prossima_partita] = { A,B }
       partita_ritorno[giornata][prossima_partita] = { B,A }
       prossima_partita = prossima_partita + 1
       togli squadra_A da lista
       togli squadra_B da lista
   }
   libera tutte le squadre
   azzera prossima_partita
}
Oppure ho completamente frainteso la tua richiesta?
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 ...
Hai ragione, non c'è bisogno di un algoritmo "intelligente" per farlo ma il
tuo non funziona comunque ;)
Infatti non garantisce che giornate diverse abbiano partite diverse. 
ciao,
Federico
-- 
Federico Colla 
http://narcisiss.bitchx.it

 sono vincoli sugli accoppiamenti, 
Hai Ragione.
Il problema e' che piu' squadre giocano sullo stesso campo, che 
quindi non e' sempre disponibile. Inoltre sugli stessi campi si 
giocano campionati di diverse categorie. Quindi devo incastrare 
orari, campionati e campi a disposizione.
Se io creo i vari campionati con accoppiamenti random, 
controllando il vincolo di disponibilita' del campo, e 
successivamente controllo i vincoli di relazione con gli altri 
campionati pensate che possa funzionare?
Grazie


 Kenshirov
ora che hai esposto i vincoli è già diverso...
tanto vale usare un "brute force" e dovresti cavartela in tempo lineare
comunque quali sono i limiti? quanti cioè i campionati e, indicativamente,
quante squadre hanno i campi più affollati?


 
Ho 10 campionati. 12 squadre a campionato. Potenzialmente su 
ogni campo ci devono giocare 6 - 8 squadre. Ogni giornata di 
campionato e' divisa in sabato e domenica. Quando si gioca e' 
indifferente. Si puo' giocare anche la sera, ma non tutti i 
campi hanno l'illuminazione. Ovviamente se una squadra gioca in 
casa al turno successivo (o al massimo fra due) deve giocare in 
trasferta.
Con "brute force" significa che dovrei costriurmi l'albero con 
tutte le possibili combinazioni e controllare quale e' quallo 
che rispetta i vincoli?



Great!
stottlemy...@duskmail.com

 che rispetta i vincoli?
Penso che intendesse cosi`.
Comunque usare un algoritmo di forza bruta in questo caso puo` non dare 
una soluzione in tempi ragionevoli.
Io mi trovo bene ad usare Constraint Programming, che parte dalle idee 
di Arc-Consistenza sviluppate in IA.
Il problema che proponi ha qualche attinenza al problema del Social 
Golfer, di cui sono state risolte acune istanze proprio con Constraint 
Programming:
http://4c.ucc.ie/~tw/csplib/prob/prob010/
Ciao,
Marco