# data[].attributes.attachment_link.readable_text
Le jeu de la vie est un automate cellulaire imaginé par John Horton Conway en 1970 et qui est probablement le plus connu de tous les automates cellulaires. Malgré des règles très simples, le jeu de la vie est Turing-complet.

Le jeu de la vie est un jeu de simulation au sens mathématique plutôt que ludique. Bien que n'étant pas décrit par la théorie des jeux, certains le décrivent comme un " jeu à zéro joueur ".

Le jeu de la vie est un " jeu à zéro joueur ", puisqu'il ne nécessite pas l'intervention du joueur lors de son déroulement. Il s'agit d'un automate cellulaire, un modèle où chaque état conduit mécaniquement à l'état suivant à partir de règles pré-établies.

Le jeu se déroule sur une grille à deux dimensions, théoriquement infinie (mais de longueur et de largeur finies et plus ou moins grandes dans la pratique), dont les cases - qu'on appelle des " cellules ", par analogie avec les cellules vivantes - peuvent prendre deux états distincts : " vivante " ou " morte ".

Une cellule possède huit voisins, qui sont les cellules adjacentes horizontalement, verticalement et diagonalement.

À chaque étape, l'évolution d'une cellule est entièrement déterminée par l'état de ses huit voisines de la façon suivante :

une cellule morte possédant exactement trois voisines vivantes devient vivante (elle naît) ;

une cellule vivante possédant deux ou trois voisines vivantes le reste, sinon elle meurt.

Ainsi, la configuration donne au tour suivant la configuration qui redonne ensuite la première.

On peut également formuler cette évolution ainsi :

si une cellule a exactement trois voisines vivantes, elle est vivante à l'étape suivante.

C'est le cas de la cellule verte dans la configuration de gauche ;

si une cellule a exactement deux voisines vivantes, elle reste dans son état actuel à l'étape suivante.

Dans le cas de la configuration de gauche, la cellule située entre les deux cellules vivantes reste morte à l'étape suivante ;

si une cellule a strictement moins de deux ou strictement plus de trois voisines vivantes, elle est morte à l'étape suivante.

C'est le cas de la cellule rouge dans la configuration de gauche.

L'état suivant d'une cellule est : (S = 3) OU (E = 1 ET S = 2).

Avec :

S : nombre actuel de cellules vivantes dans son voisinage (entier naturel compris entre 0 et 8 inclus) ;

E : état actuel de la cellule (entier naturel égal à 0 pour une cellule morte et égal à 1 pour une cellule vivante).

Afin de représenter le processus, les cellules vivantes sont généralement représentées colorées sur la grille, sur un fond de cellules mortes incolores.

Les schémas de cet article suivent les conventions de couleur suivantes :

bleu : cellules en cours de vie

vert : cellules naissantes

rouge : cellules mourantes

jaune : cellules ne vivant qu'une seule génération

Le jeu de la vie est inventé par John Horton Conway en 1970, alors qu'il est professeur de mathématiques à l' université de Cambridge, au Royaume-Uni.

J. H. Conway s'intéresse alors à un problème proposé par le mathématicien John Leech dans le domaine de la théorie des groupes et qui avait trait à l'empilement dense de sphères à 24 dimensions (connu comme le réseau de Leech). Il découvre quelques propriétés remarquables et publie les résultats de son étude en 1968. Conway est également intéressé par un problème présenté vers les années 1940 par un mathématicien renommé : John von Neumann.

Ce dernier a essayé de trouver une hypothétique machine qui pourrait s'auto-reproduire. Il y parvient en construisant un modèle mathématique aux règles complexes sur un repère cartésien. Conway essaye de simplifier les idées de von Neumann et finit par réussir. Couplant ses succès précédents avec les réseaux de Leech avec ses travaux sur les machines auto-réplicantes, il donne naissance au jeu de la vie.

Le premier contact entre le grand public et ces travaux se fait en 1970 à travers une publication dans Scientific American dans la rubrique de Martin Gardner : " Mathematical Games ".

Gardner écrit dans ses colonnes que " le jeu de la vie rendit Conway rapidement célèbre et il ouvrit aussi un nouveau champ de recherche mathématique, celui des automates cellulaires. En effet, les analogies du jeu de la vie avec le développement, le déclin et les altérations d'une colonie de micro-organismes, le rapprochent des jeux de simulation qui miment les processus de la vie réelle. "

D'après Gardner, Conway expérimenta plusieurs jeux de règles concernant la naissance, la mort et la survie d'une cellule avant d'en choisir un où la population des cellules n'explose pas (ce qui arrive souvent lorsque les conditions de naissances sont moins strictes) mais où des structures intéressantes apparaissent cependant facilement. À l'origine, John Conway y jouait à la main, en utilisant un plateau de go pour grille et des pierres de go pour matérialiser les cellules vivantes.

Plusieurs structures intéressantes furent découvertes, comme le " planeur ", un motif qui se décale en diagonale toutes les 4 générations, ou divers " canons " qui génèrent un flux sans fin de planeurs. Ces possibilités augmentent l'intérêt pour le jeu de la vie. De plus sa popularité augmente d'autant qu'il arrive à une époque où une nouvelle génération de mini-ordinateurs meilleur marché est commercialisée, ce qui permet de tester des structures pendant la nuit, lorsque personne d'autre ne les utilise.

Vers la fin des années 1980, la puissance des ordinateurs est suffisante pour permettre la création de programmes de recherche de structures automatiques efficaces ; couplés au développement massif d'Internet, ils conduisent à un renouveau dans la production de structures intéressantes.

Au bout du compte, le jeu de la vie attire plus l'intérêt du grand public sur les automates cellulaires (entre autres grâce à divers économiseurs d'écran) que, par exemple, tous les travaux de Edgar Frank Codd, spécialiste reconnu du domaine et auteur de l'ouvrage de référence Cellular automata (1968).

Des structures, constituées de plusieurs cellules, peuvent apparaître dans l'univers ; les plus classiques sont :

Il existe également d'autres structures, qui apparaissent beaucoup plus rarement (voire pas du tout pour les jardins d'éden) dans l'univers de jeu :

Les structures stables (en anglais ) sont des ensembles de cellules ayant stoppé toute évolution : elles sont dans un état stationnaire et n'évoluent plus tant qu'aucun élément perturbateur n'apparaît dans leur voisinage. Un bloc de quatre cellules est la plus petite structure stable possible.

Certaines figures se stabilisent en structures florales après une succession d'itérations comparables à une floraison.

Les oscillateurs se transforment de manière cyclique, en revêtant plusieurs formes différentes avant de retrouver leur état initial. Des figures de ce type sont très nombreuses : on en connaît actuellement des centaines. La " grenouille " est une structure qui se répète toutes les deux générations.

Elles peuvent apparaître relativement facilement dans l'univers de jeu par l'évolution spontanée de " graines " beaucoup plus simples.

Les vaisseaux - ou navires - (en anglais spaceships , " vaisseaux spatiaux ") sont des structures capables, après un certain nombre de générations, de produire une copie d'elles-mêmes, mais décalée dans l'univers du jeu.

Le déplacement d'un vaisseau qui retrouve après n étapes sa configuration initiale déplacée de A cases horizontalement et de B cases verticalement est noté A-B, et sa vitesse (A, B)c/n, où c représente la " vitesse de la lumière " dans le jeu de la vie, c'est-à-dire la vitesse maximale d'une cellule par génération. L'existence de vaisseaux de type A - B pour A et B quelconques a été démontrée. On distingue :

des vaisseaux de type transversal (ou orthogonaux), c'est-à-dire A = 0 ou B = 0 ;

des vaisseaux de type diagonal, avec A = ± B ;

des vaisseaux ayant un déplacement oblique, c'est-à-dire A ≠ ± B. On parle aussi de vaisseau-cavalier (knightship en anglais).

Le premier vaisseau oblique, appelé Gemini, a été découvert par Andrew J. Wade en 2010. Il se déplace de 5 120 cellules verticalement et de 1 024 cellules horizontalement toutes les 33 699 586 générations. Des variantes existent où sa vitesse et sa période sont différentes. C'est aussi un constructeur universel.

On prouve également qu'un vaisseau de type A - B a nécessairement une période N ≥ 2(A+B), donc que la vitesse maximale pour un vaisseau diagonal est (1, 1)c/4, et que celle pour un vaisseau orthogonal est (2, 2)c/4 = (1, 1)c/2.

On sait construire des vaisseaux de taille et de période aussi grandes que souhaitées, en utilisant des séries de composants.. Le planeur est le plus petit vaisseau du jeu de la vie, qui possède aussi la plus grande vitesse pour un vaisseau diagonal.

Les mathusalems sont des structures actives qui mettent un certain temps avant de se stabiliser. Certains, comme les " lapins ", mettent plus de 15 000 générations avant de se stabiliser en un nombre plus ou moins important de débris variés.

Les puffeurs (de l'anglais , " générateur de fumée ") sont des configurations qui se déplacent en laissant derrière elles une traînée constituée de débris.

Les canons, ou lanceurs, ou encore lances-navires (en anglais ) sont en quelque sorte des oscillateurs lâchant des débris, capables de produire des vaisseaux, à un rythme variable (toutes les 15, 23, 30 ou 360 générations par exemple, ou bien de manière apparemment imprévisible pour les lance-navires pseudo-aléatoires[précision nécessaire]).

De telles structures peuvent être créées à partir de puffeurs que l'on modifie afin que les débris s'agencent sous forme de navires. Le premier canon à avoir été découvert émet un planeur toutes les 30 générations.

Un jardin d'Éden est une configuration sans passé possible : aucune configuration ne donne à l'étape suivante un jardin d'Éden.

La démonstration mathématique se fonde sur la combinatoire et se trouve notamment dans Winning Ways for your Mathematical Plays, livre publié en 1982 par Berlekamp, Conway, et Guy.

En 2010, Gemini, le tout premier constructeur universel du jeu de la vie, a été découvert. Cette immense figure fait 4 217 807 cellules sur 4 220 191. En avançant, cette figure crée une copie d'elle-même en détruisant la précédente. L'opération prend environ 34 millions de générations. Comme Gemini se déplace et ne laisse rien derrière lui, c'est aussi un vaisseau. C'est d'ailleurs le premier vaisseau à se déplacer obliquement, c'est-à-dire ni orthogonalement, ni diagonalement.

La puissance et la capacité mémoire des ordinateurs personnels depuis le passage au 64 bits permet l'exploration de très grands espaces cellulaires du jeu de la vie. On peut alors en espérer l'émergence de structures complexes d'un haut niveau d' auto-organisation, voire d'esthétique. Stephen Wolfram et d'autres , ont exploré cette voie. Dès les années 1980, le clown émerge à l'itération 110 d'une dynamique d'un réseau amorcé à partir d'un U initial de 7 cellules (appelé généralement "pi heptomino") formant une image de la lettre U.

N.b. : le clown est formé à l'envers. Pour voir un clown comme sur l'illustration, c'est un U inversé qu'il faut dessiner.

Détails sur la dynamique du réseau : ce " U " de 7 cellules (également appelé heptomino pi) évolue vers une structure complexe et " organique " en passant par des formes très esthétiques. De plus, la structure est auto-reproductible avec un déphasage, la nouvelle structure fille (itération 45) interférant avec une version de la structure mère (itération 15) en cours d'évolution. À l'itération 110 on obtient cette image de " clown ". Puis le réseau se stabilise sur une forme stable oscillante complexe.

Certaines propriétés du jeu de la vie ont pu être démontrées, en particulier :

La croissance d'une configuration est au maximum en t². Cette propriété est triviale pour tout automate cellulaire bi-dimensionnel : dans le cas du jeu de la vie, comme la vitesse de transmission de l'information est de une case par pas de temps dans chacune des 8 directions, le nombre de cellules vivantes est trivialement limité par une borne en 8t². La question serait plutôt de savoir quelle est la configuration dont le taux de croissance est maximal.

L'existence de portes logiques , , . Ces portes logiques permettent de coder une machine de Turing universelle au sein du jeu de la vie. Par conséquent, le problème qui consiste à prédire le comportement asymptotique de toute structure du jeu de la vie est indécidable.

Malgré sa simplicité, ce jeu est une machine de Turing universelle : il est possible de calculer tout algorithme pourvu que la grille soit suffisamment grande et les conditions initiales correctes.

Plusieurs programmes informatiques simulent le jeu de la vie; dont Mirek's Cellebration. Ceux qui sont écrits en Java ou JavaScript peuvent être inclus facilement dans une page web. Ces simulateurs sont cependant peu efficaces quand ils représentent le terrain par un tableau bi-dimensionnel et se contentent de faire évoluer les cellules en suivant les règles de Conway.

En 1980, Bill Gosper a inventé puis écrit Hashlife, un algorithme de simulation beaucoup plus efficace, permettant de manipuler plusieurs millions de cellules sur des millions de générations en des temps plus courts. Cet algorithme reposait sur une idée différente : en effet, si l'on considère une portion de l'espace du jeu relativement isolée de ses voisines, il est possible de la faire " tourner " pendant un certain nombre n de générations, puis de mémoriser le résultat. Si la configuration de départ se reproduit ailleurs, on pourra alors " sauter " directement n générations pour cette partie du jeu. Ce nouvel algorithme faisait donc " tourner " différentes portions de l'espace à des vitesses différentes et parvenait à préserver la cohérence aux bordures de chaque région ainsi simulée. Il faisait appel à une table de hachage pour mémoriser et retrouver rapidement des configurations locales.

Le jeu de la vie est extrêmement sensible à la manière de calculer la génération suivante. L'implémentation classique est synchrone, c'est-à-dire que l'état de chaque cellule de génération n+1 est calculé à partir de l'état des cellules de génération n. Bersini et Detours ont montré que les comportements intéressants du jeu de la vie disparaissent avec la quasi-totalité des schémas de mise à jour non synchrones (où les états n+1 peuvent s'influencer les uns les autres, comme dans la vraie vie). Cependant, Nehaniv a montré que tout comportement synchrone peut être émulé par des automates cellulaires asynchrones et il est donc possible de retrouver le comportement du jeu de la vie sans " horloge globale " cadençant l'évolution des générations,.

Depuis 2008, de nombreux programmes (dont le plus connu est Golly) intègrent cet algorithme dans une interface graphique. Ils ont permis de créer des configurations énormes et très ingénieuses et de suivre leur évolution, insufflant une nouvelle dynamique dans l'étude déjà très riche de cet automate cellulaire.

Depuis 2012, une recherche sur Google des termes " Conway's game of life " fait apparaître un easter-egg : un jeu de la vie interactif s'affiche en arrière-plan.

Il existe des variantes du jeu de la vie, fondées sur des règles de voisinage légèrement différentes, par exemple HighLife ou Day & night. Cette variante comporte deux types de cellules, les " positives " et les " négatives ", chacune répondant aux mêmes règles, à la différence du signe. Une cellule positive nécessite une somme de 3 pour " naître ", une négative une somme de −3. Les cellules vivantes s'intègrent dans le bilan des cellules alentour pour leur survie ou leur déclin. Les deux populations ne peuvent en général survivre côte à côte.

: document utilisé comme source pour la rédaction de cet article.

" (en) Martin Gardner, Mathematical Games. The fantastic combinations of John Conway's new solitaire game " life ", Scientific American , no 223,‎ , p. 120-123 (lire en ligne, consulté le )

(en) Edgar Frank Codd, Cellular Automata, New York Academic Press,

Jean-Paul Delahaye, Jeux finis et infinis, Éditions du Seuil, (ISBN 978-2-02-096483-8 ), chap. 1 (" Quarante ans de jeu de la vie ")

1. (en)Adam P. Goucher, Oblique Life spaceship created, Game of Life News, 19 mai 2010, (consulté le 11 mai 2010).

2. Bernard Feltz et al, Emergence and Reductionism: from the Game of Life to Science of Life, in SELF-ORGANIZATION AND EMERGENCE IN LIFE SCIENCES, Springer Netherlands Editor, 2006, (Print) 978-1-4020-3917-1 (Online)[1]

3. N. M. Gotts, Emergent phenomena in large sparse random arrays of Conway's Game of Life, in INTERNATIONAL JOURNAL ON SYSTEM SCIENCES, Volume 31, Issue 7 July 2000, pages 873 - 894 [2]

4. Jean-Claude Perez, " DE NOUVELLES VOIES VERS L'INTELLIGENCE ARTIFICIELLE : pluri-disciplinarité, auto-organisation et réseaux neuronaux ", 1988, Éd. Masson Paris(ré-édition en 1989), pages 261-262, .

5. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, A K Peters/CRC Press; 2nd edition (March 30, 2004)

6. H. Bersini, V. Detours, " Asynchrony Induces Stability in Cellular Automata Based Models ", In Proceedings of the IVth Conference on Artificial Life - MIT Press/Bradford Books, 1994.

7. C. L. Nehaniv, " Evolution in Asynchronous Cellular Automata ", Artificial Life VIII, 65-73, MIT Press, 2002.

8. C. L. Nehaniv, " Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network ", International Journal of Algebra & Computation, 14(5-6):719-739, 2004.

9. en:List of Google's hoaxes and easter eggs#Search

Sur les autres projets Wikimedia :

# data[].attributes.attachment_link.description
Le jeu de la vie est un automate cellulaire imaginé par John Horton Conway en 1970 et qui est probablement le plus connu de tous les automates cellulaires. Malgré des règles très simples, le jeu de la vie est Turing-complet. Le jeu de la vie est un jeu de simulation au sens mathématique plutôt que ludique.

# data[].attributes.attachment_link.readable_text
Recently a zoo in Paris has showcased a very particular creature. The creature was a Physarum polycephalum is a protist (category in which all living things which we do not have an idea of how to classify are part), a unicellular living being with 720 sexes and some amazing characteristics like the possibility to heal itself in seconds after has been cut in half, remember things , transfer memories to other of its species and solve complex tasks.

The creature is quite amazing since it can do all these things without a brain or a nervous system, giving to the scientists hard times to figure out how this happens and opening to the idea of a new form of intelligence.

One of the incredible tasks the slime mold can do is to solve complex maze finding the shortest path or the most efficient way to connect food sources.

One of the experiments was done on the slime mold was reproducing the Tokyo major cities' positions with food and since Physarum avoids bright light, light was used to simulate mountains, lakes and other prohibitive terrain on his miniature map.

The results were quite similar to what the actual Tokyo rail network is. Which took a long time for engineers to plan. Here is a video showing the slime mold during the experiment.

And the following picture compares the map with the slime mold network. Quite similar, is it?

When experimented with mazes once the slime molds find the most efficient path, if a part of it is cut and joined to another slime mold, the information will be transmitted and it will go directly to the end using the information gathered.

slime mold solving a maze

Recently I started to practice algorithms, and when I read the description of the experiment I immediately thought: that is Dijkstra.

Dijkstra is an algorithm used to find the shortest path from a start point to an end taking into consideration for every path the difficulty of that path, which for example in a street network can represent its speed (if it is a highway or a country road). The algorithm starting from the first nodes finds the shortest path to the end, this is used from Google Maps to find the best way for your destination.

Starting from the first nodes, its neighbors are analyzed and inserted in a list, which gets sorted by the shorted summed distance from the start. Every node keeps track of the node from which is coming. Once a node adds al its neighbours from the list it goes out from the list and the next one is analyzed.

Consider, from the previous picture the node A. The node A has a distance of 7 from S (which represents the Start). But if we go to A through the node B the total distance we can do is 3+2. which is less than 7. So that node will be overwritten with a new total distance from the start and the node from which is coming will be overwritten by the new node ( in this case B).

This continues until the End node goes out from the list, and we can backtrack the path, reading from which node the best path was coming.

An efficient implementation of this algorithm is the A star search. This adds to the calculation of heuristic value, which can be how far every point from the endpoint in air distance and sums it to the distance from the start. This helps to make the algorithm faster because the nodes in the neighborhood that are farther from the end should be penalized in the analysis and go down in the list when sorted, but in case it is the actual shortest way will still be eventually analyzed.

So I tried to challenge the little French brainless genius writing my own version of what he naturally does.
https://amaze-solver.herokuapp.com/
I tried to solve it in an Object Oriented way.

I used two class AStar and NodeElement: the first for every cell of the maze.

class NodeElement { constructor(row, col, difficulty, isWall, aStarInstance){heuristicCalculation(node) {return this.heuristic = this.eucledianDistance + this.difficultySumsneighboursCalculation(openQueue){if(this.row < this.aStar.matrixLenght-1) {
 this.row = row
 this.col = col
 this.eucledianDistance = this.aStar.eucledianDistance(this)
 let difficultySums
 }
 let neighbours = []
 enqueuedNode = openQueue.find(node=>node.row===this.row+1 && node.col===this.col)
 if(!enqueuedNode){
 newNode = this.aStar.nodes.find(node=>(node.row===this.row+1 && node.col===this.col))
 if(newNode.wall===false && !this.aStar.alreadyChecked.includes(newNode) && !this.aStar.openQueue.includes(newNode) ) {
 newNode.heuristicCalculation(this)
 neighbours.push(newNode)
 }
 }else{
 enqueuedNode.heuristicCalculation(this)
 }
 }
 if(this.col < this.aStar.matrixLenght-1) {
 enqueuedNode = openQueue.find(node=>node.row===this.row && node.col===this.col+1)
 if(!enqueuedNode){
 newNode = this.aStar.nodes.find(node=>(node.row===this.row && node.col===this.col+1))
 if(newNode.wall===false && !this.aStar.alreadyChecked.includes(newNode) && !this.aStar.openQueue.includes(newNode) ){
 newNode.heuristicCalculation(this)
 neighbours.push(newNode)
 }
 }else{
 enqueuedNode.heuristicCalculation(this)
 }
 }
 if(this.row > 0) {
 enqueuedNode = openQueue.find(node=>node.row===this.row-1 && node.col===this.col )
 if(!enqueuedNode){
 newNode = this.aStar.nodes.find(node=>(node.row===this.row-1 && node.col===this.col))
 if(newNode.wall===false && !this.aStar.alreadyChecked.includes(newNode) && !this.aStar.openQueue.includes(newNode) ){
 newNode.heuristicCalculation(this)
 neighbours.push(newNode)
 }
 }else{
 enqueuedNode.heuristicCalculation(this)
 }
 }
 if(this.col > 0) {
 enqueuedNode = openQueue.find(node=>node.row===this.row && node.col===this.col-1)
 if(!enqueuedNode){
 newNode = this.aStar.nodes.find(node=>(node.row===this.row && node.col===this.col-1))
 if(newNode.wall===false && !this.aStar.alreadyChecked.includes(newNode) && !this.aStar.openQueue.includes(newNode) ){
 newNode.heuristicCalculation(this)
 neighbours.push(newNode)
 }
 }else{
 enqueuedNode.heuristicCalculation(this)
 }
 }
 return neighbours
 let enqueuedNode
 let newNode
 difficultySums = this.difficulty + Number(node.difficultySums)
 if( this.difficultySums === '' ) {
 this.difficultySums = difficultySums
 this.through=node
 }else if(this.difficultySums > difficultySums){
 this.difficultySums = difficultySums
 this.through=node
 }else{
 this.wall = isWall
 this.difficulty = difficulty
 this.through = ''
 this.heuristic = Infinity
 this.eucledianDistance = Infinity
 this.difficultySums = ''
 this.aStar = aStarInstance
 this.neighbours=[]
 } } } }

and the second for the generic algorithm

class AStar { constructor(start, end, grid){this.optimalPath=[]startAlgorithm(){while(this.openQueue.length>0 ){retrieveOptimalPath(node){eucledianDistance(node){
 this.grid = grid
 this.matrixLenght = this.grid.length
 }
 this.openQueue[0].heuristicCalculation(this.openQueue[0])
 if(this.openQueue[0]===this.end){
 this.optimalPath.push(node)
 return Math.sqrt(Math.pow(Math.abs(node.row-this.end.row),2)+Math.pow(Math.abs(node.col-this.end.col),2))
 }
 if(node.through!==this.start){
 this.retrieveOptimalPath(node.through)
 }else{
 this.optimalPath.push(this.start)
 }
 }
 break
 }
 let neighbours = this.openQueue[0].neighboursCalculation(this.openQueue)
 let queue = this.openQueue
 this.alreadyChecked.push(queue.shift())
 let newQueue = queue.concat(neighbours)
 let sortedNeighbours = newQueue.sort(function(a, b){return a.heuristic - b.heuristic})
 this.openQueue = sortedNeighbours
 }
 if(this.openQueue.length !== 0){this.retrieveOptimalPath(this.openQueue[0])}
 }
 this.nodes =[]
 for(let i=0;i<grid.length;i++){
 for(let j=0;j<grid[0].length;j++){
 if(i==start[0] && j==start[1]){
 this.start = new NodeElement(i, j, grid[i][j].difficulty, grid[i][j].wall, this)
 this.nodes.push(this.start)
 } else if(i==end[0] && j==end[1]){
 this.end = new NodeElement(i, j, grid[i][j].difficulty, grid[i][j].wall, this)
 this.nodes.push(this.end)
 } else {
 this.nodes.push(new NodeElement (i,j,grid[i][j].difficulty,grid[i][j].wall,this))
 }
 }
 }
 this.openQueue = [this.start]
 this.alreadyChecked = []

The optimal path was then obtained by running

let aStarInstance = new AStar (start,end, grid)
 aStarInstance.startAlgorithm()
 let optimalPath = aStarInstance.optimalPath

Where grid is a matrix with every element represented by this object with a boolean if it represents a wall or not and a difficulty level if it is not.

I.E.

{wall:false, difficulty: 1}

Start and End are just an array with the two coordinates (row and column) of the start and end.

Here is the github repo for the heroku host.
https://github.com/nuclear-pasta/AstarAlgorithmTest
If you want to check how this algorithm compares to others, there is this amazing website that allows you to compare all the different algorithms giving a visualization of the cells analyzed, which can help to visualize and understand how they work!
https://qiao.github.io/PathFinding.js/visual/
And if you want to understand better how Dijkstra work, there is a marvelous video on the Computerphile youtube channel with Mike Pound, which I used to create the algorithm (and used his hands in one of the previous picture)
https://www.youtube.com/watch?v=GazC3A4OQTE

# data[].attributes.attachment_link.title
How to solve a maze with an A-star algorithm (Javascript) if you are not a slime mold.

# data[].attributes.attachment_link.description
Recently a zoo in Paris has showcased a very particular creature. The creature was a Physarum polycephalum is a protist (category in which all living things which we do not have an idea of how to classify are part), a unicellular living being with 720 sexes and some amazing characteristics like the possibility to heal itself in seconds after has been cut in half, remember things , transfer memories to other of its species and solve complex tasks.

# data[].attributes.attachment_link.readable_text
L'algorithme de Dijkstra pour trouver le chemin le plus court entre a et b. Il choisit le sommet non visité avec la distance la plus faible, calcule la distance à travers lui à chaque voisin non visité, et met à jour la distance du voisin si elle est plus petite. Il marque le sommet visité (en rouge) lorsque il a terminé avec les voisins.

En théorie des graphes, l' algorithme de Dijkstra (prononcé ) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.

L'algorithme porte le nom de son inventeur, l' informaticien néerlandais Edsger Dijkstra, et a été publié en 1959.

Cet algorithme est de complexité polynomiale. Plus précisément, pour sommets et arcs, le temps est en , voire en .

L'algorithme de Dijkstra permet de résoudre un problème algorithmique : le problème du plus court chemin. Ce problème a plusieurs variantes. La plus simple est la suivante : étant donné un graphe non-orienté, dont les arêtes sont munies de poids, et deux sommets de ce graphe, trouver un chemin entre les deux sommets dans le graphe, de poids minimum. L'algorithme de Dijkstra permet de résoudre un problème plus général : le graphe peut être orienté, et l'on peut désigner un unique sommet, et demander d'avoir la liste des plus courts chemins pour tous les autres nœuds du graphe.

Principe sur un exemple

L'algorithme prend en entrée un graphe orienté pondéré par des réels positifs et un sommet source. Il s'agit de construire progressivement un sous-graphe dans lequel sont classés les différents sommets par ordre croissant de leur distance minimale au sommet de départ. La distance correspond à la somme des poids des arcs empruntés.

Au départ, on considère que les distances de chaque sommet au sommet de départ sont infinies, sauf pour le sommet de départ pour lequel la distance est nulle. Le sous-graphe de départ est l'ensemble vide.

Au cours de chaque itération, on choisit en dehors du sous-graphe un sommet de distance minimale et on l'ajoute au sous-graphe. Ensuite, on met à jour les distances des sommets voisins de celui ajouté. La mise à jour s'opère comme suit : la nouvelle distance du sommet voisin est le minimum entre la distance existante et celle obtenue en ajoutant le poids de l'arc entre sommet voisin et sommet ajouté à la distance du sommet ajouté.

On continue ainsi jusqu'à épuisement des sommets (ou jusqu'à sélection du sommet d'arrivée).
Animation d'un algorithme de Dijkstra
L'algorithme de Dijkstra fonctionne aussi sur un graphe non orienté (qui peut le plus peut le moins). L'exemple ci-contre montre les étapes successives dans la résolution du chemin le plus court dans un graphe. Les nœuds symbolisent des villes identifiées par une lettre et les arêtes indiquent la distance entre ces villes. On cherche à déterminer le plus court trajet pour aller de la ville A à la ville J.

En neuf étapes, on peut déterminer le chemin le plus court menant de A à J, il passe par C et H et mesure 487 km.

Présentation sous forme de tableau

On peut aussi résumer l'exécution de l'algorithme de Dijkstra avec un tableau. Chaque étape correspond à une ligne. Une ligne donne les distances courantes des sommets depuis le sommet de départ. Une colonne donne l'évolution des distances d'un sommet donné depuis le sommet de départ au cours de l'algorithme. La distance d'un sommet choisi (car minimale) est soulignée. Les distances mises à jour sont barrées si elles sont supérieures à des distances déjà calculées.

Le tableau donne non seulement la distance minimale de la ville A à la ville J (487) mais aussi le chemin à suivre à rebours (J - H - C - A) pour aller de A à J ainsi que toutes les distances minimales de la ville A aux autres villes rangées par ordre croissant.

Le graphe est noté où :

l'ensemble est l'ensemble fini des sommets du graphe ;

l'ensemble est l'ensemble des arcs de tel que : si est dans , alors il existe un arc depuis le nœud vers le nœud ;

on définit la fonction définie sur dans qui à un couple associe le poids positif de l'arc reliant à (et s'il n'y a pas d'arc reliant à ).

Le poids du chemin entre deux sommets est la somme des poids des arcs qui le composent. Pour une paire donnée de sommets (le sommet du départ) (le sommet d'arrivée) appartenant à , l'algorithme trouve un chemin depuis vers de moindre poids (autrement dit un chemin le plus léger ou encore le plus court).

L'algorithme fonctionne en construisant un sous-graphe de manière que la distance entre un sommet de depuis soit connue et soit un minimum dans . Initialement, contient simplement le nœud isolé, et la distance de à lui-même vaut zéro. Des arcs sont ajoutés à à chaque étape :

1. en identifiant tous les arcs dans ;

2. en choisissant l'arc dans qui donne la distance minimum depuis à en passant tous les chemins créés menant à ce nœud.

L'algorithme se termine soit quand devient un arbre couvrant de , soit quand tous les nœuds d'intérêt sont dans .

On peut donc écrire l'algorithme de la façon suivante :

Entrées :  un graphe avec une pondération positive   des arcs,   un sommet de     pour chaque sommet    Tant qu'il existe un sommet hors de  Choisir un sommet  hors de   de plus petite distance   Mettre  dans   Pour chaque sommet  hors de   voisin de   Si d[b] > d[a] + poids(a, b)  prédécesseur[b] := a Fin Pour Fin Tant Que

L'algorithme utilise les fonctions annexes suivantes.

Initialisation de l'algorithme

Initialisation(G,sdeb)
1pour chaque point s de G faire 2 d[s] := infini /* on initialise les sommets autres que sdeb à infini */ 3fin pour 4 d[sdeb] := 0 /* la distance au sommet de départ sdeb est nulle */

Recherche d'un nœud de distance minimale

On recherche un nœud de distance minimale (relié par l'arc de poids le plus faible) de parmi les nœuds situés hors de . Le complémentaire de est noté . On implémente pour cela une fonction Trouve_min(Q) qui choisit un nœud de Q de distance minimale.

Trouve_min(Q)
1 mini := infini
2 sommet := -1
3pour chaque sommet s de Q 4si d[s] < mini 5alors 6 mini := d[s] 7 sommet := s 8 renvoyer sommet

Mise à jour des distances

On met à jour les distances entre et en se posant la question : vaut-il mieux passer par ou pas ?

maj_distances(s1,s2)
1si d[s2] > d[s1] + Poids(s1,s2) /* Si la distance de sdeb à s2 est plus grande que */ 2 /* celle de sdeb à S1 plus celle de S1 à S2 */ 3alors 4 d[s2] := d[s1] + Poids(s1,s2) /* On prend ce nouveau chemin qui est plus court */ 5 prédécesseur[s2] := s1 /* En notant par où on passe */

Voici la fonction principale utilisant les précédentes fonctions annexes :

Dijkstra(G,Poids,sdeb)
1 Initialisation(G,sdeb)
2 Q := ensemble de tous les nœuds
3tant que Q n'est pas un ensemble vide faire 4 s1 := Trouve_min(Q) 5 Q := Q privé de s1 6pour chaque nœud s2 voisin de s1 faire 7 maj_distances(s1,s2) 8fin pour 9fin tant que

Le plus court chemin de à peut ensuite se calculer itérativement selon l'algorithme suivant, avec la suite représentant le plus court chemin de à :

1 A = suite vide
2 s := sfin
3tant que s != sdeb faire 4 A = A + s /* on ajoute s à la suite A */ 5 s = prédécesseur[s] /* on continue de suivre le chemin */ 6fin tant que 7 A = sdeb /* on ajoute la node de départ */

Attention : s'il n'y a pas de chemin de à cette partie de l'algorithme fait une boucle infinie ou une erreur selon votre implémentation.

Spécialisation de l'algorithme

Il est possible de spécialiser l'algorithme en arrêtant la recherche lorsque l'égalité est vérifiée, dans le cas où on ne cherche que la distance minimale entre et .

L'efficacité de l'algorithme de Dijkstra repose sur une mise en œuvre efficace de Trouve_min. L'ensemble est implémenté par une file à priorités. Si le graphe possède arcs et nœuds, qu'il est représenté par des listes d'adjacence et si on implémente la file à priorités par un tas binaire (en supposant que les comparaisons des poids d'arcs soient en temps constant), alors la complexité en temps de l'algorithme est . En revanche, si on implémente la file à priorités avec un tas de Fibonacci, l'algorithme est en .

La démonstration de correction est une récurrence sur Card( P) (qui augmente de 1 à chaque itération) et repose sur l'invariant suivant :

où :

mini(c) est le poids d'un plus court chemin menant à c ;

miniP(c) est le poids d'un plus court chemin dont tous les sommets intermédiaires sont dans P menant à c.

Si n = Card( P), la preuve est la suivante :

pour n = 0 et 1 : immédiat ;

pour n un entier non nul, supposons l'invariant vrai.

L'algorithme sélectionne un pivot tel que , et l'ajoute dans P. Il faut donc montrer que après modification de P:

Par hypothèse, avant modification de P, donc s'il existe un chemin C tel que alors ce chemin contient au moins un sommet b a tel que .

Soit donc un tel sommet b tel que tous ses prédécesseurs dans C soient dans P (il existe car le premier sommet de C est l'origine qui est dans P). Décomposons C en Cb- et Cb+ où Cb- est la première partie de C dont le dernier sommet est b, et Cb+ la suite de C. Alors : contradiction.

Il n'existe donc aucun chemin C tel que d'où . L'égalité est toujours vraie pour les autres éléments de P.

Enfin, l'algorithme met à jour la fonction d (et prédécesseur) pour les successeurs b du pivot a : .

Montrons qu'alors, :

si c n'est pas un successeur du pivot a, alors il n'existe aucun nouveau chemin C menant à c tel que et dont tous les sommets intermédiaires sont dans P après l'ajout de a dans P puisqu'il faudrait alors passer par a avant de passer par un autre sommet , mais ce ne serait pas le plus court chemin jusqu'à d puisque le poids du plus court chemin jusqu'à d a déjà été calculé avant l'ajout de a dans P par hypothèse, et ce chemin ne contient donc que des sommets ayant été dans P avant l'ajout de a dans P ;

sinon, il existe de tels chemins, en notant C le meilleur d'entre eux, alors C sera un des nouveaux chemins engendrés par l'ingestion du pivot a par P, donc et d'autre part le pivot a est le dernier sommet intermédiaire de C puisque le plus court chemin menant aux autres sommets de P ne passe par a comme expliqué plus haut. C est donc la réunion du plus court chemin menant à a avec l'arc (a, c) : d'où .

Applications

L'algorithme de Dijkstra trouve une utilité dans le calcul des itinéraires routiers. Le poids des arcs pouvant être la distance (pour le trajet le plus court), le temps estimé (pour le trajet le plus rapide), la consommation de carburant et le prix des péages (pour le trajet le plus économique).

Une application courante de l'algorithme de Dijkstra apparaît dans les qui permettent un protocoles de routage interne " à état de liens ", tels que Open Shortest Path First (OSPF) ou - ou encore sur les réseaux ATM -, routage internet très efficace des informations en cherchant le parcours le plus efficace. [réf. nécessaire]

L'algorithme de Dijkstra est fondé sur un parcours en largeur.

La spécialisation de l'algorithme de Dijkstra qui calcule un plus court chemin d'une source à une destination est une instance de l'algorithme A* dans lequel la fonction heuristique est la fonction nulle. L'algorithme A* qui utiliserait une heuristique minorante et monotone (par exemple la distance à vol d'oiseau) peut être plus efficace .

L'algorithme ne s'applique pas aux graphes avec des poids négatifs. Mais l'algorithme de Bellman-Ford permet de résoudre le problème des plus courts chemins depuis une source avec des poids négatifs (mais sans cycle négatif).

L'algorithme de Floyd-Warshall calcule des plus courts chemins entre tous les sommets dans un graphe où les poids peuvent être négatifs.

1. " ↑ (en) Edsger Dijkstra, A note on two problems in connexion with graphs ", Numerische Mathematik , Springer Science+Business Media, vol. 1, no 1,‎ , p. 269-271 (ISSN 0029-599X et 0945-3245, OCLC 1760917, DOI 10.1007/BF01386390, lire en ligne)

2. ↑ " http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.4349&rep=rep1&type=pdf "

3. Dijkstra, E. W., " ↑ A note on two problems in connexion with graphs ", Numerische Mathematik, vol. 1,‎ , p. 269-271 (DOI 10.1007/BF01386390.) .

4. ↑ Par exemple, les nœuds n'ayant pas d'arêtes autres que celle que l'on a parcourue pour arriver à eux, ne sont pas considérés comme des nœuds d'intérêt.

5. La suite de caractères /* ... */ est un ↑ commentaire.

6. ↑ Cormen et al. 2010, p. 610

7. " ↑ (en) John Moy, Using the Dijkstra algorithm, a tree is formed from this subset of the link state database. ", " RFC2328 OSPF Version 2 ", (consulté le ) : p. 161

8. " ↑ (en) David R. Oran, An algorithm invented by Dijkstra (see references) known as shortest path first (SPF), is used as the basis for the route calculation. " " RFC1142 : OSI IS-IS Intra-domain Routing Protocol ", (consulté le ) :

(en) " A short introduction to the art of programming " de Edsger W. Dijkstra, 1971, contenant l'article original (1959) décrivant l'algorithme de Dijkstra (pages 67 à 73).

# data[].attributes.attachment_link.description
L'algorithme de Dijkstra pour trouver le chemin le plus court entre a et b. Il choisit le sommet non visité avec la distance la plus faible, calcule la distance à travers lui à chaque voisin non visité, et met à jour la distance du voisin si elle est plus petite.

# data[].attributes.attachment_link.readable_text
J'ai fait ça pour mon petit docteur. Elle l'utilise avec sa trousse médicale. Elle a cassé l'original plusieurs fois ... La super-colle ne fonctionne plus pour coller deux morceaux de plastique ensemble, alors j'en ai fait un plus solide.

Plus connu sous son nom usuel " Blob ", le Physarum polycephalum est un organisme monocellulaire. Il possède cependant des capacités d'apprentissage faisant l'objet de recherche dans le laboratoire d'Audrey Dussutour, directrice de...

En dehors de son offre de projets récurrents, le service Education Jeunesse du CNES tire parti de l'actualité spatiale pour proposer de nouveaux projets et sensibiliser les jeunes aux sciences et aux technologies spatiales.

# data[].attributes.attachment_link.title
Les outils makers au service de l'étude du BLOB

# data[].attributes.attachment_link.description
En septembre 2021 le projet " élevé ton blob " se monte dans plusieurs centaines d'écoles. Cette coopération entre le CNES et le CNRS avec le soutien de l'académie de Toulouse propose aux élèves d'école, collège et lycée de développer une série d'expérimentations en parallèle de Thomas Pesquet présent dans l'ISS pour la mission Alpha.

# data[].attributes.attachment_link.description
Train a computer to recognize your own images, sounds, & poses. A fast, easy way to create machine learning models for your sites, apps, and more – no expertise or coding required.

# data[].attributes.body
Imiter le vivant ?
Emergence ? Jeux de la vie
Prédiction ?
Résoudre ? Jeux de go
Se tromper ?

# data[].attributes.body
1 - Créer une machine capable d'identifier Bourgeon/Fleur/Fruit du jardin.
2 - Créer une machine capable d'identifier 5 espèces de plantes du jardin.

# data[].attributes.body
> Utiliser des instruments d’observation, de mesures et des techniques de préparation et de collecte

> Identifier et choisir des notions, des outils et des techniques, ou des modèles simples pour mettre en œuvre une démarche scientifique.