Général
Générateur et solveur de labyrinthes (dans Php, le 02/01/2010 à 19h 17min)
Je vais vous présenter ici le script que j'ai écrit dans le cadre du concours PHP organisé sur le Site du Zér0. L'énoncé ainsi que le topic du concours se trouve ici : sujet du concours.
Pour la petite histoire, j'ai fini 1er ex-æquo de ce concours. :)
Le compte-rendu est disponible ici : résultat sur le SdZ.
Exemple de rendu
La suite de l'article explique le principe de génération, et montre le script en action.
Je vais vous présenter ici le script que j'ai écrit dans le cadre du concours PHP organisé sur le Site du Zér0. L'énoncé ainsi que le topic du concours se trouve ici : sujet du concours.
Pour la petite histoire, j'ai fini 1er ex-æquo de ce concours. :)
Le compte-rendu est disponible ici : résultat sur le SdZ.
Exemple de rendu
La suite de l'article explique le principe de génération, et montre le script en action.
Réduire le bruit numérique sur les photos ? (dans C, le 30/12/2009 à 13h 21min)
Pour commencer, un petit rappel :
La suite de cet article présente une idée que j'ai eu pour réduire le bruit, ainsi que l'écriture du programme correspondant en C. Les résultats sont relativement probants.
Pour commencer, un petit rappel :
Citation : Linternaute
Le bruit est un terme issu du domaine de l'acoustique et désigne un signal parasite. Que ce soit pour le son ou pour l'image, le principe est identique : sur tout signal de base vient s'adjoindre un ensemble d'informations parasites aléatoires.
Si le niveau du signal est suffisant, la proportion de bruit dans le signal utile (le fameux rapport signal/bruit) reste insignifiante. Par contre, si le niveau de bruit prend le pied sur l'information principale, le bruit sera présent.
On l'aura compris, le bruit est donc quelque chose dont on se passerai bien.Si le niveau du signal est suffisant, la proportion de bruit dans le signal utile (le fameux rapport signal/bruit) reste insignifiante. Par contre, si le niveau de bruit prend le pied sur l'information principale, le bruit sera présent.
La suite de cet article présente une idée que j'ai eu pour réduire le bruit, ainsi que l'écriture du programme correspondant en C. Les résultats sont relativement probants.
Résolveur de sudoku en PHP (dans Php, le 29/12/2009 à 22h 56min)
Petit retour dans le temps avec ce script retrouvé au fond de mon disque dur, et datant de Mars 2006. C'est mes premiers pas dans l'algorithmique, et dans l'utilisation du brute-force pour résoudre un problème : on test toutes les possibilités, jusqu'à ce qu'on trouve la solution.
Bien sûr, on respecte tout le temps les règles du sudoku, ce qui nous permet de largement limiter les essais. Cependant, il arrive souvent que l'on se retrouve dans une configuration où l'on ne peut plus rajouter de chiffre sans violer une des règles; dans ce cas, le sudoku est bloqué, il faut alors revenir en arrière et essayer une autre possibilité. On peut donc assimiler la recherche de la solution au parcours d'un arbre de possibilités en profondeur.
Avec le recul, je me dis qu'il faudrait reprendre au moins la moitié de ce script, qui me semble maintenant bien compliqué et bien mal pensé (surtout au niveau de la représentation des données et de l'organisation de l'algorithme; je pense qu'il y a beaucoup de calculs redondants), mais je n'ai pas forcément le temps ni l'envie.
Vous pourrez trouver ici :
Voilà, vous pourrez maintenant épater vos amis en résolvant n'importe quel sudoku !
Petit retour dans le temps avec ce script retrouvé au fond de mon disque dur, et datant de Mars 2006. C'est mes premiers pas dans l'algorithmique, et dans l'utilisation du brute-force pour résoudre un problème : on test toutes les possibilités, jusqu'à ce qu'on trouve la solution.
Bien sûr, on respecte tout le temps les règles du sudoku, ce qui nous permet de largement limiter les essais. Cependant, il arrive souvent que l'on se retrouve dans une configuration où l'on ne peut plus rajouter de chiffre sans violer une des règles; dans ce cas, le sudoku est bloqué, il faut alors revenir en arrière et essayer une autre possibilité. On peut donc assimiler la recherche de la solution au parcours d'un arbre de possibilités en profondeur.
Avec le recul, je me dis qu'il faudrait reprendre au moins la moitié de ce script, qui me semble maintenant bien compliqué et bien mal pensé (surtout au niveau de la représentation des données et de l'organisation de l'algorithme; je pense qu'il y a beaucoup de calculs redondants), mais je n'ai pas forcément le temps ni l'envie.
Vous pourrez trouver ici :
- la source php
- une démonstration du script : la grille de test proposée par défaut fait planter le script chez Free, je pense qu'il bouffe trop de mémoire. Quand je dis que ce n'est pas optimisé...
Voilà, vous pourrez maintenant épater vos amis en résolvant n'importe quel sudoku !
Pathfinding en PHP (dans Php, le 23/12/2009 à 13h 06min, édité 2 fois, dernier le 02/01/2010 à 19h 18min)
Le pathfinding, ou recherche de chemin en français, consiste grossièrement à trouver un chemin entre un point de départ et un point d'arrivé, respectant certaines contraintes (le plus court possible, par exemple).
C'est un problème qui peut se rapprocher à de la recherche opérationnelle :
Je vous présente dans la suite de l'article une implémentation en Php de l'algorithme A*
Le pathfinding, ou recherche de chemin en français, consiste grossièrement à trouver un chemin entre un point de départ et un point d'arrivé, respectant certaines contraintes (le plus court possible, par exemple).
C'est un problème qui peut se rapprocher à de la recherche opérationnelle :
Citation : Wikipédia
A la base, un problème de pathfinding peut se ramèner à un problème de recherche du meilleur chemin entre deux noeuds dans un graphe. Il existe un ensemble d'algorithmes classiques pour résoudre ce type de problème. Toutefois, le pathfinding devient un problème complexe lorsque l'on cherche à prendre en compte diverses contraintes additionnelles (exécution en temps réel, présence d'incertitudes, contrainte de ressources, environnement évolutif, etc).
Je vous présente dans la suite de l'article une implémentation en Php de l'algorithme A*
Là haut, dans les Nuages (dans Paysage, le 22/07/2008 à 01h 41min)
De retour d'une rando, vers Pralognan-la-Vanoise - un coin relativement paumé - dont vous avez pu voir la première photo dans l'article précédent...
Je campais, j'ai bien cru que j'allais foutre ... le camp. Un temps immonde. Du froid, de la pluie, des nuages épais comme un Big Mac...
Le seul avantage, c'est que ça donnait de jolis effets sur la montagne. Et j'ai mangé une tartiflette, le 14 Juillet 2008. L'année sans été, vous vous souvenez ?
Là haut, dans la montagne
De retour d'une rando, vers Pralognan-la-Vanoise - un coin relativement paumé - dont vous avez pu voir la première photo dans l'article précédent...
Je campais, j'ai bien cru que j'allais foutre ... le camp. Un temps immonde. Du froid, de la pluie, des nuages épais comme un Big Mac...
Le seul avantage, c'est que ça donnait de jolis effets sur la montagne. Et j'ai mangé une tartiflette, le 14 Juillet 2008. L'année sans été, vous vous souvenez ?
Là haut, dans la montagne