4.9 Les pro grammes de tran sport
149
© Dunod – Toute reproduction non autorisée est un délit.
Figure 4.41 Une exé cu tion de l’algo rithme de Prim
Le lec teur aura cer tai ne ment remar qué que les trois algo rithmes que nous venons
de pré sen ter, basés tous les trois sur une stra té gie « gour mande » (on dit aussi : « glou -
tonne » ; en anglais : « greedy »), se révèlent par ti cu liè re ment effi caces. Le lec teur consul
tera les cha pitres consa crés aux matroïdes dans les ouvrages trai tant d’algo rith mique [8]
ou de théo rie des graphes pour trou
ver les jus ti fi cations théo
riques de cette effi
ca cité.
4.9 les pro grAmmes de trAn sport
Les notions sur les arbres, pré sen tées dans les para graphes pré cé dents, vont nous être
utiles pour résoudre un pro blème pra tique des plus cou rants en recherche opé ra tion -
nelle : celui des pro grammes de tran
sport, que nous défi nis sons ci dessous.
149
© Dunod – Toute reproduction non autorisée est un délit.
Figure 4.41 Une exé cu tion de l’algo rithme de Prim
Le lec teur aura cer tai ne ment remar qué que les trois algo rithmes que nous venons
de pré sen ter, basés tous les trois sur une stra té gie « gour mande » (on dit aussi : « glou -
tonne » ; en anglais : « greedy »), se révèlent par ti cu liè re ment effi caces. Le lec teur consul
tera les cha pitres consa crés aux matroïdes dans les ouvrages trai tant d’algo rith mique [8]
ou de théo rie des graphes pour trou
ver les jus ti fi cations théo
riques de cette effi
ca cité.
4.9 les pro grAmmes de trAn sport
Les notions sur les arbres, pré sen tées dans les para graphes pré cé dents, vont nous être
utiles pour résoudre un pro blème pra tique des plus cou rants en recherche opé ra tion -
nelle : celui des pro grammes de tran
sport, que nous défi nis sons ci dessous.