Poste de recherche

Recherche heuristique bidirectionnelle de front à front avec des expansions de nœuds quasi-optimales

Il est bien connu que tout algorithme de recherche heuristique unidirectionnelle admissible doit développer tous les états dont la valeur f est inférieure au coût de la solution optimale lorsqu'il utilise une heuristique cohérente. De tels états sont appelés "sûrement étendus" (s.e.). Une étude récente a caractérisé les paires d'états s.e. pour la recherche bidirectionnelle avec des heuristiques cohérentes : si une paire d'états est s.e., alors au moins un des deux états doit être étendu. Cet article dérive une limite inférieure, VC, sur le nombre minimum d'expansions requises pour couvrir toutes les paires s.e., et présente un nouvel algorithme de recherche heuristique bidirectionnelle frontale admissible, Near-Optimal Bidirectional Search (NBS), qui est garanti de ne pas faire plus de 2VC expansions. Nous prouvons également qu'aucun algorithme frontal admissible n'est meilleur que 2VC dans le pire des cas. Les résultats expérimentaux montrent que NBS rivalise avec ou surpasse les algorithmes de recherche bidirectionnelle existants, et surpasse souvent A* également.

Derniers documents de recherche

Connectez-vous avec la communauté

Participez à l'écosystème croissant de l'IA en Alberta ! Les demandes de conférenciers, de parrainage et de lettres de soutien sont les bienvenues.

Explorer la formation et l'enseignement supérieur

Vous êtes curieux de connaître les possibilités d'études auprès de l'un de nos chercheurs ? Vous voulez plus d'informations sur les possibilités de formation ?

Exploiter le potentiel de l'intelligence artificielle

Faites-nous part de vos objectifs et de vos défis concernant l'adoption de l'IA dans votre entreprise. Notre équipe Investissements & Partenariats vous contactera sous peu !