Je n'ai jamais été habitué à faire un contrôle sur la taille d'une liste pour ne pas faire exploser la complexité (ça me parait 'sale')
J'ai l'impression que c'est quelque chose de commun, par exemple en pathfinding.
En A*, on sait dans quelle direction est la destination.
Si les 2 points ne sont pas connectés, il va falloir tester tout le graphe pour s'en rendre compte, ce qui va être long quand on a un grand graphe. Ou bien on peut abandonner l'idée de trouver une solution au bout d'un certain nombre d'essais.
Dans le cadre d'un jeu vidéo, ça peut être envisageable sachant que du coup c'est le joueur qui va choisir un autre point plus proche/accessible.
(En réalité, pour un jeu, je trouve plus commode de faire un algo pour détecter les différents graphes déconnectés, puis de lancer l'algo si les 2 points sont connectés, ça évite de perdre du temps à tester une solution puisqu'on sait à l'avance que ça ne marchera pas, mais ça dépend un peu du contexte à chaque fois)
(Et effectivement, ça fait gagner du temps mais ça fait utiliser plus de mémoire)
Ici, la complexité temporelle du seconde algorithme est au moins de N^log(N) !
Oui, je dirais que souvent, la complexité mémoire/spatiale évolue inversement par rapport à la complexité temporelle.
[^] # Re: Solution
Posté par Damien Thébault . En réponse au journal Informatique fondamentale : chemins dans un graphe. Évalué à 5.
Je n'ai jamais été habitué à faire un contrôle sur la taille d'une liste pour ne pas faire exploser la complexité (ça me parait 'sale')J'ai l'impression que c'est quelque chose de commun, par exemple en pathfinding.
En A*, on sait dans quelle direction est la destination.
Si les 2 points ne sont pas connectés, il va falloir tester tout le graphe pour s'en rendre compte, ce qui va être long quand on a un grand graphe. Ou bien on peut abandonner l'idée de trouver une solution au bout d'un certain nombre d'essais.
Dans le cadre d'un jeu vidéo, ça peut être envisageable sachant que du coup c'est le joueur qui va choisir un autre point plus proche/accessible.
(En réalité, pour un jeu, je trouve plus commode de faire un algo pour détecter les différents graphes déconnectés, puis de lancer l'algo si les 2 points sont connectés, ça évite de perdre du temps à tester une solution puisqu'on sait à l'avance que ça ne marchera pas, mais ça dépend un peu du contexte à chaque fois)
(Et effectivement, ça fait gagner du temps mais ça fait utiliser plus de mémoire)
Ici, la complexité temporelle du seconde algorithme est au moins de N^log(N) !Oui, je dirais que souvent, la complexité mémoire/spatiale évolue inversement par rapport à la complexité temporelle.