Ah oui, exact. C'est du cut/flow sur les plaques et pas sur les trous. Bien joué !Envoyé par hellfoust
Du coup, ca explique l'indication.
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Ah oui, exact. C'est du cut/flow sur les plaques et pas sur les trous. Bien joué !
Du coup, ca explique l'indication.
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Peux etre il faut transformer le graphe biparti en reseau de transport puis voir le flux maximal ?
A mon sens le graphe biparti correspondant au problème est le graphe ayant pour noeuds : un noeud par trou de la matrice et un noeud par droite, et ayant pour arcs : un arc entre un "trou" et une "droite" (au plus 2) à laquelle il participe (cf ma première réponse a propos du set cover). Mais je n'ai pas réussi à trouver ce qui fait que ce cas est plus simple que le cas général.
« La science informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. » — Edsger Dijkstra
Merci a vous tous pour votre aide
Merci beacoup
Haaa je viens de comprendrePour ceux qui sont lents comme moi : les solutions proposées jusqu'à présent n'exploitaient pas le fait que :
- une droite verticale ne peut couper qu'une droite horizontale (d'où le fait que le graphe soit biparti)
- une case est défini par une ligne et par une colonne (d'où la possibilité de representer les cases sous la forme d'arc)
La solution de hellfoust exploite ces deux propriétés. Bien vue
J'aurai juste une remarque (il faut bien que j'en ai une) : penser à traiter le cas des plaques obligatoires (il n'y a pas d'arcs pour les cases n'appartenant pas à une intersection, elles ne sont donc pas prises en compte lors de la recherche du vertex cover) et ne pas les faire figurer dans le graphe.
« La science informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. » — Edsger Dijkstra
Je penses que toutes les cases peuvent être couvertes par deux plaques (une verticale et une horizontale). Pour les cases "obligatoires", l'une des deux plaques est de taille "1".
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Tu as raison. J'étais à coté de la plaque. Donc plus de remarques
« La science informatique n'est pas plus la science des ordinateurs que l'astronomie n'est celle des télescopes. » — Edsger Dijkstra
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager