Réseau minimal

[nodjim]

Bonsoir aux ététistes présents.
Une petite enigme bien gentille.
Comment relier avec le minimum de longueur totale de routes droites toutes les villes d'un même pays ? Chaque ville doit être raccordée au moins une fois à ce réseau minimal.

[windows7]

salut

tu connais l'algo de Dijkstra ?

[nodjim]

Non, je vais regarder ce que c'est.

[nodjim]

Apparemment, cet algo sert à calculer le plus court chemin entre 2 points d'un réseau. Ce n'est pas tout à fait la question que je pose.

[windows7]

toi tu veux un graphe qui avec comme sommet les n villes c'est bien ca ?

[Doraki]

Mon algo candidat consiste à partir des n points isolés,
de prendre au hasard une composante connexe de ce qu'on a déjà construit au hasard, et de la relier au point qui est le plus proche d'elle.
Et de recommencer.

Il me semble que ça donnera toujours le même graphe à la fin, mais j'ai pas encore trop essayé de montrer que ça donne la meilleure solution.

[nodjim]

C'est ça. Moi non, plus, je n'arrive pas à prouver que c'est la solution la meilleure, bien que, quel que soit un tracé initial donné quelconque reliant les villes l'une après l'autre (sans croisement si possible, mais ça c'est facile à respecter), l'algo aboutit toujours au même résultat.

[nodjim]

Pour être plus précis:
On trace une route unique, sans croisement, qui relie toutes les villes. Ensuite, on examine chaque route: Si on la retire, on a 2 ensembles de villes séparés: On relie alors ces 2 ensembles par les 2 villes de chacun d'eux les plus proches.

[nodjim]

toi tu veux un graphe qui avec comme sommet les n villes c'est bien ca ?

Un graphe qui relie tous les points entre eux au moins une fois. Aucun point ne doit être isolé.

[fatal_error]

salut,

au hasard, et de la relier au point qui est le plus proche d'elle.

ui mais par exemple, supposons dans un repere orthornormé
une ville en (0,0), et une ville en (1,0) qui sont reliées.
on ajoute une ville en (0.4,0.1).
Alors on la relie a la ville (0,0), mais on a plus court, en reliant aussi cette ville à (1,0) au lieu de laisser la liaison (0,0)-(1,0)

Pour ma part mon algo ressemble à ca.
On a nos n villes optimalement reliées.
On prend la nouvelle ville V.
On note v_0 la ville la plus proche de V

Lier v_0,V
Pour toutes les villes v_r voisines de V
Si d(v_r,v_0)>d(V,v_0)
On supprime la liaison [v_r,v_0]
On cree la liaison [V,v_r]
/*
Ici, on préserve la connexité et on se fait un ptit optimal local. Par rapport à la ville la plus proche
*/
Finsi
FinPour
//pour les villes secondaires, on look si on peut pas casser des liaisons
Pour toutes les villes
Calculer dsortant(vr), l'arrete la plus courte sortant de chaque ville v_r
Si d(V,v_r)<dsortant(v_r)
Pour toutes les ville v_s reliées à v_r
Si v_s nest pas isolée en coupant la liaison [v_s,v_r]
Couper la liaison [v_r,s_v]
Creer la liaison [V,v_r]
Finsi
FinPour
Finsi
Finpour
Le deuxieme cas etant un peu crapuleux. Jmen suis rendu compte en prenant des ptits segments tres courts qui donnenet une espece de croissant de lune qui se referme. Si on place une ville au "detroit" du croissant, ben on peut reliée la nouvelle ville aux deux bords et rattacher un des bords à cette ville.

[fatal_error]

salut,

au hasard, et de la relier au point qui est le plus proche d'elle.

ui mais par exemple, supposons dans un repere orthornormé
une ville en (0,0), et une ville en (1,0) qui sont reliées.
on ajoute une ville en (0.4,0.1).
Alors on la relie a la ville (0,0), mais on a plus court, en reliant aussi cette ville à (1,0) au lieu de laisser la liaison (0,0)-(1,0)

Pour ma part mon algo ressemble à ca.
On a nos n villes optimalement reliées.
On prend la nouvelle ville V.
On note v_0 la ville la plus proche de V

Code: Tout sélectionner

Lier [v_0,V]
Pour toutes les villes v_r voisines de V
   Si d(v_r,v_0)>d(V,v_0)
      On supprime la liaison [v_r,v_0]
      On cree la liaison [V,v_r]
/*
Ici, on préserve la connexité et on se fait un ptit optimal local. Par rapport à la ville la plus proche
*/
Finsi
FinPour
//pour les villes secondaires, on look si on peut pas casser des liaisons
Pour toutes les villes
   Calculer dsortant(vr), l'arrete la plus courte sortant de chaque ville v_r
   Si d(V,v_r)<dsortant(v_r)
      Pour toutes les ville v_s reliées à v_r
         Si v_s nest pas isolée en coupant la liaison [v_s,v_r]
            Couper la liaison [v_s,v_r]
            Creer la liaison [V,v_r]
         Finsi
      FinPour
   Finsi
Finpour


Le deuxieme cas etant un peu crapuleux. Jmen suis rendu compte en prenant des ptits segments tres courts qui donnenet une espece de croissant de lune qui se referme. Si on place une ville au "detroit" du croissant, ben on peut reliée la nouvelle ville aux deux bords et rattacher un des bords à cette ville.

[Doraki]

Si les distances entre les villes sont toutes différentes,
la preuve consiste à dire que si on prend un point A du graphe, alors il doit être relié au point B le plus proche de A.

Si on a un arbre couvrant qui n'utilise pas cette arête,
si on ajoute A-B, on crée un cycle A-B-...-C-A, et peut retirer la liaison C-A.
Le graphe obtenu est alors un autre arbre couvrant (on peut toujours aller de A à C donc on a rien cassé), et il est plus court vu que d(A,B) un arbre couvrant minimal du graphe initial)

Si y'a des distances égales, je sais pas si ça peut tout faire foirer.

salut,

ui mais par exemple, supposons dans un repere orthornormé
une ville en (0,0), et une ville en (1,0) qui sont reliées.
on ajoute une ville en (0.4,0.1).
Alors on la relie a la ville (0,0), mais on a plus court, en reliant aussi cette ville à (1,0) au lieu de laisser la liaison (0,0)-(1,0)

On ajoute pas de ville.

Un algo qui marche (algo de prim) :
Les sommets sont {1...n}, et on a une fonction distance, d.

On prend X = {1}, Y = {2...n}
Tant que Y est pas vide, on choisit x dans X et y dans Y qui minimise d(x,y), on relie x à y, on retire y de Y et on l'ajoute à X.

[fatal_error]

On ajoute pas de ville.

Tant que Y est pas vide, on choisit x dans X et y dans Y qui minimise d(x,y), on relie x à y, on retire y de Y et on l'ajoute à X.

Ui, je vois cque tu veux dire par la. Tu les parachutes pas n'importe comment.

Pour les distances égales, je passe.

[nodjim]

A titre indicatif, il me semble que s'il reste un angle inférieur à 60° entre 2 routes à sommet commun, il y a un problème d'optimisation.

[nodjim]

Pour les égalités de distance, je dirais qu'il y a plusieurs graphes optimaux. Mais bon, l'égalité parfaite....