Recherche du plus long chemin

Bonjour KX, merci de ta réponse,

et merci pour ton explication (je ne connaissait pas le terme de "grille").

Pour le bloc, on va faire un exemple se basant sur l'image que j'ai (c'est en diagonale parce que Mind Mup ne me permet pas de créer des angles droits et je trouve ca plus clair qu'un affichage texte)

Donc, pour ce qui est de ces blocs, je veux dire que le chemin devra etre séparé d'un noeud de toute autre partie de ce même chemin

donc quand je fais : 01 -> 02 -> 12 -> 11, le 11 est adjacent a 01, ce que je ne souhaite pas
un chemin correcte selon cette règle serai plutot 01 -> 02 ->12 -> 22 -> 21. ou la aucun noeud est adjacent a tout autre noeud du chemin (a l'exception du parent évidemment).
(en fait les Noeuds qui m'interessent sont les noeuds qui ne sont pas sur le chemin, et je ne veux pas en avoir trop d'où la recherche des longs chemins)

Après, la solution du serpentin, le gros défaut c'est la diversité, et cela ne donnera pas forcément un long chemin si on déplace le noeud final : si, pour le même graphe on déplace la sortie au noeud 56 c'est mort...

(c'etait la solution que je faisait avant (sur un tableau, pas besoins de graphe pour faire ca), j'y avait rajouté des paramètres aléatoire par rapport au changement de direction, mais j'ai tout effacé pour trouvé un truc plus optimal)

Ca voudrai dire que l'heuristique d'A* serai en fonction de la taille du graphe (oui, le serpentin ne marche pas bien pour des dimensions impaires), et en fonction de l'emplacement de la sorte en fonction de sa position relative par rapport a la forme de la grille, enfin le tout donnerai une trop grosse surcharge de calculs.. (après j'ai peut-etre tord, je n'en sait rien ^^)

ah et non, l'absense de diversité viens du fait que je fais un parcours en profondeur, pas de la forme serpentin (oui, il y a Beaucoup de manière pour obtenir un chemin de taille Dim/2, et les solutions optimales il y en a une petite dizaine (j'ai pas vraiment compté, c'est chiant de se ballader dans un fichier txt de 54000 ligne :D) qui ont a peu près la même taille, donc pas que des serpentins ^^)

Pour parcours en profondeur, admettons qu'il ai trouvé un chemin de taille 50 en terminant par 97 -> 98 -> 99, la récursion va remonter jusqu'a 97 (a cause de la règle du bloc), puis le prochain sur la liste terminera par 97 -> 87 -> 88 -> 89 -> 99, donc tout le chemin parcouru jusqu'a 97 sera identique pour ces deux chemins trouvés

Qu'est-ce qui t'intéresse finalement (histoire de ne pas se fourvoyer) ?

Si j'ai bien compris, tu veux :

• le moins de "murs" possibles (noeuds qui ne sont pas sur le chemin)
• plusieurs solutions, de préférences variées
• bonnes mais pas forcément optimales
• rapides à obtenir
• que ça puisse se généraliser (dimensions, point de départ/arrivée...)

Déjà à mon avis il faut oublier A* ton problème ne s'y prête pas (recherche de maximum et pas du minimum, nombre de contraintes importantes, etc.), il va plutôt falloir sortir l'artillerie lourde et s'orienter vers les métaheuristiques.

Exactement :) Donc par exemple, un chemin sympatique que j'aimerai optenir pour cette configuration ce serai ca : (il a une longueur de 60, donc Dim/1.8)

(j'aurai peut-etre du commencer par l'image pour etre plus clair, dsl)



l'entrée est en haut a gauche, la sortie en bas a droite, les 0 représentent le chemin généré par l'algo, les autres chiffres sont les noeuds qui m'interesse et je ne veux pas en avoir beaucoup. (donc Dim*0.8/1.8 "murs" me vas tres bien)

au niveau de la diversitée, si un chemin (de 0) ressemble à plus de 66% (ce chiffre n'est pas définitif) à un autre chemin, il sera effacé.


Merci pour m'avoir orienté vers les métaheuristiques (je ne connaissait pas) mais ca a l'aire d'etre exactement ce que je recherche :)

je vais faire des recherches la dessus

(je ne peux plus editer mon message, mais 60 c'est pas vraiment Dim/1.8 (= 56) mais c'est une des solutions que mon algo a trouvé ayant une longueur supérieur a Dim/1.8)

Je pense que le recuit simulé pourrait obtenir de bons résultats dans ton cas, il ne demande pas trop de code (un peu quand même) et le mécanisme est relativement simple à comprendre. Il y a juste le paramétrage qui est un peu compliqué mais tu as déjà fait ce travail (avec Dim/1.8 & co)

Pseudo-code :

public static Solution recherche(Grille grille) {

Solution solution = new Solution(grille); // une solution quelconque
double energie = solution.energie(); // par exemple le nombre de "murs" dans la solution

// configuration (par exemple)
int limite = 10000; // nombre d'étapes max
double energieObjectif = (double) grille.dimension()/1.8; // on s'arrête si on est en dessous
double temperature = 1; // T(n+1) = T(n) * lambda, T(0) = 1
double lambda = 0.99; // lambda = 0.99 → T(n) = 0.99^n

for (int i=0; i<limite && energie > energieObjectif; i++) {
    Solution proposition = solution.voisin(); // un voisin aléatoire de la solution
    double energie2 = proposition.energie();
    temperature = temperature*lambda; // on peut choisir de faire autrement

    if (energie2 < energie // si la solution est meilleure on la garde
        // sinon on s'autorise à prendre parfois des solutions moins bonnes
        || Math.random() < Math.exp((energie - energie2)/temperature)
    {
        solution = proposition;
        energie = energie2;
    }
}

return solution;
}

Remarque : ça c'est l'algorithme générique du recuit, maintenant il faut l'adapter à ton problème, c'est à dire :

1) Déterminer la solution de départ,

solution = new Solution(grille);

. Elle peut être quelconque (exemple: le chemin le plus court entre l'entrée et la sortie), mais si elle n'est pas trop mauvaise dès le départ (obtenu par une heuristique) ça donnera de meilleurs résultats plus rapidement... Sauf que du coup tu orienteras la recherche et donc tu vas perdre en diversité.
À voir ce que tu veux le plus : diversité vs rapidité.

2) Calculer une solution voisine

Solution proposition = solution.voisin();

Quand on parle de solution voisine, ça veut dire que les deux chemins obtenus doivent se ressembler à "un" changement près. Il ne faut pas que les solutions soient trop différentes l'une de l'autre. Remarque : les voisins sont aléatoirement choisis (et il faut que ce soit rapide vu que c'est l'opération que l'on va faire à chaque tour de boucle).

Par exemple, tu peux couper ton chemin en supprimant une cellule (case bleu sur mon illustration) et tu "recolles" les deux morceaux par une "déviation" (orange) la plus courte possible.
Les deux solutions (à gauche et à droite) peuvent donc être considérées comme voisine, à la suppression d'une case (bleue) près.

Attention : une solution doit toujours être valide, on ne doit jamais obtenir de chemin qui serait faux (par exemple avec des blocs), si en calculant un voisin tu te retrouves avec une solution invalide, il faudra trouver un autre voisin valide.

Il est par exemple envisageable qu'en voulant supprimer une case (bleue), tu doives faire le ménage et supprimer plus de cases (violette) pour que ta déviation (orange) soit un chemin acceptable.
Remarque : une solution voisine peut (et doit pouvoir) être moins bonne que l'original, c'est l'algorithme du recuit qui choisira ensuite s'il accepte ou non la régression pour continuer la recherche.

Le choix des voisins est primordial dans les métaheuristiques, je t'invite à tester plusieurs fonctions de création de voisins pour voir s'il n'y en a pas une qui fonctionne mieux que les autres.

NB. il y a également du paramétrage à faire, en particulier sur la température, à voir ce que ça te donne quand tu exécutes le programme.