Quelle est la taille du faisceau représenter dans le faisceau de l'algorithme de recherche?
J'ai une question à propos de la faisceau de l'algorithme de recherche.
Disons que n = 2
(le nombre de nœuds que nous allons développer à partir de chaque nœud). Donc, au début, nous avons seulement la racine, avec 2 nœuds que nous étendre. Maintenant, à partir de ces deux nœuds, nous développerons deux de plus. Donc, pour le moment, nous disposons de 4 feuilles. Nous allons continuer comme cela jusqu'à ce que nous trouver la réponse.
Est-ce de cette manière faisceau des travaux de recherche? Est-il développer n = 2
de chaque nœud, ou il garde 2 nœuds feuilles à tous les temps?
J'ai l'habitude de penser que n = 2
signifie que nous devrions avoir 2 nœuds actifs à partir de chaque nœud, pas deux pour l'ensemble de l'arbre.
OriginalL'auteur Dvorog | 2014-03-08
Vous devez vous connecter pour publier un commentaire.
Dans le "standard" faisceau de recherche de l'algorithme, à chaque étape, le nombre total des nœuds que vous avez actuellement les "connaître" est limitée et NON le nombre de nœuds que vous allez suivre à partir de chaque nœud.
Concrètement, si
n = 2
, cela signifie que la "poutre" sera de taille au plus 2, en tout temps. Si, au départ, vous commencez à partir d'un nœud, puis vous découvrez tous les nœuds qui sont accessibles à partir d'elle, mais jetez tous, mais deux, et terminer l'étape 1 à 2 nœuds. À l'étape 2, vous disposez de deux nœuds, et vous permettra d'élargir à la fois, et à rejeter tous les nœuds de nouveau, à l'exception exactement 2 nœuds (au total, pas les uns!). Dans les prochaines étapes, de la même façon, vous pouvez conserver 2 nœuds après chaque étape.Choisir le nœud à conserver est généralement fait par certains heuristique fonction qui évalue le nœud qui est le plus proche de la cible.
Noter que le faisceau de l'algorithme de recherche n'est pas complète (c'est à dire, il ne peut pas trouver une solution s'il en existe) ni optimale (c'est à dire qu'il ne peut pas trouver la meilleure solution). La meilleure façon de voir ce qui est témoin que lorsque
n = 1
, il réduit en fait à le meilleur de la première recherche.OriginalL'auteur amit
L'image ci-dessus, dit tout. Notez qu'à chaque étape(colonne dans l'image) seulement beam_size nœuds de sortie, qui sont sélectionnés par une méthode de tri et le reste sont rejetés.
Et ici est un très intuitive mise en œuvre que j'ai fait, et j'espère que ça aide.
Source de la photo: http://opennmt.net/OpenNMT/translation/beam_search/
OriginalL'auteur lerner