Newsgroup: it.hobby.enigmi
Titolo: Vigilanza

          o--o--o
          |     |
    o--o--o     o
    |     |     |
o--o--o--o--o--o--o
|  |     |  |     |
o  o--o--o--o--o--o
|  |  |     |     |
o--o--o--o  o     o
|  |  |  |  |     |
o  o--o--o  o--o--o
|  |     |  |
o--o--o--o--o
Le linee rappresentano le strade della nostra citta', mentre i 39 
cerchietti sono i punti strategici per sistemarci un eventuale vigile.
Ciascun vigile puo' vedere fino a 2 unita' avanti in qualunque direzione.
(Intendo i due tratti di strada che vanno dalla propria postazione fino 
alla prossima piu' il tratto seguente) In pratica un vigile in X ha il 
seguente campo di vista:
        o
        |
        o
        |
  o--o--X--o--o
        |
        o
        |
        o
Naturalmente negli spazi bianchi ci sono palazzi che impediscono la visuale.
Ora il sindaco vuole tenere tutta la citta' sotto controllo, ma il bilancio 
comunale gli impone di impiegare il minor numero possibile di vigili.
Quanti ne occorrono ?
dario

 cerchietti sono i punti strategici per sistemarci un eventuale vigile.
.
Inizio io, ma l'ho fatto a mano in poco tempo...sara' migliorato
sicuramente e sensibilmente...
;-)))
.
.
.
.
.
.
.
.
.
Ne utilizzo 13 al momento.
         o--o--X
         |     |
   X--o--o     o
   |     |     |
X--o--o--X--o--o--X
|  |     |  |     |
o  X--o--o--X--o--o
|  |  |     |     |
o--X--o--X  o     o
|  |  |  |  |     |
o  o--X--o  o--o--X
|  |     |  |
X--o--o--o--X
CiaO,
Massimo


GaS

GaS wrote:
         o--o--X
         |     |
   o--o--X     o
   |     |     |
X--o--oyyo--o--o--X
|  |     |  |     |
o  o--o--o--X--o--o
|  |  |     |     |
o--o--o--X  o     o
|  |  |  |  |     |
o  X--O--o  X--o--o
|  |     |  |
X--o--o--X--o
Forse non mi sono spiegato bene.
Sono le strade che vanno tenute sotto controllo e non le postazioni.
Ad es il tratto yy e' fuori portata.
ciao

 dario
Ho trovato una sol. da 9, ma uno o due forse si riescono a eliminare:
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
         o--o--X
         |     |
   X--o--o     o
   |     |     |
o--o--o--X--o--o--o
|  |     |  |     |
o  o--o--o--o--o--X
|  |  |     |     |
X--X--o--o  o     o 
|  |  |  |  |     |
o  o--X--o  X--o--o
|  |     |  |
o--o--o--X--o
Ciao
Andrea

 oyyo--o--X--o
Probabilmente per questo problema non sono riuscito a farmi capire.
Nel tuo schema ci sono diversi tratti di strada incostuditi yy
ciao dario

 ciao dario
.
.
.So' che la mia soluzione non e' la migliore, ma vorrei sapere
se e' corretta relativamente al vilcolo chiesto.
CiaO,
Massimo

 se e' corretta relativamente al vilcolo chiesto.
Si, tutti i tratti sono sorvegliati.
Non conosco la sol. ci devo lavorare su.
ciao

 ciao
Ci riprovo migliorando di poco Massimo M.
S
P
O
I
L
E
R
!
12 vigili
          o--o--X
          |     |
    X--o--o     o
    |     |     |
 X--o--o--X--o--o--X
 |  |     |  |     |
 o  o--X--o--X--o--o
 |  |  |     |     |
 o--X--o--o  o     o
 |  |  |  |  |     |
 o  o--o--X  o--o--X
 |  |     |  |
 X--o--o--o--X
GaS

 sicuramente e sensibilmente...
.
.
.Eccomi a 12 vigili....ma forse si e' gia' fatto meglio...
;-))
.
.
.
.
.
.
.
.
         o--o--X
         |     |
   X--o--X     o
   |     |     |
X--o--o--o--X--o--o
|  |     |  |     |
o  o--X--o--o--o--X
|  |  |     |     |
o--X--o--o  o     o
|  |  |  |  |     |
o  o--X--o  X--o--o
|  |     |  |
X--o--o--X--o
CiaO,
Massimo

 Ciascun vigile puo' vedere fino a 2 unita' avanti in qualunque direzione.
.
.
.Ho fatto una valutazione del peso per ogni punto strategico 
utilizzando lo schema di seguito...:
         4--2--4
         |     |
   4--2--5     2
   |     |     |
4--6--4--7--6--5--4
|  |     |  |     |
3  6--5--6--7--3--5
|  |  |     |     |
6--7--5--4  4     3
|  |  |  |  |     |
3  5--4--4  5--2--4
|  |     |  |
4--5--4--5--4
Si nota che il totale del peso di tutti i punti strategici e' 172 con
una media per ogni punto (sono 39) di 4,41.
In totale ci sono 51 pezzi di strada che quindi possono essere coperti
da i punti strategici che abbiamo in media con 11,56 posizionamenti.
Non c'e' una dimostrazione matematica, ma mi sembra un buon motivo
per pensare che dodici sia il minimo...
;-)
In altro caso sarebbe necessario analizzare ben 2^39 schemi che
mi sembrano un po' tanti per le forze che ho io a disposizione...
ma se ci fosse Dani inizierebbe a potare, potare, potare, fino a
trovare tutti gli schemi in meno di 3 sec...
CiaO,
Massimo

 In altro caso sarebbe necessario analizzare ben 2^39 schemi
che mi sembrano un po' tanti per le forze che ho io a disposizione... ma se
ci fosse Dani inizierebbe a potare, potare, potare, fino a trovare tutti
gli schemi in meno di 3 sec...
.
.
2^39=~0.5x10^12 non e' un numero
enorme. Ma per vedere se esiste una soluzione da 11 basta muovere 11 vigili
(uguali tra loro) sulle 39 postazioni, che fa un numero molto piu' piccolo.
Non eri tu che muovevi molto velocemente n dame sulla scacchiera? (11
nexting concatenati?)
.
.
Ciao!!!
Livio
--------------------------------
Inviato via 
http://usenet.iol.it
 

La soluzione ottimale minima usa 11 agenti.
Trovata con lp_solve sotto linux in 1 centesimo di secondo (!) dopo che 
ho codificato il problema come un problema di programmazione lineare 
intera con 39 variabili e un vincolo per ogni tratto di strada.
Una soluzione e' sotto lo spoiler,
ciao
G.Resta.
S
P
O
I
L
E
R
Facendo riferimento allo schema di Uri, numero le righe da quella piu' 
in alto (1) con 3 postazioni a quella piu' in basso (7) con 5 postazioni.
In ogni riga numero le postazioni da sinistra a destra.
Allora una soluzione ottimale e':
1a riga: 3a postaz.
2a riga: 3a postaz.
3a riga: 2a e 5a postaz.
4a riga: 3a e 7a postaz.
5a riga: 1a e 4a postaz.
6a riga: 2a e 5a postaz.
7a riga: 3a postaz.
s.e.e.o.
Ciao!
G.

 La soluzione ottimale minima usa 11 agenti.
.
.
.Cakkio....mi sembrava un problema tosto e tu lo hai risolto
in solo 1 cent di sec...?
Cmq per puro esercizio l'ho disegnato nella classica forma
rappresentata da Dario...:
         o--o--X
         |     |
   o--o--X     o
   |     |     |
o--X--o--o--X--o--o
|  |     |  |     |
o  o--X--o--o--o--X
|  |  |     |     |
X--o--o--X  o     o
|  |  |  |  |     |
o  X--o--o  X--o--o
|  |     |  |
o--o--X--o--o
11 vigili...
Come hai potuto stabile che e' il minimo e quante soluzioni
ci sono ?
CiaO,
Massimo

 ci sono ?
Mi associo negli elogi e nella curiosita' del metodo.
Ciao!!!
Livio

>
Mi associo ai complimenti.
dario


Scusate, ma i complimenti non li merito.
Spiego un po' piu' in dettaglio con degli esempi. Mi scuso se diro anche
cose ovvie.
Se cerco di determinare dei numeri reali non negativi x1, x2, x3
tali che Minimizzino la funzione lineare 4*x1+17*x2+2*x3
e siano soggetti ai vincoli:
3*x1+2*x2+5*x3 >= 100
x1 + x2 + 3*x3 >= 40
x1 + x3 >= 30
allora sto risolvendo un problema di programmazione
lineare. Un problema di programmazione lineare
e' (grosso modo) definito da una serie di
equazioni e disequazioni lineari e da una funzione obiettivo
lineare da massimizzare o minimizzare.
I problemi di questo tipo sono ben noti e sono risolvibili facilmente e
velocemente anche per problemi con migliaia e migliaia di incognite e
vincoli.
Se invece le variabili x1,x2,x3 devono assumere SOLO valori interi,
il problema diventa (in generale) enormemente piu' difficile,
ma per problemi di dimensione limitata (o con struttura particolare)
puo' ancora essere risolto in tempi ragionevoli.
In questo caso si parla di programmazione lineare INTERA.
Uno strumento gratis per risolvere (o tentare) entrambi i problemi
si chiama lp_solve e gira sotto linux, ma siccome anche il sorgente
e' disponibile immagino si possa compilare anche per win o dos o
si possa trovare gia' compilato (non ho cercato, perche' di solito
io programmo sotto linux). Inoltre, data la diffusione di questo tipo di
problemi esisteranno anche altri programmi per risolverli.
Veniamo ora al problema di Uri.
Come ho impostato il problema come problema di programmazione
lineare intera ? Molto semplice.
Ho introdotto 39 (!) variabili intere x1 .. x39, una per ogni 
postazione. Se la variabile relativa ad una postazione vale 0
vuol dire che non c'e' nessun agente, se vale 1 vuol dire
che c'e' un agente. Quindi il vincolo lineare da
minimizzare e' la somma delle 39 variabili.
Per quel che riguarda i vincoli, ne abbiamo 1 per ogni tratto
di strada (alcuni tratti di strada in realta' producono lo
stesso vincolo):
se un tratto di strada puo' essere "visto" dalle postazioni, ad es.,
3, 7 e 11, allora io voglio che ALMENO una di queste postazioni sia
coperta da un agente, ovvero che almeno una delle variabili x3,x7,x11
sia maggiore di 0. Quindi impongo x3+x7+x11 >= 1.
Tutto qua! Non e' necessario imporre vincoli ulteriori tipo
x(i) >=0 perche' le variabili vengono implicitamente assunte non
negative, e non e' necessario aggiungere vincoli del tipo x(i) <=1
perche' per la natura di minimizzazione del problema
automaticamente una soluzione con x(i)> 1 verrebbe scartata.
Una volta fatto questo ho incrociato le dita e ho dato in pasto
il problema a lp_solve che ha trovato velocemente una soluzione ottimale
di costo minimo 11, cosi' velocemente da farmi supporre che per qualche
motivo strutturale il problema fosse piuttosto facile.
Questa non e' una dimostrazione formale che 11 sia il minimo,
ma io mi fido ! Non ricordo esattamente il metodo utilizzato da lp_solve
ma dovrebbe essere un branch-and-bound che usa la versione lineare
non-intera per avere informazioni su upper e lower bound all'ottimo.
Ciao,
giovanni resta

>ci sono ?
Come ho determinato il minimo lo spiego piu' in dettaglio in un altro 
messaggio.
Per quel che riguarda il numero di soluzioni, l'approccio che ho
usato non permette di determinarle. (E sinceramente al momento non
penso di scrivere un programma ad-hoc per farlo....)
Ciao,
G.


Il mio prode e instancabile PC afferma:
- Non ci sono soluzioni con meno di 11 vigili
- Le soluzioni con 11 vigili sono 2
- Le soluzioni con 12 vigili sono 260
La seconda soluzione é molto silile a quella di Massimo 
         o--o--X
         |     |
   o--o--X     o
   |     |     |
o--X--o--o--X--o--o
|  |     |  |     |
o  o--X--o--o--o--X
|  |  |     |     |
X--X--o--o  o     o
|  |  |  |  |     |
o  o--o--X  X--o--o
|  |     |  |
o--o--X--o--o
Come potete vedere cambia solo posizione nella seconda e terza riga
dal basso.
Ciao, Damiano