Quand l'élagage cesse-t-il d'être efficace dans une recherche en profondeur? J'ai travaillé sur une méthode efficace pour résoudre le problème N-Queens et je regarde la taille pour la première fois. Je l'ai implémenté pour les deux premières lignes, mais quand est-ce que ça cesse d'être efficace? Jusqu'où dois-je tailler?Taille: quand arrêter?
Le problème N-Queens est typiquement récursif. La mise en œuvre de l'élagage à une profondeur devrait signifier la mise en œuvre à n'importe quelle profondeur. La réponse dépend du type d'élagage que vous faites. Si vous élaguez pour des mouvements symétriques, il ne vaut pas la peine d'élaguer lorsque le coût de la vérification est supérieur au coût d'évaluation d'une branche entière multiplié par la probabilité que la branche soit symétrique. Pour le problème des N-Queens, la symétrie n'est probablement pas une méthode d'élagage très fructueuse après les deux premières rangées.
Une fois, j'ai vu une citation à ce sujet: «Taillez tôt, taillez souvent». Et un autre, "Ne fais rien de stupide, ne fais rien deux fois."
Je pense que le montant de la taille que vous faites doit être déterminée par vos objectifs pour le problème, ou vos limites sur N.
Je pense que vous devez décrire votre algorithme plus en détail. Je ne suis pas sûr de ce que tu veux dire par tailler. Il ne cesse jamais d'être efficace pour rejeter des chemins qui, à coup sûr, conduiront à une impasse. – IVlad