Pipelines de combinaison
Sept expériences de recherche nommées qui visent le score, chacune un pipeline plutôt qu'un algorithme unique : elle construit un plateau avec un moteur, puis le relève ou l'achève avec un autre. À leurs côtés, deux constats décortiquent la machinerie sur laquelle les pipelines s'appuient. Chaque page consigne son idée, son plateau et les questions qu'elle laisse ouvertes.
par Raphaël Anjou
Lancer la même recherche en faisceau selon neuf ordres de parcours différents, pour qu'elle atterrisse dans des régions distinctes au lieu de toujours converger vers la même. L'ordre en zigzag a trouvé un plateau 458 inédit.
Fixer une bordure parfaite, puis explorer l'intérieur en traitant les arêtes de la bordure comme des contraintes dures dès la toute première case.
Poser d'abord une bordure parfaite, puis résoudre le plateau vers l'intérieur, anneau par anneau, chaque anneau comme un problème d'affectation sur les pièces restantes.
Décider à l'avance non pas quand un plateau peut casser, mais où : confiner chaque désaccord à une forme de cellules choisie, et chercher la meilleure forme.
Une bordure parfaite de 60 pièces n'est pas un objet rigide. Chaque cadre entièrement apparié admet exactement 45 échanges libres à coût de bordure nul ; un tiers des cadres parfaits ne peuvent même pas démarrer l'intérieur, et un seul échange libre ranime chacun d'eux.
Lancer des centaines de courtes recherches bon marché sur le plateau, ne garder que les départs les plus profonds, et faire monter les survivants à travers des tours de plus en plus longs.
Une revue vérifiée plus des mesures appariées : aucune astuce par nœud ne bat la largeur brute du faisceau à temps de calcul égal. Les deux seuls additifs qui survivent sont la randomisation des clés de troncature exactement à égalité (gratuite) et le rééchantillonnage SMC des survivants (petit mais significatif).
Découper le plateau en petits blocs, résoudre chacun jusqu'à l'optimum prouvé, puis les recoller en payant les coutures au lieu de les interdire. En partant de zéro, sans record à recopier, la méthode atteint 448.
Construire tout le plateau depuis zéro, sans cadre pré-posé, par étapes, en laissant la bordure émerger en dernier des pièces restantes.