Discussion :

[olibara]

Bonjour

Je suis a la recherche d'exemple pratiques d'algorithme permettant de resoudre le problème du postier chinois dans un graph semi orienté (situation normale d'un réseau de route : certaine voies sont a sens unique mais pas toutes !)

Ci joint un joli pdf que j'ai trouvé mais il travaille sur un graph non-orienté

[Scorpi0]

De la doc sympathique :

http://www.crt.umontreal.ca/~nikolaj...nch/index.html

Voir Acte 3 Scène 2.

A noter que la résolution semi-orienté sera de toute manière identique à la version orienté (suffit de remplacer un arc non orienté par deux arcs orientés).

[olibara]

Merci Scorpio


J'étais déja tombé sur cette explication mais j'aimerais la confronter avec d'autre pour aider ma compréhension.
Car c'est encore en peu tenebreux pour moi.
A part Dijkstra que je connais bien et avec qui je joue beaucoup, je ne suis par encore un grand artiste des Graph !

[Scorpi0]

D'après mes souvenirs de cours de RO, Djikstra & cie résout la classe de problème de plus court chemin, et d'autres algos que je sais plu les noms résolvent les problèmes de flots.

Le problème du postier s'apparentent beaucoup plus à un problème de flots qu'a un problème de plus courts chemins, et c'est ce que j'ai cru comprendre dans le lien, c'est que le postier peut se transformer en un problème de recherche de flot minimum.

Étant rouillé niveau RO, et de toute façon, je n'ai quasiment fait que des heuristiques, bah je te laisse te renseigner plus sur la résolution des problèmes de flots ^^

[olibara]

Aaargh !

Moi c'est pas que je suis rouillé mais je suis généralement hermetique a toute formulation de ces Algorithmes
J'ai passé des jours a lire la litérature a propos de Dijkstra avant de comprendre comment ca marchait vraiment !
Maintenant que je sais, je trouve ca tres simple mais si je relis un article sur le sujet j'ai toujours du mal a le comprendre

En plus la formulation française et souvent asser différente de la formulation anglaise

Et aujourd'hui je suis retombé dans le bain en essayant de digerer cette tournée chinoise

J'espere que quelqu'un aura quelque autres suggestions pour me faire digerer la chose

Ta petite piece de théatre c'est pas mal mais pas encore asser détaillé a mon gout