piccola sfida

[Sephiroth83]

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!

[/\/\@®¢Ø]

Originariamente inviato da a2000
no quella è in queste 15.

Function f_arcobaleno(a$) As String
 
 Dim c$(1 To 5)
 c$(1) = "red"
 c$(2) = "orange"
 c$(3) = "yellow"
 c$(4) = "green"
 c$(5) = "blue"
 
 b$ = ""
 ic% = 2
 For i% = 1 To Len(a$)
  a1$ = Mid$(a$, i%, 1)
   ic% = 1 + i% Mod 5
   b$ = b$ + "[ccolor=" + c$(ic%) + "]" + Mid$(a$, i%, 1) + "[/ccolor]"
 Next i%
 
 f_arcobaleno = b$


End Function

Purtroppo per ora non ho tempo da dedicare al gioco, pero' posso offrirti la mia variante della funzione arcobaleno
Versione python

 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

(in python sono alle prime armi, quindi prendetela con le pinze )

edit: avevo dimenticato la versione Haskell (3 righe )
(non testata ma dovrebbe andare)

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

[a2000]

è dura la vita dei commessi viaggiatori, eh /\/\@®¢Ø ....

[a2000]

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/

[Strat]

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!

[lombardp]

Parole, parole, parole... ma finora non ho visto nessun codice completo!

Fateli vedere questi algoritmi !!!

[a2000]

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 ???? "

[a2000]

Originariamente inviato da lombardp
Parole, parole, parole... ma finora non ho visto nessun codice completo!

Fateli vedere questi algoritmi !!!

che impazienza, to' per ora solo il bulk:

 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

[cionci]

Io credo di aver risolto con un algoritmo Greedy...
Devo fare un po' di compattazione...lo posto stesera

[NA01]

Originariamente inviato da a2000
che impazienza, to' per ora solo il bulk:

 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

che è?
fortran o vb?

non i picchiare

ciao

[cionci]

Anzi lo posto ora:

#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;
}

Questo stampa tutte i passi quindi posso ridurre ancora le righe...

[a2000]

Originariamente inviato da NA01
che è?
fortran o vb?

uno e l'altro.

[a2000]

.

[lombardp]

Originariamente inviato da a2000
che impazienza, to' per ora solo il bulk:

Molte grazie! Ora devo cercare di capirlo bene.

Dato che non conosco il linguaggio, ti chiedo solo una spiegazione "sintattica": EXIT FOR serve ad abortire il ciclo corrente, oppure tutto il FOR?

[a2000]

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.

[a2000]

Originariamente inviato da /\/\@®¢Ø
Purtroppo per ora non ho tempo da dedicare al gioco, pero' posso offrirti la mia variante della funzione arcobaleno
Versione python

 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

(in python sono alle prime armi, quindi prendetela con le pinze )

Per le cose serie dovrai aspettare un po' di piu' temo

beh,sefaiachicel'hapiùcorto:

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

[lombardp]

Ti dico cosa ero arrivato a dedurre dal codice:

Originariamente inviato da a2000
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.

Non ero arrivato a capire che V era la matrice degli "spostamenti residui", per ora avevo concluso che era una matrice di "pesi" che erano decrementati sulle caselle adiacenti (nel senso degli spostamenti) a quella corrente.

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".

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

Ok, si capiva bene dal codice.

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).

Questo non solo non lo avevo minimamente immaginato, ma anche adesso non riesco a vederlo... è in un'altra porzione di codice?

[verloc]

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

[verloc]

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 )

[cn73]

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...