Informatique

Hello,

Ya quelqu'un qui a réussi la question 5 des qualif pour prolog 2020?

https://prologin.org/train/2020/qualification/force_contre_flotte

La comme ca, j'ai pas un bon algo pour resoudre le probleme. Mais quelques remarques:

La discussion des bateaux, c'est juste confusant. En fait les bateaux decrivent une image binaire (noire et blanc).

On peut commencer par decouper le probleme en region connecte. Si il y a deux regions pas connectes, on peut resoudre les deux problemes independements et concatener les solutions.

On peut aussi remarquer qu'il y a des lignes de forces qui sont possibles mais n'ont pas de sens. Si la ligne de (2,3) a (2,6) est possible, ca n'a pas de sens de considerer la ligne de (2,3) a (2,5) parceque la premiere est toujours meilleure. Ca veut dire que le nombre de ligne a considerer ne peut pas etre si grand (au plus l*h).

Si on represente le probleme comme un graphe biparti avec a gauche les lignes et a droite les cellule couverte, le probleme devient un probleme de selection. Dans le cas general, le probleme est NP complet. Mais en l'occurence la propriete du dessus assure qu'il y a au plus deux lignes de force possible qui peuvent couvrir une des cellules. Donc dans le probleme, il y a plein de forcage qui peuvent arriver.

ah, j'ai un algo qui marche, mais c'est moche.

Tu ecris le programe lineaire en nombre entier:

min \sum x_l
s.t.
x_l >= 0 \forall l
x_l <=1 \forall l
x_l+x_l' >= 1 \forall c=l,l'

Les contraintes des deux premiers types forcent que tu ne puisse pas prendre negativement une ligne ou que tu ne puisses pas la prendre plus d'une fois. Les contraintes du troisieme type force a prendre au moins une ligne pour couvrir chaque cellule du probleme. Ca modelise exactement le probleme. Et tu le resoud en nombre fractionel et pas en nombre entier.

Si il y a L lignes, alors une solution est donne par le serrage de L contraintes, supposons qu'il y en a k de type 3 serre, donc il y a donc k x_l a valeure fractionelle.

une ligne fractionelle doit faire parti de au moins 2 contraintes type 3 serre, sinon on peut deplacer sa valeure sur l'autre ligne. Chaque contrainte c serre a exactement 2 x_l fractionnel

On peut construire le graphe des l et c fractionel. Le graphe est de degree minimal 2. et le nombre de c est egal au nombre de l. Donc le graphe est exactement de degree 2. Donc il n'y a pas de coupe du graphe biparti qui coupe une seule arete du graphe. Donc on peut prendre un l sur 2 et le mettre a 1 et mettre l'autre a 0.

Il doit y avoir un algo plus simple.