[Etudes Supérieures] Codage SAGE, théorie des graphes

100101110001

[Etudes Supérieures] Codage SAGE, théorie des graphes

Messagepar steph1688 le 30/11/2016 à 00:06

Bonsoir,

Désolée de vous déranger, je suis plus une adepte du département mathématique en temps normal, mais je pense me retrouver devant un problème de codage (pour cette partie de l'exercice) par conséquent je vais tenter de venir vers vous pour voir ce que vous pouvez éventuellement en penser.

Pour faire simple, je vous joint l'ensemble du projet que je suis sencée réaliser d'ici janvier.

Le principe (et ce que veut mon prof dans un premier temps), est que je traite le problème sur une plus petite matrice (5X5 plutot que 10X10).
L'idée est d'avoir un damier avec des obstacles et pouvoir aller d'un point A a un point B avec le chemin le plus court . Mais j'en suis loin pour le moment.

Mais avant tout cela, je dois tracé le graphe associé au problème et trouver un algorithme qui me permettra de le passer sur du 10X10 après.

Pour l'instant on en est la :

J'ai une matrice :

M=matrix(5,5,[1,1,1,1,1,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1]);M

Lorsque j'essaie

print M[2,3]
ça m'écrit bien 0

for i in [0..4] :
for j in [0..4] :
print M[i,j]

ça m'affiche la liste des coefficient de la matrice


G = Graph()
a, b = var('a b')
for i in [0..4] :
for j in [0..4] :
a = i
b = j
' '.join(['M[', str(a) + ',' + str(b), ']'])
G.add_vertex(' '.join(['M[', str(a) + ',' + str(b), ']']))

J'ai la liste des 25 sommets de la forme 'M[0,0]' jusqu'à 'M[4,4]'

show(G)

J'ai les 25 sommets qui s'affichent

L'objectif maintenant est de réussir a faire un algorithme qui balaye la matrice, et qui ajoute un arc d'un sommet a un autre si le voisin du sommet étudié est égale à 1.
Sachant que les voisins en question peuvent être a gauche, a droite, au dessus, en dessous, mais également en diagonale.

Un sommet est identifié en fonction de sa place dans la ligne et dans la colonne...

11111
10001
10001
11111
11111

le 1 en rouge est sur la 1ère ligne , 3ème colonne...

ses voisins pour l'algorithme qui m'intéresse sont du coup :
i , j+1 = 1
i+1 , j+1 = 0
i+1 , j-1 = 0
i+1 , j-1 = 0
i-1 , j-1 = 1

donc il faudrait rajouter un arc entre mon sommet que j'étudie et les sommets (i , j+1) et (i-1 , j-1)

Le GROS problème que j'ai du coup c'est comment le transformer en algorithme sachant que j'en ai pour ainsi dire jamais fait.
Certes je suis en train de tourner sur tous les sites que je peux trouver mais je rame.

Je suis partie sur ça pour le moment :

for i in [0..4] :
for j in [0..4] :
(pour donner mes valeurs à i et j)

C'est l'instruction du if qui me gène du coup...

On peut déjà dire que si le sommet = 0, forcément il n'y aura pas d'arc lui arrivant dessus (pas besoin de l'étudier en qq sorte)
Ensuite si le sommet = 1, des arcs peuvent lui arriver dessus si certains de ses voisins sont égaux à 1 aussi...


if voisin de M[i,j] = 1 et M[i,j] = 1 alors on ajoute un arc (je sais que ce n'est pas du codage, j'essaie juste d'éclaircir les choses...)

Je pensais faire qqch du style, si l'addition du sommet "étudié" et de son voisin = 2, alors on trace un arc.

a, b, c, d, A, B = var('a b c d A B')
for i in [0..4] :
for j in [0..4] :
a = i
b = j
c = i
d = j+1
j+1<=4
if M[a,b]+M[c,d]==2 :
A=' '.join(['M[',str(a) + ',' +str(b), ']'])
B=' '.join(['M[',str(c) + ',' +str(d), ']'])
A
B

J'ai essayé pour un cas particulier avec juste une sorte de voisins, le "j+1", mais j'ai des intructions étrange qui s'affiche et des messages d'erreurs...

Je sais que ce n'est peut être pas très clair, mais j'espère que vous comprendrez ce que j'essaie de faire en espérant que cela pourra me servir pour réaliser le projet ci-joint.

Merci d'avance
Pièces jointes
Projet 2016-2017.pdf
(122.69 Kio) Téléchargé 13 fois
steph1688
hyper actif
 
Messages: 514
Inscrit le: 20/10/2013 à 21:28
profil: Elève

Retourner vers Informatique

Qui est en ligne ?

Utilisateurs parcourant actuellement ce forum : Aucun utilisateur inscrit et 1 invité