Problème : Le livreur de lait

[invite06fcc10b]

Un livreur de lait vous expose les problèmes de son travail :
"Le réseau routier comporte à chaque intersection de routes une ville. Il faut que je visite toutes les villes de ce réseau pour ravitailler les magasins avec qui j'ai un contrat commercial.
Mon objectif est de passer par toutes les villes en trouvant le chemin qui minimise la distance parcourue, afin de minimiser mes dépenses en carburant.
Malheureusement, je ne sais pas comment déterminer ce chemin. "
Patatras, alors qu'il étend la carte devant vous, vous renversez du lait sur celle-ci. Après avoir essuyé, vous constatez que les distances kilométriques ne sont plus lisibles, vous n'avez que l'indication de position de chaque ville et les routes.
Que pouvez vous proposer pour estimer une borne inférieure de la distance totale qu'il doit parcourir ? Evidemment, plus grande sera cette borne, mieux ce sera.

Contrainte : on se limitera aux méthodes dont le temps de calcul est proportionnel à N² dans le pire des cas, avec N nombre de villes à visiter.
-----

[invite06fcc10b]

Pourquoi personne ne répond à cette énigme ?
Ne me dites pas que ce problème est trop difficile !?
Faut-il des éclaircissements ?

[yat]

Pourquoi personne ne répond à cette énigme ?
Ne me dites pas que ce problème est trop difficile !?
Faut-il des éclaircissements ?

Bah je trouve qu'elle est pas évidente, moi...

Alors en première approximation : zéro.
Ensuite... euh... le périmètre du polygone convexe contenant tous les points...

Ca va encore me tourner dans la tête tout le week-end, ça...

Par contre, niveau éclaircissements, peut-être un peu plus de précisions sur l'effacement des distances... je vois pas à quoi ça sert, en fait... A moins que : Facile ! On résoud le problème du voyageur de commerce avec les différentes villes en considérant que les distances sont en ligne droite, et ça fait une borne inférieure parce que les distances réelles sont un peu plus longues

... bah quoi... N! c'est pas supérieur à N²... si ?

[invité576543]

C'est le problème du voyageur de commerce. C'est un problème ouvert, non?

Cordialement,

[A voir en vidéo sur Futura]

[invite06fcc10b]

Ensuite... euh... le périmètre du polygone convexe contenant tous les points...

Bien vu, c'est déjà une première réponse. Aux autres de faire mieux ! (car il y a mieux bien sûr)

Par contre, niveau éclaircissements, peut-être un peu plus de précisions sur l'effacement des distances... je vois pas à quoi ça sert, en fait... A moins que : Facile ! On résoud le problème du voyageur de commerce avec les différentes villes en considérant que les distances sont en ligne droite, et ça fait une borne inférieure parce que les distances réelles sont un peu plus longues
... bah quoi... N! c'est pas supérieur à N²... si ?

N!, c'est bien entendu supérieur à N², donc non, il est interdit de résoudre le problème du voyageur de commerce !

Concernant l'effacement des distances, effectivement, ça ne sert qu'à embrouiller tout le monde et on aurait pu s'en passer. Je voulais juste complexifier un peu plus le problème, car vous êtes tous tellement forts !

En fait, la question, c'est finalement quelle heuristique h(N) proposez vous pour résoudre le problème du voyageur de commerce selon l'algorithme A* ?

[invite06fcc10b]

C'est le problème du voyageur de commerce. C'est un problème ouvert, non?

C'est un problème qui requiert dans le cas général un temps de calcul qui varie de manière exponentielle avec le nombre de villes à visiter. En clair, si N est grand, aucun ordinateur n'est assez puissant pour trouver la solution. (= problème NP-complet pour les connaisseurs)
Mais ça n'est pas un problème "ouvert", puisqu'on sait comment le résoudre.

[yat]

Bon, maintenant que tu as implicitement autorisé à laisser de coté l'histoire de l'effacement des kilomètres (parce qu'il faut bien le dire, vu qu'on n'a plus que les coordonnées, je pense qu'on est de toutes façons obligés de considérer les distances à vol d'oiseau, ce qui n'est pas génant dans la mesure ou on cherche une borne inférieure), j'ai peut-être une borne inférieure un peu moins ridicule que mon polygone qui n'était bien entendu qu'une boutade.

Alors comme on a N points, on va forcément faire N-1 trajets menant tous d'une ville à l'autre (au minimum, évidemment. On est dans la borne inférieure, là). Je ne sais pas trop quel est le détail de la rêgle du jeu, alors je considère que le livreur choisit sa ville de départ et sa ville d'arrivée, de toutes façons après il suffit d'adapter.
Donc, N-1 trajets, en sachant qu'au départ de N-1 villes, on va choisir une ville et y aller. Dans le meilleur des cas, et surtout comme j'ai le droit de faire du N², on ira vers la ville la plus proche. Donc j'ai déjà une borne inférieure un tout petit peu plus correcte : pour chaque ville, je calcule les distances avec toutes les autres villes, je garde la plus petite. J'obtiens une liste de villes et de distances, je supprime la plus grande distance, j'additionne le reste et me voilà avec une borne inférieure calculée en N².

Bourrin et probablement loin de la meilleure borne inférieure, mais c'est tout ce que j'ai pour aujourd'hui....

[invité576543]

Mais ça n'est pas un problème "ouvert", puisqu'on sait comment le résoudre.

Je me suis mal exprimé. Je voulais dire que le calcul d'une borne inférieure avec un algo en N² (en fait avec un algo polynomial) est un problème ouvert. Ce n'est pas tellement à sa place dans "humour scientifique" ou comme énigme...

[invite06fcc10b]

Donc, N-1 trajets, en sachant qu'au départ de N-1 villes, on va choisir une ville et y aller. Dans le meilleur des cas, et surtout comme j'ai le droit de faire du N², on ira vers la ville la plus proche. Donc j'ai déjà une borne inférieure un tout petit peu plus correcte : pour chaque ville, je calcule les distances avec toutes les autres villes, je garde la plus petite. J'obtiens une liste de villes et de distances, je supprime la plus grande distance, j'additionne le reste et me voilà avec une borne inférieure calculée en N².

Bourrin et probablement loin de la meilleure borne inférieure, mais c'est tout ce que j'ai pour aujourd'hui....

Mais c'est une bonne réponse !
Il y a sans doute un peu mieux, mais à ma connaissance pas de manière fondamentale en restant en N².
Une petite remarque quand même, on peut se limiter à un calcul de distances uniquement avec les villes directement reliées par une route. En général, le nombre de connexions moyennes étant largement inférieur au nombre total de villes, on est inférieur à N².
Cela me conduit à une autre question : le nombre moyen de connexions est-il borné et si oui par quel nombre et à quelles conditions sur le réseau routier ?
En déduire une amélioration de la méthode proposée, tout en restant de l'ordre de N² ...

[invite06fcc10b]

Je me suis mal exprimé. Je voulais dire que le calcul d'une borne inférieure avec un algo en N² (en fait avec un algo polynomial) est un problème ouvert. Ce n'est pas tellement à sa place dans "humour scientifique" ou comme énigme...

Ca en fait une énigme bigrement intéressante du coup, non ?
Faut-il la déplacer dans "débats" ?
Quoi qu'il en soit, il existe quand même des solutions connues, et c'est à ces solutions que je faisais référence.

[yat]

le nombre moyen de connexions est-il borné et si oui par quel nombre et à quelles conditions sur le réseau routier ?
En déduire une amélioration de la méthode proposée, tout en restant de l'ordre de N² ...

Mmhhhh... je pense que le nombre de routes partant d'une ville ne dépend pas tellement du nombre total de villes... c'est purement des questions locales comme la taille de la ville et la proximité des villes voisines qui posent les conditions... En tout cas quand on regarde une carte routière. De là à en faire une hypothèse de travail, il n'y a qu'un bond que je n'hésite pas à effectuer.

Du coup, en exploitant ça, on peut considérer le nombre de connections comme une constante, et bingo ! Nous voilà avec un algo en N ! (Le point d'exclamation est un point d'exclamation, pas une factorielle)

Mais bon... par contre je ne vois pas commment exploiter ça pour obtenir une meilleure borne inf en N²...

[invite06fcc10b]

Mmhhhh... je pense que le nombre de routes partant d'une ville ne dépend pas tellement du nombre total de villes...

Je parle du nombre moyens de connexion, car pour une ville donnée, il peut bien entendu y avoir N-1 connexions au maximum. En revanche, le nombre moyen de connexions ...

[yat]

Je parle du nombre moyens de connexion

Mais ça revient au même, puisque l'énoncé dit qu'il y a une ville à chaque intersection de routes, non ? Si une ville A a une connexion avec une ville B, c'est qu'il y a au moins une route entre A et B, et qu'il n'y a aucune autre ville sur cette route. Donc les connexions d'une ville sont au maximum le nombre de routes qui en partent.

[invite06fcc10b]

Mais ça revient au même, puisque l'énoncé dit qu'il y a une ville à chaque intersection de routes, non ? Si une ville A a une connexion avec une ville B, c'est qu'il y a au moins une route entre A et B, et qu'il n'y a aucune autre ville sur cette route. Donc les connexions d'une ville sont au maximum le nombre de routes qui en partent.

Oui, bien sûr, mais je voulais parler du nombre moyen de connexions par ville. Simple question : peux-tu dessiner un réseau routier de N villes avec 5 connexions en moyenne par ville ? (N quelconque).
Par exemple, avec N=6 villes, peut-on construire un réseau routier de telle sorte que chaque ville soit directement accessible par une autre ville (sans ville intermédiaire) ?

[yat]

Oui, bien sûr, mais je voulais parler du nombre moyen de connexions par ville. Simple question : peux-tu dessiner un réseau routier de N villes avec 5 connexions en moyenne par ville ? (N quelconque).

N quelconque, ça me parait balaise... J'y arrive avec 54 villes et 135 routes (merci tableur ), mais je ne pense pas que ça soit possible avec N petit.

Par exemple, avec N=6 villes, peut-on construire un réseau routier de telle sorte que chaque ville soit directement accessible par une autre ville (sans ville intermédiaire) ?

Non, en tout cas pas dans le plan. Déjà avec 5 c'est impossible :Avec le problème des trois maisons reliées au gaz à l'eau et à l'électricité, ce sont les deux figures de bases qu'on doit retrouver dans un graphe pour que celui-ci ne soit pas planaire.

Je soupçonne que quel que soit le nombre de ville, il soit impossible d'avoir plus de 6 connexions par ville. C'est vers ça qu'on tend avec un pavage triangulaire du plan. Mais cette moyenne limite peut être très différente : en pavant avec des carrés on tend vers une moyenne de 4, de 3 e pavant avec des hexagones, et on peut même imaginer un réseau routier complêtement stupide ou toutes les villes sont sur une ligne continue, ce qui nous fait tendre la moyenne vers 2. Et comme avec un réseau d'une ville on n'a de toutes façons aucune connexion, je pense que tout ce que je peux dire sur la moyenne est qu'elle est comprise entre 0 et 6...

[invite06fcc10b]

Je soupçonne que quel que soit le nombre de ville, il soit impossible d'avoir plus de 6 connexions par ville. C'est vers ça qu'on tend avec un pavage triangulaire du plan.

Oui, effectivement. En fait, la démonstration se fait à partir de la formule d'Euler pour les graphes planaires et 6 de moyenne pour le degré des sommets est précisément une borne maximale d'ailleurs inatteignable.
En ce qui concerne les conditions pour qu'un réseau routier soit planaire, il faut simplement qu'il n'y ait pas de pont permettant d'éviter une intersection.

Enfin, pour revenir à la question de h(N) de complexité N², il suffit d'envisager tous les chemins permettant de visiter 2 villes (si possible sans revenir) à partir de chaque ville et de retenir les chemins les plus courts, qu'on appellera PCi. Comme ces chemins sont constitués de 2 arêtes et qu'il faut en tout N-1 arêtes pour le chemin complet, on obtient une autre borne inférieure en effectuant la somme des (N-1)/2 plus petites valeurs de PCi.
Mais il n'est pas sûr que cette borne soit meilleure que l'autre, elle est juste différente.

[yat]

Enfin, pour revenir à la question de h(N) de complexité N², il suffit d'envisager tous les chemins permettant de visiter 2 villes (si possible sans revenir) à partir de chaque ville et de retenir les chemins les plus courts, qu'on appellera PCi. Comme ces chemins sont constitués de 2 arêtes et qu'il faut en tout N-1 arêtes pour le chemin complet, on obtient une autre borne inférieure en effectuant la somme des (N-1)/2 plus petites valeurs de PCi.
Mais il n'est pas sûr que cette borne soit meilleure que l'autre, elle est juste différente.

Je ne comprends pas...
Deux villes quelconques ? Deux villes données ?
Voilà comment j'interprète ton explication : pour chaque ville, on ne cherche plus la ville la plus proche (ce que je proposais), mais la combinaison de deux villes pour laquelle le trajet parcouru est le plus court... ça nous fait une liste de paires d'arètes, on garde ce qu'il faut pour avoir le bon nombre d'arètes.

Mais du coup, là ou on était en temps constant pour tester les connexions d'une ville, on reste en temps constant, puisque pour chacune de ces connexions on teste à nouveau les connexions... une constante multipliée par une constante, ça reste une constante... on a donc toujours un algo en N. Donc j'ai pas du comprendre tes explications...

[invite06fcc10b]

Voilà comment j'interprète ton explication : pour chaque ville, on ne cherche plus la ville la plus proche (ce que je proposais), mais la combinaison de deux villes pour laquelle le trajet parcouru est le plus court... ça nous fait une liste de paires d'arètes, on garde ce qu'il faut pour avoir le bon nombre d'arètes.

Oui c'es ça.

Mais du coup, là ou on était en temps constant pour tester les connexions d'une ville, on reste en temps constant, ....

Oui, tu as raison, on reste en temps constant par ville, donc en temps linéaire total, on n'est pas en N².

[invite06fcc10b]

Oui, tu as raison, on reste en temps constant par ville, donc en temps linéaire total, on n'est pas en N².

Je dis n'importe quoi, moi. Dans le pire des cas, certains noeuds jouent le rôle de carrefours principaux et le nombre de chemins à 2 villes partant d'une ville donnée peut donc être proche de n en moyenne. En conséquence, il s'agit bien d'une complexité en O(n2).

[yat]

Je dis n'importe quoi, moi. Dans le pire des cas, certains noeuds jouent le rôle de carrefours principaux et le nombre de chemins à 2 villes partant d'une ville donnée peut donc être proche de n en moyenne. En conséquence, il s'agit bien d'une complexité en O(n2).

Là je ne te suis plus...

x étant le nombre de connections moyennes d'une ville, partant d'une ville donnée on a donc en moyenne x manières de choisir une première ville connectée, et pour chacune de ces x villes, x-1 manières en moyenne d'en choisir une deuxième...

...le fait qu'une ville puisse servir de carrefour principal et être reliée à toutes les autres ville sne change rien : plus ce carrefour aura de connections, plus ça limitera les connections des autres villes entre elles. Au final, notre moyenne ne peut de toutes façons pas dépasser 6. Donc en appliquant cette méthode, on aura bien en moyenne 30 tests à faire pour chaque ville dans le pire des cas. C'est une constante, alors on est toujours en N, non ? En tout cas je n'arrive pas à dessiner de configuration pour laquelle on a plus de 30 tests par ville à faire. Si tu en vois une...

[invite06fcc10b]

...le fait qu'une ville puisse servir de carrefour principal et être reliée à toutes les autres ville sne change rien : plus ce carrefour aura de connections, plus ça limitera les connections des autres villes entre elles. Au final, notre moyenne ne peut de toutes façons pas dépasser 6. Donc en appliquant cette méthode, on aura bien en moyenne 30 tests à faire pour chaque ville dans le pire des cas. C'est une constante, alors on est toujours en N, non ? En tout cas je n'arrive pas à dessiner de configuration pour laquelle on a plus de 30 tests par ville à faire. Si tu en vois une...

Je ne comprends pas ton pb. Supposons un cas simple avec 1 ville connectée à toutes les autres et c'est tout. Supposons qu'il y ait 100 villes. Pour 1 ville donnée quelconque, il y a donc 1 seule route pour aller au centre puis 98 possibilités. On a donc bien 98 chemins de 2 villes en moyenne à explorer, non ?

[yat]

Je ne comprends pas ton pb. Supposons un cas simple avec 1 ville connectée à toutes les autres et c'est tout. Supposons qu'il y ait 100 villes. Pour 1 ville donnée quelconque, il y a donc 1 seule route pour aller au centre puis 98 possibilités. On a donc bien 98 chemins de 2 villes en moyenne à explorer, non ?

J'ai peut-être fait un gros raccourci dans mon propos C'est vrai qu'en me relisant je ne comprends même plus ce que je voulais dire.

Je prends 6*(6-1)N parce que je ne sais pas vraiment comment borner mieux et que je me tape un peu de la constante, mais c'est vrai que c'est très maladroit de ma part.

En utilisant la méthode que tu décris on fait plusieurs fois la même opération, ce qui se voit bien dans cet exemple : on va calculer 100 fois quelle est la route la plus courte partant du point central. Mais une fois qu'on a, pour chaque ville, les deux chemins les plus court menant à une deuxième ville (ce qui se fait en temps linéaire puisque le nombre moyen de connections par ville est limité à 6), il suffit d'une deuxième passe : pour chaque ville on prend le chemin le plus court vers une deuxième ville, puis de cette ville le chemin le plus court qui n'est pas celui qu'on vient de prendre (c'est pour ça que j'en garde deux). Bon, je ne sais pas si ça va donner du (6+2)N ou du 30N ou quoi, mais en tout cas je pense qu'on reste en temps linéaire.

Ca a plus de sens comme ça ?

[invite06fcc10b]

il suffit d'une deuxième passe : pour chaque ville on prend le chemin le plus court vers une deuxième ville, puis de cette ville le chemin le plus court qui n'est pas celui qu'on vient de prendre (c'est pour ça que j'en garde deux). Bon, je ne sais pas si ça va donner du (6+2)N ou du 30N ou quoi, mais en tout cas je pense qu'on reste en temps linéaire.

Effectivement, ça réduit, bien vu.
Mais du coup, on ne pourrait pas appliquer ça 1 cran de plus pour avoir les trajets à 3 arêtes ? Hum ... ça se complique vite j'ai l'impression ...
Pas pour rien que c'est NP-complet ...

[yat]

Mais du coup, on ne pourrait pas appliquer ça 1 cran de plus pour avoir les trajets à 3 arêtes ? Hum ... ça se complique vite j'ai l'impression ...
Pas pour rien que c'est NP-complet ...

C'est sur... mais là on cherche une borne inférieure. Et c'est vrai que quel que soit N, on peut choisir de se baser sur les trajets à x arètes, le temps de calcul sera toujours linéaire par rapport à N.

Si on voulait vraiment résoudre le problème, x devrait être égal à N, et on reviendrait à la résolution brutale du problème, en temps exponentiel.