Flying memes

Archive for the ‘Algoritmi’ Category

Un nuovo tile engine per google map

Sunday, April 26th, 2009

Conoscevo Google Map e le sue fantastiche API ma solo di recente ho deciso di spulciare un pò più a fondo la sua documentazione e ho scoperto la notevole possibilità di modificare i tiles visualizzati da Google Map trasformando questo strumento da strettamente cartografico a ZUI (zoomable user interface).

Come funziona? Bisogna istanziare un nuovo oggetto della classe GTileLayer e specificarne all’interno una funzione che, ricevuti due parametri (un oggetto GPoint e un numero indicativo del livello di zoom) sappia ritornarne l’immagine appropriata.

Nel prossimo articolo andrò un pò più nel dettaglio, per il momento vi lascio a questa proof-of-concept che potrebbe trasformarsi, a breve, nella gallery ufficiale del sito.

Midpoint displacement algorithm

Sunday, March 22nd, 2009

Grazie all’appuntamento settimanale con i Ruby Quiz oggi sono venuto a conoscenza del Midpoint displacement algorithm, utilissimo per la generazione di una spezzata che simuli la silhouette di una catena montuosa.

Questo algoritmo basa la sua operatività essenzialmente su di un array contenente le altezze dei punti che compongono la spezzata. Tale array all’inizio presenterà solamente due valori (capo e coda dell’intero profilo che vogliamo creare), entrambi settati a 0.

(more…)

Q-learning con processing.org

Sunday, January 18th, 2009

Il reinforcement learning (o apprendimento con rinforzo) è una approcio che appartiene alla categoria dei sistemi intelligenti e che si applica a tutte quelle casistiche nelle quali un agente deve esplorare ed interagire con l’ambiente circostante.

(more…)

Uno stormo con processing.org

Thursday, January 1st, 2009

Esiste molta letteratura sul problema di simulazione di uno stormo (detto anche Flocking), queste sono le tre regole principali a cui ogni partecipante allo stormo deve obbedire:

(more…)

Ruby-dlx, le otto regine e le colonne secondarie

Tuesday, December 16th, 2008

Eravamo rimasti al seguente quesito: “Come implementiamo l’insieme di costrizioni che abbiamo evinto in modo da risolvere il problema delle 8 regine con i Dancing Links ?”

(more…)

Le otto regine e ruby-dlx

Monday, December 8th, 2008

Il problema delle otto regine rientra a far parte di quell’insieme di sfide che da molti anni interessano ed incuriosiscono matematici ed appassionati (questo problema è stato proposto nel 1848).

(more…)

Risolvere i Sudoku in Ruby con i Dancing Links: ruby-dlx

Tuesday, December 2nd, 2008

Ho appena effettuato il commit della prima release funzionante di ruby-dlx. Ruby dlx è una piccola libreria che implementa in Ruby l’algoritmo dei Dancing Links descritto nel post di settimana scorsa.

(more…)

Knuth e i dancing links

Sunday, November 23rd, 2008

Nel post precedente cercando di trovare un algoritmo interessante per la generazione di Sudoku mi sono imbattuto nei Dancing Links.

L’algoritmo DLX è stato inventato da Donald Knuth (il pdf originale è disponibile gratuitamente) ed è essenzialmente un’implementazione performante di un algoritmo di backtracking (Algoritmo X).

(more…)

Un algoritmo per creare Sudoku?

Friday, November 14th, 2008

Da un paio di settimane stò studiando un pò il mondo che contorna questi simpatici puzzles con l’obiettivo di creare un generatore di Sudoku in Ruby.

La prima cosa che ho scoperto è che non è stato ancora dimostrato il numero minimo di cifre che è necessario esporre (cioè visualizzare ‘completate’ all’inizio del puzzle) per garantire al Sudoku una soluzione univoca; al momento sono stati trovati Sudoku validi con 17 cifre esposte.

Ma come si determina quando un Sudoku ha una soluzione univoca?

(more…)