IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Calcul de différents itinéraires


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2013
    Messages
    50
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2013
    Messages : 50
    Points : 27
    Points
    27
    Par défaut Calcul de différents itinéraires
    Bonsoir,

    Je travaille sur un script qui simule la colonisation spatiale. Pour chaque planète colonisée, mon algorithme recherche ses 2 voisines les plus proches et les colonise, etc... Voici un schéma pour éclairer mes explications :
    Nom : Capture.PNG
Affichages : 245
Taille : 27,2 Ko

    Mon problème, c'est : comment calculer tous les itinéraires ? Je calcule déjà toutes les normes séparant chaque planète mais par exemple, à l'étape N, j'aurai 2^N itinéraires différents. J'aimerais pouvoir ranger tous ces itinéraires dans une matrice mais je ne sais pas comment m'y prendre...

    Voici mon algorithme :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
     
            Vector = bsxfun(@minus,P(:,1:3),Origine);
            Normes = sqrt(sum(Vector.^2, 2));
     
            [best_ways(1),idx(1)] = min(Normes);
            Normes(idx(1)) = inf;
            [best_ways(2),idx(2)] = min(Normes);
     
            P(idx(1),4) = 1;
            P(idx(2),4) = 1;
     
            planete_visitee(1,:) = P(idx(1),:);
            planete_visitee(2,:) = P(idx(2),:);
            P(idx(1),:) = P(1,:);
            P(idx(2),:) = P(2,:);
            P(1,:) = planete_visitee(1,:);
            P(2,:) = planete_visitee(2,:);
     
            Planetes_visitees = [P(1,:);P(2,:)];
     
            if all(Planetes_visitees(1,1:3)) == all(Terre(1,1:3)) || all(Planetes_visitees(2,1:3)) == all(Terre(1,1:3))
                Terre_trouvee = true;
            end
     
     
            exposant = zeros(1,100);
            exposant(1) = 2;
     
            for i = 2:length(exposant)
            	exposant(i) = exposant(i-1)*2;
            end
     
            j = 1;
            k = 3;
            l = 1;
            while Terre_trouvee == false
     
                for i = 1:exposant(j)
                    Vector = zeros(Indices(N),3);
     
                    Vector(k:end,1) = P(exposant(j)+(k - exposant(j)):end,1) - P(l,1);
                    Vector(k:end,2) = P(exposant(j)+(k - exposant(j)):end,2) - P(l,2);
                    Vector(k:end,3) = P(exposant(j)+(k - exposant(j)):end,3) - P(l,3);
     
                    Normes = sqrt(sum(Vector.^2, 2));
     
                    [best_ways(1),idx(1)] = min(Normes(k:end));
                    idx(1) = idx(1) + (k-1);
                    Normes(idx(1)) = inf;
                    [best_ways(2),idx(2)] = min(Normes(k:end));
                    idx(2) = idx(2) + (k-1);
     
                    P(idx(1),4) = 1;
                    P(idx(2),4) = 1;
     
                    planete_visitee(1,:) = P(idx(1),:);
                    planete_visitee(2,:) = P(idx(2),:);
                    P(idx(1),:) = P(k,:);
                    P(idx(2),:) = P(k+1,:);
                    P(k,:) = planete_visitee(1,:);
                    P(k+1,:) = planete_visitee(2,:);
     
                    Planetes_visitees = [Planetes_visitees;P(k,:);P(k+1,:)];
     
                    if all(P(k,1:3)) == all(Terre(1,1:3)) || all(P(k+1,1:3)) == all(Terre(1,1:3))
                        Terre_trouvee = true;
                        break;
                    end
     
                    k = k+2;
                    l = l+1;
                end
     
            j = j+1;
            end
    Aide bienvenue !
    Merci d'avance !

  2. #2
    Expert confirmé Avatar de DonQuiche
    Inscrit en
    Septembre 2010
    Messages
    2 741
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 2 741
    Points : 5 485
    Points
    5 485
    Par défaut
    Bonjour.

    La bonne réponse est tout simplement qu'il ne faut pas chercher à calculer ou stocker cette masse exponentiellement croissante de trajectoires. La bonne question est donc : que cherches-tu à faire et comment le faire sans calculer l'ensemble des trajectoires ?

  3. #3
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2013
    Messages
    50
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2013
    Messages : 50
    Points : 27
    Points
    27
    Par défaut
    Oui en fait, à un moment donné, la Terre sera trouvée par mon algorithme. Et là je dois retracer le bon chemin, celui parcouru depuis la planète d'origine jusqu'à la Terre et calculer la longueur de ce chemin.

  4. #4
    Expert confirmé Avatar de DonQuiche
    Inscrit en
    Septembre 2010
    Messages
    2 741
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 2 741
    Points : 5 485
    Points
    5 485
    Par défaut
    Puisque tu fais un balayage le mieux est de stocker pour chaque planète l'identité d'une de ses prédécesseures, par exemple la première par laquelle elle a été ajoutée. Une fois le balayage fini tu reviendras en arrière, cela te donnera un des chemins possibles.

    Si en revanche tu veux le plus court chemin, tu peux t'en approcher en choisissant à chaque étape la prédecesseure qui minimise la distance D(0 à N) + D(N à N+1). Pour ce faire il faudra stocker non seulement la prédecesseure mais en plus la distance du point de départ. C'est une optimisation locale et ça devrait donner un bon résultat pour ton problème.

    Et si tu veux faire plus élaboré je t'invite à te renseigner sur les algorithmes de recherche du plus court chemin.

  5. #5
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2013
    Messages
    50
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2013
    Messages : 50
    Points : 27
    Points
    27
    Par défaut
    Merci beaucoup, je vais faire des tests avec ta proposition.

    Edit : Cela fonctionne bien avec ta méthode de balayage. En fait chaque planète n'a qu'une seule prédécesseure. Merci en tout cas

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [XL-2011] Mêmes calculs ; tables différentes
    Par vbhdbms dans le forum Excel
    Réponses: 1
    Dernier message: 22/10/2014, 19h46
  2. [Google Maps] Calcul du meilleur itinéraire
    Par cladoo dans le forum APIs Google
    Réponses: 4
    Dernier message: 15/11/2013, 12h32
  3. Calcul avec différents pourcentages
    Par jonaszrenard dans le forum Excel
    Réponses: 5
    Dernier message: 05/10/2010, 22h39
  4. Calcul sur différents enregistrements
    Par pulpita dans le forum Requêtes et SQL.
    Réponses: 22
    Dernier message: 09/09/2010, 17h40
  5. Calcul sur différentes colonnes
    Par climz dans le forum Access
    Réponses: 4
    Dernier message: 22/05/2006, 20h00

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo