Est-ce un classique de programmation dynamique?

Messages : 0

Inscription : 18 juin 2017 13:21

Profil de l'utilisateur : Élève de lycée

Est-ce un classique de programmation dynamique?

Message par Lohengrin » 19 févr. 2018 22:11

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 ?

Messages : 0

Inscription : 04 oct. 2017 15:58

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par Errys » 19 févr. 2018 22:17

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-2019
LLG MP*3 2019-2020
Ulm 2020-?

Messages : 0

Inscription : 18 juin 2017 13:21

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » 19 févr. 2018 22:49

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.

Messages : 3823

Inscription : 17 avr. 2012 21:19

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par bullquies » 20 févr. 2018 02:49

on comprend rien à ce qu'on "peut" ou "doit" faire.
The Axiom of Choice is obviously true, the Well-Ordering Principle is obviously false, and nobody knows about Zorn's Lemma. - Jerry Bona

Messages : 0

Inscription : 18 juin 2017 13:21

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » 20 févr. 2018 17:34

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.

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par fakbill » 22 févr. 2018 13:16

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é.

Messages : 0

Inscription : 18 juin 2017 13:21

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » 22 févr. 2018 21:26

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)

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par fakbill » 23 févr. 2018 10:34

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é.

Messages : 9679

Inscription : 30 juil. 2008 16:59

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par fakbill » 23 févr. 2018 10:38

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é.

Messages : 0

Inscription : 18 juin 2017 13:21

Profil de l'utilisateur : Élève de lycée

Re: Est-ce un classique de programmation dynamique?

Message par Lohengrin » 23 févr. 2018 15:48

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.

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

Répondre