Crowdly
Додати до Chrome
Pb scientifique info. (MESIIN240125)
Шукаєте відповіді та рішення тестів для Pb scientifique info. (MESIIN240125)? Перегляньте нашу велику колекцію перевірених відповідей для Pb scientifique info. (MESIIN240125) в learning.devinci.fr.
Отримайте миттєвий доступ до точних відповідей та детальних пояснень для питань вашого курсу. Наша платформа, створена спільнотою, допомагає студентам досягати успіху!
Qu'est-ce qu'un trajet dit "parasite" ?
Soit G un graphe orienté modélisant des trajets entre des villes, défini par :
- V(G) l'ensemble des nœuds, chaque nœud
modélisant une ville
- E(G) l'ensemble des arcs. Le poids w(e) associé à chaque arc e
∈
E(G) modélise
au coût de déplacement entre deux villes.
Dans ce cadre, en quoi consiste de résoudre le problème du voyageur de commerce ?Soit la matrice de coûts réduite suivante :
Quelle est la valeur du regret maximal (pas sa position) ?
Écrire un nombre entier.
Dans l'algorithme de Little, une fois que l'on a calculé tous les regrets dans la matrice réduite, quel trajet choisit-on pour la prochaine étape de séparation ?
On considère le début d'un arbre de recherche construit par l'algorithme de Little.
La racine a été évaluée à 1000. On choisit de séparer le problème sur le trajet AB, de regret 100.
Quelle est la valeur du nœud ?
Entrez un nombre.
Nous sommes au cours de l'exécution de l'algorithme de Little.
Un noeud vient d'être évalué, et nous avons identifié le projet trajet qui fera l'objet de la prochaine séparation : AB.
Nous allons évaluer le noeud de type "Trajet AB inclus". Pour cela, nous devons modifier la matrice de coûts.
Quelle opération doit-on réaliser sur cette matrice ?
Cocher toutes les réponses possibles. Attention : les mauvaises réponses donnent lieu à un malus.
On considère le début d'un arbre de recherche construit par l'algorithme de Little.
La racine a été évaluée à 1000. On choisit de séparer le problème sur le trajet AB, de regret 100.
Quelle est la valeur du nœud ?
Entrez un nombre.
Soit n le nombre de villes dans le problème du voyageur de commerce.
Il n'existe pas d'algorithme capable de résoudre ce problème en temps polynomial par rapport à n.
Soit un problème de voyageur de commerce avec 4 villes : A, B, C, D.
Au cours de l'exécution de l'algorithme de Little, on a déjà inclus les trajets AB et BC.
Quel trajet parasite faut-il éliminer à ce stade ?
Écrivez simplement 2 lettres, sans aucun autre caractère.
Quel algorithme avez-vous implémenté pour résoudre le problème du voyageur de commerce ?