Est-ce un classique de programmation dynamique?

Modérateur : Michel Quercia

Répondre
Lohengrin
Messages : 116
Enregistré le : dim. juin 18, 2017 1:21 pm
Classe : ETH (CS)

Est-ce un classique de programmation dynamique?

Message par Lohengrin » lun. févr. 19, 2018 11:11 pm

On connait les hauteurs de chaque case d’une grille NxM. On peut passer d’une case à l’autre (O,E,N,S) seulement si la différence de hauteur est inférieure à d. Quelle est la plus petite quantité de terre nécessaire (ce que l’on prend à une case est transporté dans une des 4 cases voisines) pour qu’il soit impossible de traverser la grille ?

Errys
Messages : 259
Enregistré le : mer. oct. 04, 2017 3:58 pm
Classe : MPSI

Re: Est-ce un classique de programmation dynamique?

Message par Errys » lun. févr. 19, 2018 11:17 pm

De traverse la grille en partant de quel point et pour aller à quel point ? Et quand tu parles de "terre", on peut rajouter de la hauteur à une case de la grille c'est ça ?
Lycée Édouard Branly 2015-2018
LLG HX1 2018-?

Lohengrin
Messages : 116
Enregistré le : dim. juin 18, 2017 1:21 pm
Classe : ETH (CS)

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » lun. févr. 19, 2018 11:49 pm

De n'importe quel point de la première rangée a n'importe quel point de la dernière. Ce que l'on prend à une case on le transfère a une voisine, par exemple deux case mitoyennes ayant la hauteur h on prend d/2 de l'une pour le placer sur l'autre pour arriver à des hauteurs de h+d/2 et h-d/2 ce qui bloque le passage.

Avatar du membre
bullquies
Messages : 6532
Enregistré le : mar. avr. 17, 2012 9:19 pm
Classe : Thé à la

Re: Est-ce un classique de programmation dynamique?

Message par bullquies » mar. févr. 20, 2018 3:49 am

on comprend rien à ce qu'on "peut" ou "doit" faire.

Lohengrin
Messages : 116
Enregistré le : dim. juin 18, 2017 1:21 pm
Classe : ETH (CS)

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » mar. févr. 20, 2018 6:34 pm

J’ai donc la réponse ce n’est pas un grand classique !

Une reformulation : Vous êtes le bienveillant général président d’un pays de cocagne où tout n’est que miel et lait, luxe, calme et volupté, que vos ancêtres et vous avez patiemment bâti au fil des décennies. Las! vos turbulents voisins du sud, ces vipères lubriques dont vous sépare une frontière accidentée de taille N par M s’ingénient à traverser cette frontière avec des véhicules transportant des tracts immondes et diffamatoires qu’ils distribuent à votre bien-aimée population. Fort heureusement la technologie arriérée de ces hyènes puantes ne permet pas à leurs véhicules de gravir de trop fortes pentes. Si la différence d’altitude entre deux cellules élémentaires de la frontière est supérieure ou égale à δ les véhicules ne peuvent progresser. Vous connaissez la hauteur actuelle de chaque cellule élémentaire de la frontière. Vous voulez donc, en déplaçant une certaine hauteur de terre d’une cellule à l’une de ses 4 voisines, bloquer l’arrivée de ces rats visqueux. Vous vous demandez donc quelle est la quantité minimale de terre qu’il vous faudra déplacer pour arriver à vos fins.

Ex.
δ=10, N = 8, M = 11

29 20 29 29 29 20 29 20
32 20 32 32 32 20 32 20
33 20 33 33 33 20 33 20
34 20 34 34 34 20 34 20
40 20 40 40 40 20 40 20
39 20 39 39 39 20 39 20
38 20 38 38 38 20 38 20
37 20 37 37 37 20 37 20
35 20 35 35 35 20 35 20
33 20 33 33 33 20 33 20
31 20 31 31 31 20 31 20

En déplaçant 25 vous protégez votre population de cette vile propagande.

29 20 29 29 29 20 29 20
32 20 32 32 32 20 32 20
33 20 33 33 33 20 33 20
32 15 32 32 32 15 32 15
42 25 42 42 42 25 42 25
39 20 39 39 39 20 39 20
38 20 38 38 38 20 38 20
37 20 37 37 37 20 37 20
35 20 35 35 35 20 35 20
33 20 33 33 33 20 33 20
31 20 31 31 31 20 31 20


Si cela n’est toujours pas clair il existe une version vue du sud.

Avatar du membre
fakbill
Messages : 11167
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Est-ce un classique de programmation dynamique?

Message par fakbill » jeu. févr. 22, 2018 2:16 pm

Mouais le blabla n'aide pas non plus...
"Vous vous demandez donc quelle est la quantité minimale de terre" : juste la quantité? Ou la quantié fois la distance? Si je veux déplacer 2 unites de (i,j) à (I,j-4) ça compte comme quoi? un coût de 2? ou de 2 fois 4? est ce que je peux répartir X pris en (i,j) sur plusieurs cases? si oui ça me coute combien?

il faut bloquer le chemin de où à où? de n'importe quel bord à n'importe quel bord?
On se déplace comment? Aussi en diagonale ou pas?

Bref, non ce n'est toujours pas clair :(
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Lohengrin
Messages : 116
Enregistré le : dim. juin 18, 2017 1:21 pm
Classe : ETH (CS)

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » jeu. févr. 22, 2018 10:26 pm

Third try lucky ... :?
Juste la quantité
Déplacement uniquement aux quatres cellules mitoyennes (i+1,j), (i-1,j), (i,j+1), (i,j-1)
bloquer de (1,j) avec j (1 ... n) à (n,k) avec k (1 ... n)

Avatar du membre
fakbill
Messages : 11167
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Est-ce un classique de programmation dynamique?

Message par fakbill » ven. févr. 23, 2018 11:34 am

oK là ça me semble clair.
C'est chi*** car comment controller qu'on crée par un nouveau chemin en bloquant un autre?
un algo très peu malin serait de se dire qu'on liste tout les chemins. Pour chaque chemin on le coupe en commençant par la facon de le couper qui coute le moins cher et qui ne crée pas de nouveau chemin...et ça merdouille...
C'est pénible donc intéressant ton truc :) Un expert en percolation?
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Avatar du membre
fakbill
Messages : 11167
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: Est-ce un classique de programmation dynamique?

Message par fakbill » ven. févr. 23, 2018 11:38 am

dans ton exemple tu les bloques sur une seule ligne mais ce n'est pas obligé ou je déconne? Ils ne se déplacent pas en diagonal donc on peut les bloquer de plein de façons différentes
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Lohengrin
Messages : 116
Enregistré le : dim. juin 18, 2017 1:21 pm
Classe : ETH (CS)

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » ven. févr. 23, 2018 4:48 pm

Non pas du tout obligé c'est juste le cas dans mon exemple mais d'autres solutions sont possibles.
Pour l'instant je regarde avec une récursion (bloquer la ième colonne puis chercher à quelle rangée
bloquer la i+1 de façon à obtenir un minimum local et ainsi de suite. Je prends comme minimum de départ le minimum le plus bas obtenu en bloquant les rangées comme dans l'exemple.

__
__| |
| |
__| | __
|____| |
|
|__
__
__| |
| | __
__| | __|
|____|
__
__| | __
| | |
__| | __|
|____|

Lohengrin
Messages : 116
Enregistré le : dim. juin 18, 2017 1:21 pm
Classe : ETH (CS)

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » ven. févr. 23, 2018 4:50 pm

Bon mes alignements foirent...

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité