optimiser son barathon au niveau national en UK

@phallusflasque: Et le g/intéressant bordel !

@phallusflasque: Il y'a quand même plus de 27 000 bières à boire sur la route je suis pas sur de tenir :o

@ThisIsANewDay: A 3,70€ la pinte en moyenne en Angleterre, ça fait chère le barathon !

@Azertsix: y avait le g/informatique voir mm le g/science, c'est une application du "problème du voyageur de commerce " a la base, faite par des chercheur, ce serait "le problème de ce type le plus complexe jamais résolu", [...] Il y a tellement de pubs au Royaume-Uni que c’est le problème de ce type le plus complexe jamais résolu.[...]

@phallusflasque: Ouais, moi j'aurais mis ça en g/intéressant.

@Azertsix: pas faux, mais ça dépend surtout du point de vus aussi, perso c'est surtout le Lol que j'ai retenus, genre des chercheurs qui ce sont dit"tiens on va cherché la solution de la route la plus courte pour faire tout les pubs du pays!"
plus que le coté "tiens c'est intéressent a savoir, si un jour me viens l'idée de me tapé un tour de planète et demie en buvant de bières dans autre pays !"
mais je peux comprendre que tu puisse trouver de l’intérêt a cette info' !

@Azertsix: Putain arrête cette propagande c'est de plus en plus louche

@phallusflasque: D'après ce que j'ai appris à l'école, c'est un problème est impossible à résoudre déjà pour 50 étapes... ils ont sûrement trouvé un algorithme rapide qui trouve un chemin assez court mais certainement pas LE plus court.

@Minipouss: C'est un problème complexe et intéressant mais facile à résoudre pour 50 étapes.

src: https://en.wikipedia.org/wiki/Travelling_salesman_problem, https://en.wikipedia.org/wiki/Dijkstra's_algorithm

@Minipouss: Tu dis qu'il est impossible de trouver le plus court chemin pour un graphe orienté pondéré avec plus de 50 nœuds ?

@MrChirac: ca ne donne qu'un bon résultat, pas forcément le meilleur

@Minipouss: Avec les algorithmes actuelles, pour 50 noeuds (et bien plus) tu as l'assurance d'avoir le chemin le plus court en une fraction de secondes.

@MrChirac: C'est un problème NPC et il est dit qu'en résoudre un permettrait de résoudre tous les autres. Du coup, on aurait une crise avec la sécurité informatique car un de ces problèmes concerne les nombres premiers utilisés dans ce domaine.

Après donne moi un exemple d'algorithme, je vérifierai mais toujours est-il que j'ai vu ça en cours il y a moins de 10 ans et je ne pense pas qu'il y ait eu une grosse révolution dans le domaine (je peux me tromper) et c'est pourquoi j'aimerai bien avoir un exemple

@Minipouss: Je ne vois pas le rapport entre trouvé le chemin le plus court et la cryptographie... Peux-tu préciser?
Sinon concernant l'algorithme, t'as raison, c'est NPC. Mais ça commence à poser problème avec bien plus que 50 noeuds. Si tu veux un exemple, j'utilise le package Networkx en python pour "jouer" avec les graphs. https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html

@MrChirac: "Trouver un algorithme qui résout un problème NP-complet, comme le problème du voyageur de commerce, en temps polynomial suffirait à démontrer que P=NP, ce serait alors toute une série de problèmes très importants qui se trouveraient résolus (et, dans un même temps, les systèmes de cryptographie à clé publique seraient cassés). Même sans exhiber un algorithme, une preuve pourrait donner des indices précieux pour construire un tel algorithme, ou pour le moins en relancer sérieusement la recherche, car on le saurait alors possible avec certitude. L'existence de cet algorithme remettrait en question l'utilisation des systèmes de cryptographie à clé publique, qui servent notamment pour la sécurisation des transactions bancaires. En effet, casser ces systèmes revient à résoudre un problème NP (intuitivement, c'est facile si on connaît la clé privée). La sécurité repose sur l'assertion que ce n'est pas possible en temps polynomial." https://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%3D_NP

je crois que prouver que ton chemin est le plus court est un problème NP si je me rappelle bien, ce qui est déjà très compliqué. Trouver le plus court est NPC, ce qui est impossible sans un algo magique dans un temps "humain". En gros ton algo va trouver un très bon chemin mais je ne pense pas que ce soit le meilleur et je ne pense pas qu'un algo puisse le prouver.