TIPE coloration de graphe et péage

Une petite question sur votre TIPE...

Modérateurs : Marc Ménétrier, Th. Zabulon

Avatar du membre
Der RHDJ
Messages : 1850
Enregistré le : sam. avr. 12, 2014 11:26 pm
Classe : Jône
Localisation : Boue

Re: TIPE coloration de graphe et péage

Message par Der RHDJ » mer. août 15, 2018 4:04 pm

Si les sommets de ton graphe représentent les voitures, tu représentes quoi par les arrêtes ?
2012-2013 : 1/2 insouciante
2013-2014 : 3/2 arrogante
2014-2015 : 5/2 aigrie ET arrogante
X2015
Coët en GU - Médaille du Mythe échelon Platine - Vaneau d'Or

Polight
Messages : 93
Enregistré le : ven. nov. 10, 2017 9:18 pm

Re: TIPE coloration de graphe et péage

Message par Polight » lun. août 20, 2018 6:48 pm

Der RHDJ a écrit :
mer. août 15, 2018 4:04 pm
Si les sommets de ton graphe représentent les voitures, tu représentes quoi par les arrêtes ?
Rien de particulier

Avatar du membre
Der RHDJ
Messages : 1850
Enregistré le : sam. avr. 12, 2014 11:26 pm
Classe : Jône
Localisation : Boue

Re: TIPE coloration de graphe et péage

Message par Der RHDJ » lun. août 20, 2018 6:51 pm

Polight a écrit :
lun. août 20, 2018 6:48 pm
Der RHDJ a écrit :
mer. août 15, 2018 4:04 pm
Si les sommets de ton graphe représentent les voitures, tu représentes quoi par les arrêtes ?
Rien de particulier
Je peux me tromper, mais je ne crois pas que les graphes marchent comme ça...
2012-2013 : 1/2 insouciante
2013-2014 : 3/2 arrogante
2014-2015 : 5/2 aigrie ET arrogante
X2015
Coët en GU - Médaille du Mythe échelon Platine - Vaneau d'Or

Avatar du membre
siro
Messages : 3212
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: TIPE coloration de graphe et péage

Message par siro » lun. août 20, 2018 6:57 pm

Magique ce topic.

PS : c'est pas (encore) un sujet de TIPE. Coloration de graphe ? Mais c'est quoi ton graphe et pourquoi tu veux le colorier ? On colorie pas pour faire joli...
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Polight
Messages : 93
Enregistré le : ven. nov. 10, 2017 9:18 pm

Re: TIPE coloration de graphe et péage

Message par Polight » jeu. août 23, 2018 1:16 pm

Der RHDJ a écrit :
lun. août 20, 2018 6:51 pm
Polight a écrit :
lun. août 20, 2018 6:48 pm
Der RHDJ a écrit :
mer. août 15, 2018 4:04 pm
Si les sommets de ton graphe représentent les voitures, tu représentes quoi par les arrêtes ?
Rien de particulier
Je peux me tromper, mais je ne crois pas que les graphes marchent comme ça...
En fait ce qui sera important pour les arrêtes ça sera surtout la coloration.

Je n'ai pas encore entièrement élaboré la problématique, mais ça sera quelque chose proche de ceci : comment la coloration de graphe peut répondre aux problèmes des péages posés par les voitures autonomes (organiser l'attribution des barrières de péages aux véhicules).
Dans le graphe, chaque sommet est un véhicule et chaque couleur est une barrière. Ainsi deux sommets relié par une arrêtes auront une couleur différentes.

J'aimerai aussi transposer cette idée aux avions et aux pistes d’atterrissage. Plus précisément, comment gérer "automatiquement" (c'est-à-dire sans intervention humaine) les pistes d'atterrissage (à l'aide des graphes et des couleurs) pour poser chaque avion.

J'attends vos réponses et votre aide. :mrgreen:

Polight
Messages : 93
Enregistré le : ven. nov. 10, 2017 9:18 pm

Re: TIPE coloration de graphe et péage

Message par Polight » jeu. août 23, 2018 1:20 pm

U46406 a écrit :
mar. août 14, 2018 6:42 pm
Le problème du péage me semble artificiel...


Plutôt creuser du côté du problème plus classique et plus problématique de l' allocation de place de stationnement dans un parking ?
(en 2D)
ou le rangement dans un entrepôt de stockage de produits ou colis ?
(en 3D, avec un chariot élévateur pour aller en hauteur)


PS Ton profil n'indique pas si tu es en MP ?
Et si oui, en MP option Informatique ?
memberlist.php?mode=viewprofile&u=61465

D'ailleurs ces deux sujets proposés par U46406 m'intéressent également, mais comment pourrais-je les exploiter ?

Polight
Messages : 93
Enregistré le : ven. nov. 10, 2017 9:18 pm

Re: TIPE coloration de graphe et péage

Message par Polight » mer. août 29, 2018 1:05 pm

Je suis toujours à la rech d'aide

Avatar du membre
Der RHDJ
Messages : 1850
Enregistré le : sam. avr. 12, 2014 11:26 pm
Classe : Jône
Localisation : Boue

Re: TIPE coloration de graphe et péage

Message par Der RHDJ » mer. août 29, 2018 2:55 pm

Je me répète, mais je pense que tu comprends mal ce qu'on peut décrire par un graphe, ou tu expliques mal ton idée.

Si tu as un graphe il faut que les sommets décrivent quelque chose, que les arrêtes décrivent quelque chose, et là ça aurait (potentiellement) du sens de le colorier.

Essaye de te poser cette question : à quelles conditions tu mets une arrête entre deux voitures ?
2012-2013 : 1/2 insouciante
2013-2014 : 3/2 arrogante
2014-2015 : 5/2 aigrie ET arrogante
X2015
Coët en GU - Médaille du Mythe échelon Platine - Vaneau d'Or

Avatar du membre
siro
Messages : 3212
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: TIPE coloration de graphe et péage

Message par siro » mer. août 29, 2018 3:09 pm

Polight a écrit :
mer. août 29, 2018 1:05 pm
Je suis toujours à la rech d'aide
Je suis toujours à la recherche de pourquoi tu veux utiliser un graphe, et ce que signifient les couleurs.

Tant que tu ne répondras pas à la question la seule chose qui va t'arriver c'est un gros mur.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Hazherty
Messages : 270
Enregistré le : lun. août 01, 2011 9:09 pm
Classe : Doctorat

Re: TIPE coloration de graphe et péage

Message par Hazherty » jeu. août 30, 2018 2:34 pm

Polight a écrit :comment la coloration de graphe peut répondre aux problèmes des péages posés par les voitures autonomes
C'est ça qui me pose problème. Tu pars du principe que tu vas utiliser cette technique (la coloration de graphe) pour savoir si/comment elle peut répondre à ce problème.

Or, l'utilisation de cette technique devrait tomber sous le sens au cours de ta démarche de modélisation puis confrontation avec les expériences/simulations :
"J'utilise ça parce que cet algo est pas adapté, celui-là presque mais c'est trop simpliste, donc si je veux pouvoir modéliser tous les effets que je considère, il faut que je modélise mon problème sous forme de graphe colorié, où mes éléments du graphe représentent chacun ça, ça et ça."

Si on te demande pourquoi utiliser des graphes coloriés, c'est parce que tu aurais systématiquement droit à cette question de la part de tes profs/examinateurs. Et il faut pouvoir y apporter une réponse argumentée basée sur le contexte et ta problématique, pas juste "c'est le sujet de mon TIPE".

Si tu n'es pas à l'aise avec la colorisation de graphes, mais que tu veux l'utiliser quand même (pour plein de bonnes raisons comme la curiosité ou l'approfondissement), alors cantonne toi à des problèmes dont il est connu qu'ils se résolvent à l'aide de cet objet.
Si tu es à l'aise, tu dois savoir si ces graphes sont utiles ou non pour résoudre le problème des voitures autonomes sur les péages (et en particulier, s'il n'existe pas de solution plus simple).

Polight
Messages : 93
Enregistré le : ven. nov. 10, 2017 9:18 pm

Re: TIPE coloration de graphe et péage

Message par Polight » sam. sept. 01, 2018 1:07 pm

Bonjour, tout d'abord merci de votre aide. Je reviens à la charge après avoir réfléchi à vos questions.
Der RHDJ a écrit :
mer. août 29, 2018 2:55 pm
Je me répète, mais je pense que tu comprends mal ce qu'on peut décrire par un graphe, ou tu expliques mal ton idée.

Si tu as un graphe il faut que les sommets décrivent quelque chose, que les arrêtes décrivent quelque chose, et là ça aurait (potentiellement) du sens de le colorier.

Essaye de te poser cette question : à quelles conditions tu mets une arrête entre deux voitures ?
J'ai pensé à la modélisation suivante. 4 voies d'autoroutes, et 6 barrières de péage. Je note les 4 voies 1, 2, 3, et 4, en allant de la droite vers la gauche et les barrières de péages, a, b, c, d, e, f, en allant de la droite vers la gauche.

Les voitures de la voie 1 ne peuvent aller que dans les barrières de péage notés a, b et c.
Les voitures de la voie 2 ne peuvent aller que dans les barrières de péage notés b, c et d.
Les voitures de la voie 3 ne peuvent aller que dans les barrières de péage notés c, d et e
Les voitures de la voie 4 ne peuvent aller que dans les barrières de péage notés d, e et f.

Tout ceci pour éviter que les voitures autonomes ne se rentrent dedans en essayant d'aller à une barrière trop loin.

Pour représenter les voitures qui arrivent au péage, j'ai pensé à utiliser une liste de flottant, ou l'unité représente le numéro de la voie, et le chiffre après la virgule représente la place de la voiture sur cette voie. Par exemple, si une voiture est la troisième sur la voie 2, elle sera dans la liste sous le nom 2.3
Et ceci est rendu possible grâce à des capteurs posés en amont sur l'autoroute.

Les couleurs sont les barrières des péages.

Et les arêtes sont les contraintes, deux voitures sont reliés par une arêtes lorsqu'elles sont en "conflit". Deux voitures sont en conflits si elles sont susceptible d'emprunter la même borne de péages (en particulier deux voitures qui sont sur la même voie sont en conflit)

Les nombres de voie et de barrières de péage ne sont là qu'à titre indicatif et pourront être modifié.

Ainsi au bout de 15 voitures (par exemple) dans la liste, je construis et colorie le graphe associé de façon optimal ce qui va attribuer chaque voiture de la meilleur des manières possibles. Ensuite je remets la liste à 0 et je recommence.

Les graphes semblent être la structure adapté pour répondre au problème grace au coloration optimal. J'ai essayé d'être le plus clair possible, qu'est-ce que vous en pensez ? :mrgreen:

Avatar du membre
-L-C-
Messages : 205
Enregistré le : dim. mai 25, 2008 9:55 pm
Classe : Ingénieur (ENSIIE)

Re: TIPE coloration de graphe et péage

Message par -L-C- » mar. sept. 04, 2018 3:48 pm

Pour représenter les voitures qui arrivent au péage, j'ai pensé à utiliser une liste de flottant, ou l'unité représente le numéro de la voie, et le chiffre après la virgule représente la place de la voiture sur cette voie. Par exemple, si une voiture est la troisième sur la voie 2, elle sera dans la liste sous le nom 2.3
Les flottants, pas une bonne idée. Représente plutôt par un couple de deux entiers. Dans ton exemple, la voiture sera notée (2,3). Pourquoi ? Tout simplement parce que l'ordre est clair :
(2,3) est bien < à (2,17) et (2,3) est bien != de (2,30)
Ce qui n'est pas du tout le cas avec les flottants.
Les couleurs sont les barrières des péages.
Et les arêtes sont les contraintes, deux voitures sont reliés par une arêtes lorsqu'elles sont en "conflit". Deux voitures sont en conflits si elles sont susceptible d'emprunter la même borne de péages (en particulier deux voitures qui sont sur la même voie sont en conflit)
Ok ok si je comprend bien ta modélisation :
- un noeud est une voiture
- une arête est un conflit
- la couleur associée au noeud correspond à la borne de péage prise par la voiture

A quel moment tu modélises le fait que ta voiture (2,1) ne puisse pas avoir la couleur 'a' ou 'e' ou 'f' ?
Ainsi au bout de 15 voitures (par exemple) dans la liste, je construis et colorie le graphe associé de façon optimal ce qui va attribuer chaque voiture de la meilleur des manières possibles. Ensuite je remets la liste à 0 et je recommence.
Qu'appelles-tu optimum ? C'est de minimiser le temps d'attente moyen par voiture ? Parce qu'il y a bien quelque chose dont tu n'as pas parlé c'est que le problème possède une dimension temporelle...
Quid de la 16eme voiture, on oublie carrément les 15 précédentes ? Alors pourquoi 15 ? Pourquoi ne pas choisir 1 quitte à choisir arbitrairement ? Dans ce cas ton problème devient beaucoup plus facile :mrgreen: . Je comprend bien que tu as choisi 15 arbitrairement mais j'essaye de te faire comprendre que la remise à zéro de ton graphe est en soit un problème.
Les graphes semblent être la structure adapté pour répondre au problème grace au coloration optimal. J'ai essayé d'être le plus clair possible, qu'est-ce que vous en pensez ? :mrgreen:
Tu ne m'as pas convaincu :(
Modifié en dernier par -L-C- le mar. sept. 04, 2018 4:04 pm, modifié 1 fois.
"L'enfant est le père de l'homme" (William Wordsworth)

Avatar du membre
siro
Messages : 3212
Enregistré le : dim. mai 01, 2016 8:09 pm
Classe : Cassandre

Re: TIPE coloration de graphe et péage

Message par siro » mar. sept. 04, 2018 4:03 pm

Polight a écrit :
sam. sept. 01, 2018 1:07 pm
Les graphes semblent être la structure adapté pour répondre au problème grace au coloration optimal. J'ai essayé d'être le plus clair possible, qu'est-ce que vous en pensez ? :mrgreen:
Je pense que pour le moment tu es en train d'essayer de pipoter et de nous arnaquer. Ton discours tient pas trois minutes contre un jury, et tu cours droit dans un mur.

Désolé du ton sec, mais franchement on dirait que tu essayes de force de faire coller un outil avec un problème concret même si la modélisation est ultra artificielle. Trouve un autre outil ou un autre problème à régler. En plus c'est pas comme si ça manquait les exemples d'application de la coloration de graphe : https://fr.wikipedia.org/wiki/Coloratio ... pplication

Après, je dis pas que ton problème est pas reliable à de la CDG, mais va falloir être plus convainquant. Parce que j'ai beau retourner le problème dans tous les sens, les voitures qui vont dans un péage ça me fait plus penser à de la théorie des tresses qu'à de la coloration de graphe.

Bref, en clair : la modélisation c'est capital. Si tu en fais une artificielle comme celle-là, c'est la bulle directement.
Chaque vénérable chêne a commencé par être un modeste gland. Si on a pensé à lui pisser dessus.

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité