mapinfo
Messages postés8Date d'inscriptionmercredi 10 janvier 2007StatutMembreDernière intervention 3 janvier 2008
-
25 avril 2007 à 23:57
PCPT
Messages postés13272Date d'inscriptionlundi 13 décembre 2004StatutMembreDernière intervention 3 février 2018
-
21 févr. 2008 à 18:17
Bonsoir,
Je débute en programmation en C, je devrais écrire un programme en C sur U.M.T.S. Voilà l'énnocé.
Une image de satellite est une carte des altitudes du terrain surlequel une société de Télécoms souhaite placer N antennes de relais. Sachant que ces antennes ne couvrent qu'un rayon de largeur R et qu'elles n'émettent pas vers le haut (une demi-shère), écrire le programme qui calcule qui calcule le meilleur emplacement pour ces N antennes de façon à obtenir la meilleure couverture possible.
Je demande de l'aide, car je ne sais pas par quoi commencer et comment. Des propositions, des pistes.
acx01b
Messages postés280Date d'inscriptiondimanche 7 septembre 2003StatutMembreDernière intervention 8 juillet 20146 26 avril 2007 à 10:17
salut j'ai une proposition d'algorithme
placer les N antennes au hasard
p = pourcentage de la surface couverte par le réseau
i = 0
tant que i < 100000
deplacer au hasard une antenne choisie au hasard
p2 = pourcentage de la surface couverte par le réseau
si p2 > p alors p = p2
sinon annuler le deplacement de l'antenne
i <-- i + 1
fin tant que
cs_rt15
Messages postés3874Date d'inscriptionmardi 8 mars 2005StatutModérateurDernière intervention 7 novembre 201413 26 avril 2007 à 13:13
Salut,
Regarde peut être du côté de l'algo du simplex et de la théorie des graphes, tout spécialement si tu as eu des cours sur le sujet.
Bon courage : trouver la solution optimale de ce problème paraît délicat à vu de nez.
Donc la solution à l'arrache de acx01b est peut être pas mal dans ce cas là. Ou un truc du genre un cadrillage, et tu teste toutes les combinaisons de placement de tes N antennes sur les "croix" du cadrillage. Mais ça risque d'être bien long en fonction de la taille de ton cadrillage...
mapinfo
Messages postés8Date d'inscriptionmercredi 10 janvier 2007StatutMembreDernière intervention 3 janvier 2008 26 avril 2007 à 21:48
Bonsoir, acx01b et rt 15
Votre réponse ne répond pas vraiment à mon problème. Mais, avec cet algorithme je peux rien faire. Il me faut une vrai explication et une solution satisfaisante. Je suis coinçé. Un programme meme petit avec des commentaires pour commencer et puis c'est à moi d'améliorer ou de le perfectionner ou de le modifier. Je n'ai pas encore suivi des cours sur la théorie des graphes ou l'algorithme de simplex. Aidez-moi svp car je suis bloqué.
Autre chose l'interpréteur lisp a été écrit en C et il tourne bien?
acx01b
Messages postés280Date d'inscriptiondimanche 7 septembre 2003StatutMembreDernière intervention 8 juillet 20146 26 avril 2007 à 23:19
#define X 100 // longueur de la carte satellite
#define Y 100 // largeur de la carte satellite
#define N 20 // nombre d'antennes
#define R 15 // rayon d'action d'une antenne
#define H 35 // hauteur maximale
#define MAX_ITERATION 10000 // nombre maximum d'essais
int map[X][Y];
int antenne[N][2];
void creer_map() {
pour tous les X*Y points :
map[x][y] = rand()%H;
}
void optimiser_antennes() {
pour toutes les N antennes :
antenne[N][0] = rand()%X, antenne[N][1] = rand()%X
int i;
for (i = 0; i < MAX_ITERATION; i++) {
p = pourcentage de couverture
choisir une antenne au hasard
sauvegarder sa position
modifier sa position au hasard
pour tous les points de la map regarder si il est assez près d'une antenne
(distance euclidienne entre le point et une antenne < R)
p2 = nouveau pourcentage de couverture
si (p2 <= p) annuler le changement
}
}
int main() {
creer_map();
optimiser_positions_antennes();
afficher_position_antennes();
}