|
|
|
|
Strumenti |
19-11-2003, 18:58 | #101 |
Member
Iscritto dal: May 2003
Città: Torino
Messaggi: 63
|
Se mi date tempo fino a sabato (venerdì pomeriggio ho un esame di Teoria dei segnali quindi fino ad allora non molto tempo libero...) vedo di implementare l'algoritmo che mi è venuto in mente (anche grazie ai suggerimenti di a2000).
Intanto se modifico quello vecchio col quale ho generato la matrice 100x100 (in pratica tolgo la ricorsione per non avere limiti allo stack) penso di poter arrivare a 10000x10000 in pochi secondi. Il problema di questo programma è che accetta solo matrici con lati di lunghezza multipla di 5... Col programma brute force ho scoperto anche che per una matrice 5x5, partendo da qualunque punto si può arrivare in qualunque altro punto della matrice (ovviamente eccetto il punto di partenza). Ad esempio posso volere una matrice che cominci da (3,4) e finisca in (4,4) e so che esiste (so anche come è fatta). Non è niente di complicato, però è interessante!
__________________
AMD K6 450 MHz, Epox MVP3G2 FSB 100 MHz, 320 MB RAM, HDD IBM 7200 60 GB, VooDoo III (è vecchia ma per diablo II va ancora bene ) |
20-11-2003, 08:26 | #102 | |
Bannato
Iscritto dal: Jul 2000
Città: Malo (VI)
Messaggi: 994
|
Quote:
Versione python Codice:
color = ['red','orange','yellow','green','blue'] n = len(color) def arcobaleno( str ): result = '' for i in range(0,len(str) ): result += "[ccolor=" + color[i%n] + "]" + str[i] + "[/ccolor]" return result edit: avevo dimenticato la versione Haskell (3 righe ) (non testata ma dovrebbe andare) Codice:
color = ["red","orange","yellow","green","blue"] decor (col,char) = "[ccolor=" ++ col ++ "]" ++ [char] ++ "[/ccolor]" arcobaleno str = map decor $ zip (cycle color) str Per le cose serie dovrai aspettare un po' di piu' temo Ultima modifica di /\/\@®¢Ø : 20-11-2003 alle 18:42. |
|
20-11-2003, 08:54 | #103 |
Bannato
Iscritto dal: Jan 2001
Messaggi: 1976
|
è dura la vita dei commessi viaggiatori, eh /\/\@®¢Ø ....
|
20-11-2003, 09:03 | #104 |
Bannato
Iscritto dal: Jan 2001
Messaggi: 1976
|
per esempio:
" Un problema che da lungo tempo ha attratto i matematici è il problema del commesso viaggiatore. Un commesso viaggiatore deve visitare un certo numero di città; conosce la lunghezza ( o il tempo o il costo, a seconda dei casi) dello spostamento necessario per recarsi da una città all’altra: vuole determinare il percorso più breve ( o più veloce o più economico) che gli permetta di partire da casa sua e di farvi ritorno dopo aver visitato ogni città una sola volta. Come può fare? " http://digilander.libero.it/dimauro/...ames/commesso/ |
20-11-2003, 10:33 | #105 |
Member
Iscritto dal: Oct 2003
Messaggi: 109
|
Il problema del commesso viaggiatore.
Tradotto nel linguaggio della teoria dei grafi, il problema consiste nel trovare un ciclo di Hamilton di peso minimo in un grafo pesato completo, cioè si vuole trovare un ciclo ottimale. Non esiste nessun algoritmo efficace per risolvere tale problema! Si può comunque trovare una soluzione raginevole. Esiste un metodo trovato da Lin, Held e Karp ma non è straordinario. Volevo solo precisare che è tosto. Più semplice è il problema del postino cinese. ( Algoritmo di Fleury). Ciao! |
20-11-2003, 10:42 | #106 |
Senior Member
Iscritto dal: Jun 2002
Città: Firenze
Messaggi: 630
|
Parole, parole, parole... ma finora non ho visto nessun codice completo!
Fateli vedere questi algoritmi !!!
__________________
---> Lombardp CSS Certified Expert (Master Level) at Experts-Exchange Proud user of LITHIUM forum : CPU technology Webmaster of SEVEN-SEGMENTS : Elettronica per modellismo |
20-11-2003, 10:49 | #107 |
Bannato
Iscritto dal: Jan 2001
Messaggi: 1976
|
ah sì, lo conosco:
Un postino cinese deve spedire 100 lettere a tutti i suoi amici postini in diverse città della Cina. decide di comprare cento francobolli di costo diverso per ognuna delle destinazioni. Va dal tabaccaio il quale, per dargli i francobolli più appropriati, gli pone le seguenti domande: 1) in che tipo di zona deve andare ogni singola lettera (rurale, marina, montuosa ecc.) 2) l'età del destinatario 3) il suo stato civile 4) gli hobby del destinatario 5) il colore della busta 6) .... mentre sta per porgli la sesta domanda entra un'altro cliente che porta una tazza del cesso sulle spalle e dice: " ieri ti ho fatto vedere il buco del culo, questa è la tazza del cesso, ora sto' rotolo di carta igienica me lo vuoi dare o no ???? " |
20-11-2003, 11:01 | #108 | |
Bannato
Iscritto dal: Jan 2001
Messaggi: 1976
|
Quote:
Codice:
i = 1: j = 5 For k = 1 To iMax * jMax v(i, j) = 100 Call ConnMin(i, j, 0, hMin, vMin) If vMin > 8 Then Exit For i = i + Di(hMin): j = j + Dj(hMin) For h = 1 To 8 ih = i + Di(h): jh = j + Dj(h) v(ih, jh) = v(ih, jh) - 1 Next h Next k Sub ConnMin(i, j, n, hMin, vMin) vMin = v(i + Di(1), j + Dj(1)): hMin = 1 For h = 2 To 8 vx = v(i + Di(h), j + Dj(h)) If vx < vMin Then: vMin = vx: hMin = h Next h End Sub |
|
20-11-2003, 12:12 | #109 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53967
|
Io credo di aver risolto con un algoritmo Greedy...
Devo fare un po' di compattazione...lo posto stesera |
20-11-2003, 12:22 | #110 | |
Senior Member
Iscritto dal: Jun 2003
Città: Genova
Messaggi: 5676
|
Quote:
che è? fortran o vb? non i picchiare ciao |
|
20-11-2003, 12:42 | #111 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53967
|
Anzi lo posto ora:
Codice:
#include <stdio.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #define DIM 10 #define SPOST 8 int valido(int x, int y, int ris[]) { if(x >= 0 && y >= 0 && y < DIM && x < DIM) if(!ris[x*DIM+y]) return 1; return 0; } int eval(int x, int y, int ris[]) { if(!valido(x,y,ris)) return 9; return 0+((valido(x-2, y-2, ris))?1:0)+((valido(x+2, y-2, ris))?1:0) +((valido(x-2, y+2, ris))?1:0)+((valido(x+2, y+2, ris))?1:0) +((valido(x-3, y, ris))?1:0)+((valido(x+3, y, ris))?1:0) +((valido(x, y-3, ris))?1:0)+((valido(x, y+3, ris))?1:0); } void stampaL(char l[]) { for(int i=0; i<DIM; ++i) { for(int j=0; j<DIM; j++) printf("%c",l[i*DIM+j]); printf("\n"); } } int main(int argc, char *argv[]) { int min = 0, tx, ty, x = 0, y = 0, ris[DIM*DIM], i, j, tmp; int spostx[8] = {-3, 3, 0, 0 ,-2, 2,-2, 2}; int sposty[8] = { 0, 0,-3, 3 ,-2,-2, 2, 2}; char l[DIM*DIM]; memset(ris, 0, DIM*DIM*sizeof(int)); ris[x*DIM+y] = 1; for(i=1; i<DIM*DIM; ++i) { for(int h=0; h<DIM*DIM; ++h) if(ris[h] == 0) l[h] = '0'; else l[h] = 'X'; l[x*DIM+y] = 'A'; min = 9; for(j=0; j<8; ++j) { tmp = eval(x+spostx[j], y+sposty[j], ris); if(tmp < 9) l[(x+spostx[j])*DIM+y+sposty[j]] = '0' + tmp; if(tmp < min) { min = tmp; tx = x+spostx[j]; ty = y+sposty[j]; } } stampaL(l); x = tx; y = ty; ris[x*DIM+y] = i+1; printf("\n%d (%d,%d) min=%d\n",i+1, x, y, min); getchar(); if(min == 9) { printf("\nerrore"); break; } } for(i=0; i<DIM*DIM; ++i) { printf("%4d",ris[i]); if(!((i+1)%DIM)) printf("\n"); } getchar(); return 0; } |
20-11-2003, 12:43 | #112 | |
Bannato
Iscritto dal: Jan 2001
Messaggi: 1976
|
Quote:
|
|
20-11-2003, 12:54 | #113 |
Bannato
Iscritto dal: Jan 2001
Messaggi: 1976
|
.
Ultima modifica di a2000 : 20-11-2003 alle 12:56. |
20-11-2003, 12:57 | #114 | |
Senior Member
Iscritto dal: Jun 2002
Città: Firenze
Messaggi: 630
|
Quote:
Dato che non conosco il linguaggio, ti chiedo solo una spiegazione "sintattica": EXIT FOR serve ad abortire il ciclo corrente, oppure tutto il FOR?
__________________
---> Lombardp CSS Certified Expert (Master Level) at Experts-Exchange Proud user of LITHIUM forum : CPU technology Webmaster of SEVEN-SEGMENTS : Elettronica per modellismo |
|
20-11-2003, 13:30 | #115 |
Bannato
Iscritto dal: Jan 2001
Messaggi: 1976
|
il ciclo corrente. nel caso specifico il ciclo in k.
la matrice v(i, j) è la matrice dei gradi di connessione residui di ogni singola cella. è inizializzata a v(i, j) = 8 ad eccezione delle fasce di bordo. inoltre è orlata (con valore singolare = 100 ) in modo da evitare il ceck di validità degli spostamenti. 1) ad ogni passo si effettua lo spostamento (consentito) sulla cella con il minor valore di connessione 2) si aggiorna il valore di connessione di tutte le celle connesse alla cella prescelta con un artificio (valori negativi) la stessa matrice viene utilizzata per tenere memoria degli spostamenti (da 1 a 8). per ogni elemento di v(i,j) potrebbe bastere mezzo byte (4 bit). la subroutine di ricerca del minimo ConnMin diventa ricursiva a n passi se si vuole discriminare tra due valori di minimo uguali in base ai passi successivi. Ultima modifica di a2000 : 20-11-2003 alle 13:34. |
20-11-2003, 13:47 | #116 | |
Bannato
Iscritto dal: Jan 2001
Messaggi: 1976
|
Quote:
beh,sefaiachicel'hapiùcorto: Codice:
Function f_arcobaleno(a$) As String c$ = "red orangeyellowgreen blue " For i% = 1 To Len(a$) f_arcobaleno = f_arcobaleno + "[ccolor=" + Trim$(Mid$(c$, (i% Mod 5) * 6 + 1, 6)) + "]" + Mid$(a$, i%, 1) + "[/ccolor]" Next i% End Function Ultima modifica di a2000 : 21-11-2003 alle 10:08. |
|
20-11-2003, 14:02 | #117 | |||
Senior Member
Iscritto dal: Jun 2002
Città: Firenze
Messaggi: 630
|
Ti dico cosa ero arrivato a dedurre dal codice:
Quote:
Quindi non ero arrivato a definire che era diversa nelle fasce di bordo (ci sono meno collegamenti), ma ero arrivato alla conclusione dell'orlatura per evitare il "boundary checking". Quote:
Quote:
__________________
---> Lombardp CSS Certified Expert (Master Level) at Experts-Exchange Proud user of LITHIUM forum : CPU technology Webmaster of SEVEN-SEGMENTS : Elettronica per modellismo |
|||
20-11-2003, 15:15 | #118 |
Senior Member
Iscritto dal: Jan 2000
Messaggi: 549
|
Che era il "traveling salesman" lo avevo capito da parecchio.
Solo che sono onesto e volevo comunque arrivare a una mia soluzione. Soluzione comunque basata sulle primissime indicazioni di a2000(mi sun' unest'). Devo ricredermi sulla possibilità di non ricorrere a strutture(nodo),per un codice + compatto) Si costrusce la matrice mxn di nodi (inizializzati allo stato non visitato). Si fa una funzione "visita"che ha come parametro il reference al nodo(per fare +veloce) e che restituisce il nodo successivo secondo il criterio di ottimizzazione. ...almeno credo |
20-11-2003, 15:19 | #119 |
Senior Member
Iscritto dal: Jan 2000
Messaggi: 549
|
Sono tutti algoritmi di "Network traversal "
Quello + famoso (e + difficile) è quello che deve trovare il percorso minimimo per visitare tutte le "città" una sola volta tornando a quella di partenza. (scannatevi ) |
20-11-2003, 15:33 | #120 |
Senior Member
Iscritto dal: Jul 1999
Città: Torino
Messaggi: 2221
|
coinci è davvero impressionante la velocità del tuo algoritmo! la 10 X 10 viene praticamente restituita istantaneamente...l'ho fatto girare su un vecchio server Unix via telnet...
|
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 23:21.