Les algorithmes gloutons.

Les stations essences.

Une voiture veut parcourir un trajet de 2000 km, son réservoir ne lui permet de faire que 300 km avant de refaire le plein (on va dire que la voitire est électrique), On donne une table de stations sur le trajet et la distance de celles ci au point de départ.


	
Exercices
	
    
	
  1. Quelle est la stratégie gloutonne permettant d'avoir une réponse optimale au problème.
    2. 
	
  2. Si on est à une station, expliquer clairement les choses à faire pour trouver la station suivante.
    3. 
	
  3. Compléter la fonction suivante(table,indice_derniere) qui va donner la station située après la station d'indice indice_derniere la plus éloignée tout en restant à moins de 300 km de celle ci, si ce n'est pas possible la fonction doit retourner -1.  Ici vous avez deux choix : vous pouvez considérer que la table est pré classée et dans ce cas il suffit d'examiner les indices après indice_dernier où examiner tous les indices de la table à chaque fois.
    4. 
	
    
	
  4. En vous aidant de la fonction précédente faire une fonction qui va donner la liste des stations, obtenue grâce à l'algorithme glouton, où la voiture doit faire le plein. Il suffit d'appliquer la fonction précédente tant que la distance de la station à la fin est supérieure à 300 km et de stocker les stations successives dans une liste (vous pouvez utiliser append ou concaténer).
    5. 
	

	

	
Exercices
		
Comme nous devons trier le tableau avec un tri du programme la méthode est en \(\Theta(n^2)\) (n nombres de stations), alors qu'en examinant à chaque fois la table on obtient un algorithme en  \(\Theta(kn)\) (k nombre de solutions) donc au pire il est en \(\Theta(n^2)\). Trier la table avec un algorithme du programme peut être contre productif si il y a a peu de solutions par rapport au nombre de stations.
 
	

	Solution stations

	
Les spectacles.

	
Le fichier spectacle-liste.csv contient une liste de 42 concerts avec l'heure du début et l'heure de fin de chacun (1830 signifie 18h30). Comme la salle ne contient qu'une scène, un seul concert peut avoir lieu à la fois. 

	
Exercices
	
    
	
  1. Rappeler comment obtenir le nombre maximum de spectacles et un programme qui l'accompagne.
    2. 
	
  2. Importer le fichier en utilisant la bibliothèque csv (voir Base de données).
    3. 
	
  3. Facultatif mais hautement recommandé : formater la table.
    4. 
	
  4. Faire une fonction qui va trier les données en fonction de l'heure de fin du programme. (utiliser un des deux tris du programme)
    5. 
	
  5. Faire une fonction suivant(table,indice_dernier) qui suppose que la table est triée et qui va donner le plus petit indice du spectacle commençant après (ou égal) la fin du spectacle d'indice indice_dernier. Si il n'y a pas de spectacle commençant après la fonction doit retourner -1.
    6. 
	
  6. Donner les spectacles qu'il faut programmer pour en avoir le plus en utilisant l'algorithme glouton (vous pouvez par exemple faire une fonction qui va stocker le nom des spectacles dans un tableau et le retourner à la fin.)
    7. 
	

	

Solutions spectacles

	
	
Le voyageur de commerce.

	
On utilisera le début du programme suivant ainsi que le fichier à dézipper CSV des villes, pour connaître la distance à vol d’oiseaux d'une ville à une autre il suffit de faire distance("Wissembourg",Strasbourg") par exemple.

	

	
On se donne une suite de villes sous forme de tableau, par exemple ensemble_villes = ['Strasbourg','Gambsheim','Lauterbourg','Wissembourg'] est le but est d'utiliser l’algorithme glouton pour avoir un ordre de passage au problème du voyageur de commerce qui commence à la première ville du tableau (ici Strasbourg).

	
Pour savoir si une ville à déjà été visitée, on utilise un tableau de Bool,  visite = [True, False, False, False], qui va indiquer si une des villes a déjà été visitée.

	
Exercices
	
    
	
  1. Faire une fonction prochaine(ensemble_villes,visite, ville) qui va indiqué l'indice de la ville du tableau villes qui n' a pas déjà été visitée la plus proche de la ville donnée, la fonction retourne None si toutes les villes ont déjà été visitée.
    2. 
	
  2. Faire une fonction qui va donner le chemin du voyageur de commerce pour une liste de villes données et la distance du trajet.
    3. 
	
	

	

	Solutions ville

	
Remarque
	
Si vous voulez avoir une solution non optimale avec l'algo glouton, essayez ["Gambsheim","Strasbourg","Haguenau","Wissembourg","Lauterbourg"].

	
On rapelle que l'algo donne une solution que l'on espére pas trop mauvaise rapidement, l'algo dynamique (qui donne une solution optimale) a un temps raisonnable tant que le nombre de villes ne dépasse pas 20.