Est-ce un classique de programmation dynamique?
Est-ce un classique de programmation dynamique?
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 ?
Re: Est-ce un classique de programmation dynamique?
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-?
LLG HX1 2018-2019
LLG MP*3 2019-2020
Ulm 2020-?
Re: Est-ce un classique de programmation dynamique?
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.
Re: Est-ce un classique de programmation dynamique?
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
Re: Est-ce un classique de programmation dynamique?
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.
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.
Re: Est-ce un classique de programmation dynamique?
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
"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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Est-ce un classique de programmation dynamique?
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)
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)
Re: Est-ce un classique de programmation dynamique?
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?
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Est-ce un classique de programmation dynamique?
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Est-ce un classique de programmation dynamique?
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.
__
__| |
| |
__| | __
|____| |
|
|__
__
__| |
| | __
__| | __|
|____|
__
__| | __
| | |
__| | __|
|____|
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.
__
__| |
| |
__| | __
|____| |
|
|__
__
__| |
| | __
__| | __|
|____|
__
__| | __
| | |
__| | __|
|____|