1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
|
# -*- coding:Utf-8 -*-
# xxxx -x*x- coding:Latin-1 -*-
# Enoncé de l'exercice : Forum développer.com, message posté par petitours.
#
def ff_lire_data(fic ) :
"""
Lit le fichier de data,
ligne 1 = timeout,
lignes suivantes = pour chaque paquet, 2 colonnes (adresse,longueur)
"""
with open(fic, 'r') as nf :
timeout = int ( nf.readline().split(',')[0] )
les_adresses = [] # Les adresses de tous les paquets
les_longueurs = [] # et leur longueur
for i, lig in enumerate(nf):
ch_adresse, ch_longueur, ch_filler = lig.split(',') # split renvoie des chaines ; J'ai besoin de filler, car mon fichier contient une VIRGULE à la fin de chaque ligne.
les_adresses.append( int (ch_adresse)) # Adresse
les_longueurs.append(int (ch_longueur)) # Longueur
print ('fin de fichier')
# close implicite grace au with open()
return ( [ timeout , i1 , les_adresses, les_longueurs ] ) # Timeout, nbre de paquets, plus 2 tableaux addr et longueurs.
# **********************************************************************************************************
# **********************************************************************************************************
def ff_calcule_cout( adresse_debut, adresse_fin, qtimeout) :
"""
Calcul du coût de transmission d'un groupe de données. ---------------------------------------
"""
cout_formule_numero_1 = 12 + 1.04 * ( 5+ adresse_fin - adresse_debut +1 )
cout_formule_numero_2 = 12 + qtimeout
return max ( cout_formule_numero_1, cout_formule_numero_2)
# **********************************************************************************************************
# **********************************************************************************************************
def affiche_en_clair(qscenario, tb_adresse, tb_longueur) :
"""
Fonction qui va afficher en clair les endroits où il faut séparer les paquets
"""
les_0_1 = qscenario[0]
print ( "$$$$$ $$$$$ $$$$$ Syntèse scénario $$$$$ $$$$$ $$$$$")
debut_lot = tb_adresse[0]
for i in range(len(les_0_1) ) :
if les_0_1[i] == 1 :
fin_lot = tb_adresse[i] + tb_longueur[i] - 1
print ( " Lot à transférer = de l'adresse ", debut_lot, " à ", fin_lot)
debut_lot = tb_adresse[i+1]
# **********************************************************************************************************
# Programme principal ************************************************************************************
"""
On a des 'PAQUETS', disons 1000 paquets par exemple. Chaque paquet est défini par une ADRESSE et une LONGUEUR.
Les (adresse,longueur) des paquets sont initialisés par lecture d'un fichier CSV.
Dans l'énoncé de départ, les PAQUETS sont des emplacements-mémoires d'un HHT. Et on veut récupérer le contenu de ces emplacements mémoire
(on peut éventuellement récupérer aussi des emplacements non utiles, on saura gérer)
On peut lancer des instructions à ce HHT, pour lui dire : 'Envoie moi les données entre l'adresse A et l'adresse B
Le protocole de communication impose B <= A +250 ( on aura une variable longueur_max =250 dans le programme, pour pouvoir éventuellement modifier ce paramètre)
Le coût de tranfert du LOT [A,B] est donné par une fonction FF_CALCULE_COUT ;
ce coût dépend bien sûr de B-A, mais aussi d'une autre variable QTIMEOUT, lue dans le fichier d'input. (Première ligne du fichier de description des paquets)
L'objectif de ce traitement est de chercher comment regrouper les PAQUETS en LOTS, pour minimiser le coût total de transfert des données.
exemple : Si on doit transférer le PAQUET addr=1000, Lg=4 et le paquet addr=1020, lg = 2, on a le choix entre transférer ces 2 paquets en 2 LOTS séparés,
ou bien transférer le LOT de longueur 22 , commençant à l'adresse =1000.
Selon qTimeout, c'est une option ou l'autre qui sera la plus avantageuse.
Comme dit plus haut, je recense dans TB_SCENARIO tous mes sénarios (toutes les branches de l'arbre)
Je prends tous mes paquets (ils sont classés sur ADRESSE CROISSANTE dans le fichier CSV) ; et pour chaque paquets, j'ai 2 options :
le PAQUET en cours sera envoyé dans le même lot que le paquet suivant, ou pas.
Pour décrire un Scénario de façon non-équivoque, il me suffit donc d'un tableau de booléens :
0 = le paquet en cours est envoyé dans le même LOT que le paquet suivant
1 = le paquet en cours n'est pas envoyé dans le même LOT que le paquet suivant.
Mais pour faciliter les traitements, je mémorise en plus pour chaque scénario quelques variables supplémentaires (coût cumulé par exemple)
Quand à un moment de mon analyse, j'ai plusieurs scénarios qui tous prévoient de regrouper des LOTS entre le paquet 0 et le paquet N, et de faire une coupure après ce paquet N,
je peux comparer les coûts de ces scénarios, et garder un seul de ces scénarios, le plus économique.
Quelles que soient les façons dont on associera les paquets au delà ce ce paquet N, ça ne changera rien au résultat partiel.
Grâce à cet écrémage, le nombre de branches à explorer reste très faible (250 max grâce à la limite longueur_max=250, mais en fait beaucoup plus faible)
Sans cet écrèmage, on aurait 2^^nb_paquets scénarios à analyser : pas réalisable.
"""
if __name__ == '__main__':
# 1. Initialisation des données --------------------------------------------------------------------
[ timeout , nb_paquets, les_adresses, les_longueurs ] = ff_lire_data( "c:\prj\petitours.csv" )
longueur_max = 250
# J'ajoute un paquet bidon très loin, ainsi on va s'obliger à 'fermer' après le dernier paquet, dans la boucle générale.(pas besoin de code particulier pour gérer la fin de tableau).
nb_paquets = nb_paquets+1
les_adresses.append ( 99999999)
les_longueurs.append (0)
tb_scenario = []
tb_scenario2 = []
un_scenario = ( [], les_adresses[0], 0 ,0 )
"""
1=liste des 0 ou 1 = Liste des endroits où on regroupe ou sépare nos paquets.
2=adresse du 1er paquet apres le dernier mur,
3=Cout cumulé
4=Redondant avec 2 , emplacement de la dernière coupeure entre LOTS
"""
tb_scenario.append(un_scenario)
# 2. Boucle sur les paquets --------------------------------------------------------------------------
"""
je ne fais pas à proprement parler du parcours d'arbre, je recense toutes les branches de l'arbre.
Mais dès que je peux supprimer telle ou telle branche de l'arbre qui s'avère inutile parce que trop coûteuse ou incompatible avec les contraintes, je supprime cette branche.
Plus précisément, si la branche est incompatible avec les règles, je ne la crée pas dans mon tableau tb_scenario2
Et si elle est compatible avec les règles mais trop couteuse, je la crée dans scenario2, mais je ne la copie pas dans tb_scenario.
"""
for numero_paquet in range( 1, nb_paquets) :
tb_scenario2 = [] # ou del tb_scenario2[:]
fin_paquet_a_venir = les_adresses[ numero_paquet] + les_longueurs[numero_paquet] - 1
best_cout = 9999999999
for un_scenario in tb_scenario :
les_0_1_svg = list( un_scenario[0] )
addr_prem_paquet = un_scenario[1]
cout_cumule = un_scenario[2]
for k in range ( 2) :
# on ajoute en principe 2 scenarios 0 ou 1 , PAsede séparation ou Séparation avant le PAQUET_A_VENIR
# k=0 : pas de mur avant numero_paquet, k=1 : avec un mur avant numero_paquet
les_0_1 = list ( les_0_1_svg)
les_0_1.append(k)
if k == 0 :
if fin_paquet_a_venir - addr_prem_paquet <= longueur_max :
# pas de mur avant numero_paquet, possible uniquement si numero_paquet n'est pas trop loin de addr_prem_paquet
un_scenario = ( les_0_1, addr_prem_paquet, cout_cumule, k )
tb_scenario2.append(un_scenario)
# Fin du test : if futur-paquet 'compatible'
else :
cout_incremental = ff_calcule_cout ( addr_prem_paquet , fin_paquet_a_venir , timeout )
nv_cout = cout_cumule + cout_incremental
un_scenario = ( les_0_1, les_adresses[numero_paquet], nv_cout , k )
best_cout = min ( best_cout, nv_cout ) # Je mémorise le coût minimal parmi les scénarios qui finnissent par un mur à cet endroit.
tb_scenario2.append(un_scenario)
# fin de la boucle for k in 0,1
# Fin de la boucle : Pour tous les scénarios qui étaient en attente
# Suppression de tous les sénarios 'périmés'
tb_scenario = [] # ou del tb_scenario[:]
# Nettoyage des scenarios trop couteux, et on re-transfère vers tb_scenario au lieu de tb_scenario2
for un_scenario in tb_scenario2 :
if un_scenario[3] == 0 : # Les scenarios 'ouverts' , je les conserve tous sans condition.
tb_scenario.append(un_scenario)
else : # Les scénar fermés par un mur, je n'en conserve qu'un : le moins cher.
cout_cumule = un_scenario[2]
if cout_cumule == best_cout :
tb_scenario.append(un_scenario)
best_cout = -1 # Je viens de copier un scénario, les autres scénarios ex-aequo ne m'intéressent plus ; je donne donc une valeur 'farfelue' à best_cout.
print ( "Fin du step i= ", numero_paquet - 1 , " Nb scénarios dans le tuyau = ", len(tb_scenario) , " Addr/lg du paquet à venir = ", les_adresses[numero_paquet] , " ; " , les_longueurs[numero_paquet] )
# Fin de la boucle sur numero_paquet , et donc fin du traitement.
# 3. Affichage du résultat ---------------------------------------------------------------------------------------------------
#Je boucle sur tb_scenario, mais par construction, il ne peut y avoir qu'un scénario dans tb_scenario.
if len(tb_scenario) != 1 :
print ( "ERREUR ! Je devrais avoir un seul scénario à ce niveau, et j'en ai : " , len(tb_scenario) )
for un_scenario in tb_scenario :
affiche_en_clair ( un_scenario, les_adresses, les_longueurs) |
