Le test avec les villes désordonnées ne fonctionne pas

[MathieuSoysal]

J'ai découvert un problème sur le fonctionnement de l'algo BrutForce de ma branche en faisant des tests.
Le problème est que je ne suis pas certains que la suite 0453120 soit réellement le parcours le plus court, des calcules sont nécessaire pour effectuer la vérification.
L'algo renvoi le parcourt de villes suivant : "0123540"
Voici le code du Test en question :

   @Test
    public void test_ParcourOptimum_Pour_6villes_desorde() {

        Pays pays = new Pays(6);

        brutForce = new BrutForce(pays);

        pays.setPositionVille(0, new Position(2, 2));
        pays.setPositionVille(4, new Position(2, 3));
        pays.setPositionVille(5, new Position(2, 4));
        pays.setPositionVille(3, new Position(2, 5));
        pays.setPositionVille(1, new Position(2, 6));
        pays.setPositionVille(2, new Position(2, 7));


        brutForce.recherche();

        assertEquals("0453120", brutForce.getParcour().getVillesEmprunté());

    }

Posté ici les résultat obtenue par vos algorithmes à fin de facilité les comparaison.
Le lien du commit.

[Matthias-DELON]

Dans ce cas là, le parcours le plus court est bien "0453120". En ce qui me concerne mon algorithme passe parfaitement le test que j'ai dut remanier pour qu'il puisse être compatible avec mon implémentation.
Voici mon test:

    Graphe g;
    Resolveur r;

    @Test
    public void testBruteForce1(){
        g = new Graphe(7, 6);

        g.getOneSommet(0).setCoords(2,2);
        g.getOneSommet(4).setCoords(2,3);
        g.getOneSommet(5).setCoords(2,4);
        g.getOneSommet(3).setCoords(2,5);
        g.getOneSommet(1).setCoords(2,6);
        g.getOneSommet(2).setCoords(2,7);

        r = new Resolveur(g, g.getOneSommet(0).getVille());

        Trajet t = r.bruteForce();

        assertEquals("[0, 4, 5, 3, 1, 2, 0]", t.toString());

    }

[MathieuSoysal]

Je propose que l'on fusionne nos algos pour que l'on soit sur la même longeur d'onde et avoir un résultat final digne de se nom, j'ai crée un projet "fusion des algos" à fin de mieux structurer nos idées.

Je propose que l'on recrées un tout nouveau programme à partir du tien et du mien, en utilisant les instructions mit dans le projet fusion.

Le lien du projet fusion

[MathieuSoysal]

problème résolu

validation du test

Je suis parti sur l’hypothèse qu'il y ai plusieurs parcourt optimum possible.
Alors j'ai pris la distance du premier parcours et vérifier s'il n'a pas varié lors des changements de numéros de villes :

    @Test
    public void test_ParcourOptimum_Pour_6villes_desorde() {


        Pays pays = new Pays(6);
        
        brutForce = new BrutForce(pays);

        pays.setPositionVille(0, new Position(2, 2));
        pays.setPositionVille(1, new Position(2, 3));
        pays.setPositionVille(2, new Position(2, 4));
        pays.setPositionVille(3, new Position(2, 5));
        pays.setPositionVille(4, new Position(2, 6));
        pays.setPositionVille(5, new Position(2, 7));


        brutForce.recherche();

        double distanceMinimum= brutForce.getParcour().getDistance();


        pays.setPositionVille(0, new Position(2, 2));
        pays.setPositionVille(4, new Position(2, 3));
        pays.setPositionVille(5, new Position(2, 4));
        pays.setPositionVille(3, new Position(2, 5));
        pays.setPositionVille(1, new Position(2, 6));
        pays.setPositionVille(2, new Position(2, 7));


        brutForce.recherche();

        assertEquals(distanceMinimum, brutForce.getParcour().getDistance());

    }

Le test à étais validé avec sucés les deux renvoient 10 comme distance parcourue.

vérification des résultats

Donc je vérifie si le résultat concorde bien avec la distance parcourue :

Vérification du parcourt "0453120"

• première étape du parcourt : ville 0 à 4 = 1
• deuxième étape du parcourt : ville 4 à 5 = 1
• troisième étape du parcourt : ville 5 à 3 = 1
• quatrième étape du parcourt : ville 3 à 1 = 1
• cinquième étape du parcourt : ville 1 à 2 = 1
• sixième étape du parcourt : ville 2 à 0 = 5

Le résultat retourné est égal à 10.

Vérification du parcourt "0123540"

• première étape du parcourt : ville 0 à 1 = 4
• deuxième étape du parcourt : ville 1 à 2 = 1
• troisième étape du parcourt : ville 2 à 3 = 2
• quatrième étape du parcourt : ville 3 à 5 = 1
• cinquième étape du parcourt : ville 5 à 4 = 1
• sixième étape du parcourt : ville 5 à 0 = 1

Puis nous faisons la somme de toutes les étapes du parcourt, ce qui nous donne bien 10.

Conclusion

Donc il y a bien plusieurs parcourt minimum possible au sein d'un même graphe.
Le problème ne venais donc pas du programme mais du test qui partais de l’hypothèse qu'il n'y ai qu'un parcourt minimum possible, ce qui n'est pas forcément vrais pour tous les graphes.

Ces tests mon aussi permis de trouver un problème au sein du programme dans la branche Matthias Delon, le programme retourne une distance de 3 ce qui est impossible car la distance minimum entre deux villes est de 1 et il y a 6 villes.

Matthias Delon tu peux faire un issues à se sujet, si tu en juges nécessaire.