Quel algo appliquer ?

Bonjour à tous,

j'ai réalisé un site internet pour un client de vente de biens immobiliers. On retrouve logiquement tous les biens à vendre, et un moteur de recherche de biens, suivant différents critères. Mon client souhaiterait pouvoir proposer aux internautes la possiblité de rechercher un bien sur une commune, mais ensuite de pouvoir étendre le rayon de recherche de 10, 20 ou 30 kilomètres autour!

J'ai donc la liste des communes, et je souhaiterais savoir s'il existe un algo qui pourrait me donner la liste des communes autour! Car j'ai bien fait des algos, tels que le voyageur de commerce et autre à l'école, mais tout ça est bien loin!

Si vous avez une petite idée pour me permettre de partir, pour info meme si cela n'a pas vraiment d'importance, je travaille en PHP et les villes seront stockées dans une base MySQL!

Merci d'avance.
Manu.

Hio,

Une idée simple (trop ?) :

Pour chaque commune, stocker les coordonnées (longitude, latitude), et calculer leur distance à la commune cible.

Citation:

---

Pour chaque commune, stocker les coordonnées (longitude, latitude), et calculer leur distance à la commune cible.

---

Oui, c'est une idée, ça donne la distance à vol d'oiseau. Une autre solution c'est de faire un plus court chemin (Dijkstra), à partir d'un réseau routier, ça permet d'être un poil plus précis (en montagne la différence entre la route et le vol d'oiseau peut être énorme).

Google propose dans son API de google map cette fonction.
Il donne les distances entre plusieurs Ville, adresse, coordonnées, et un tât de chose :)

Sinon avec les longitude/latitude et le théorème de Pythagore :aie:

ReBonjour à tous,

effectivement la distance à vol d'oiseau change par rapport à la réalité, mais il faut que je vois comment réfléchissent les potentiels acheteurs, histoire de ne pas mettre en place un algorithme certainement intéressant à développer (Dijkstra) mais pas adapté. En tout cas merci à tous pour vos réponses.

Manu.

PS : je suis tout à fait d'accord avec alex_pi je vais pas récupérer un truc sans licence pour mon client et en plus ce genre de truc quand tu as besoin de l'adapter pour une raison ou une autre, tu mets 2 fois plus de temps, mais merci quand même pour le conseil.

Tu devrais vraiment te pencher vers google map pour ce genre de situation, avec une doc aussi complète en plus :

http://www.google.com/apis/maps/docu...reference.html
http://www.google.com/apis/maps/docu...ocoding_Direct

Il me semble que la clef est gratuite jusqu'à un certain nombre de reqûetes par jours.

Jua,

Citation:

---

Envoyé par AnjouWeb

effectivement la distance à vol d'oiseau change par rapport à la réalité, mais il faut que je vois comment réfléchissent les potentiels acheteurs, histoire de ne pas mettre en place un algorithme certainement intéressant à développer (Dijkstra) mais pas adapté. En tout cas merci à tous pour vos réponses.

---

Il tiendront compte de la distance à effectivement parcourir, comme tout le monde.

C'est pourquoi j'avais précisé que l'idée proposée dans mon post était sans doute trop simple (mais garde l'avantage d'être simple à implémenter, cependant, comme elle est peu réaliste, la simplicité n'intervient pas beaucoup :)).

Hello,

J'attire juste l'attention sur le faite que s'il faut calculer a chaque fois la distance entre la commune cible et toutes les autres N communes, c'est en O(N) et ce pour chaque requete.

Juste un suggestion: pre-calcule une sorte de connectivite entre communes pour eviter d'avoir a parcourir toute la liste lors des requetes. De plus disons que tu aies ainsi obtenu toutes les communes dans un certain perimetre (a vol d'oiseau), tu peux utiliser Dijkstra sur ce sous-ensemble pour raffiner ton resultat.

Bonne chance,

Gregoire

Le problème avec ta solution, c'est qu'elle oblige à ce que tout ce que tu vas parcourir lors de ton dijkstra sera dans le cercle "à vol d'oiseau", et donc pas toujours applicable (en montagne par ex).

Sinon, autre solution, tu calcules off-line les distances entre toutes les villes. Tu rentres ça dans une BDD et comme ça tu as directement les distances.

Hello,

je me doutais bien qu'il pouvait y avoir plusieurs petites astuces qui paraissent simples quand on est plongé régulièrement dans les algos. cette idée de faire un sous ensemble sur les communes répondant au critère de distance à vol d'oiseau, puis appliquer Dijkstra sur ce sous-ensemble, me séduit pas mal. Mais d'un autre coté, pour cette histoire de O(n), je me souvient que c'est la complexité de l'algo et ça indique le nombre d'opérations effectuées pour avoir le résultat, mais pourriez-vous que le réexpliquer brievement ?

je sais que j'ai au max 100 ou 150 communes à prendre en compte, et que pour le moment, j'ai moins d'une centaine de visite par jour. Mais ces visiteurs sont bien souvent des acheteurs potentiels, c'est donc une page très visitée et ce genre d'outils risque d'être assez utilisé. A terme je pense qu'on avoisinera les 300 visites jours, il faut donc que mon serveur suive et que les 30 autres sites à coté ne soit pas ralenti. Il faudra ptet passer par une mega base de données, qui contient tout, de villes à villes, alimentée par l'algo au départ bien sûr.

Manu.

Citation:

---

Envoyé par PRomu@ld

Le problème avec ta solution, c'est qu'elle oblige à ce que tout ce que tu vas parcourir lors de ton dijkstra sera dans le cercle "à vol d'oiseau", et donc pas toujours applicable (en montagne par ex).

---

correct.

Citation:

---

Sinon, autre solution, tu calcules off-line les distances entre toutes les villes. Tu rentres ça dans une BDD et comme ça tu as directement les distances.

---

oui pourquoi pas. ou de stocker le graph simplement avec la distance entre commune sur les arretes, l'algo est alors trivial et efficace.

Salutations,

Gregoire

Citation:

---

Envoyé par AnjouWeb

Hello,

je me doutais bien qu'il pouvait y avoir plusieurs petites astuces qui paraissent simples quand on est plongé régulièrement dans les algos. cette idée de faire un sous ensemble sur les communes répondant au critère de distance à vol d'oiseau, puis appliquer Dijkstra sur ce sous-ensemble, me séduit pas mal. Mais d'un autre coté, pour cette histoire de O(n), je me souvient que c'est la complexité de l'algo et ça indique le nombre d'opérations effectuées pour avoir le résultat, mais pourriez-vous que le réexpliquer brievement ?

---

formellement O(n) represente une borne superieure de la complexite de ton algo (ici en terme de calcul, mais parfois applique en terme de memoire). Intuitivement ca veut dire que le nombre d'operation de l'algorithm est proportionnel a n: donc si tu double n (le nombre de ville), le temps de calcul doublera (au pire: ie borne superieur). Abusivement on utilise O(n) pour donner la complexite exacte et non une borne superieur... Enfin je laisserai des experts corriger ce que je dis ;)

en zone urbaine le temps de transport dépend plus des moyens de communication utilisés et disponibles

en zone rurale il existe une unité administrative qui regroupe les communes proches et prens en compte leur densité c'est le canton en zone urbaine l'arrondissement

un algorithme de proximité cantonale pourrait être suffisant et permettrait d'alléger sensiblement les temps de calcul

d'autant que les agences pourraient modifier le prédécoupage en fonction de leur connaissance du terrain et des découpages commerciaux

les temps de paramétrage et calcul seraient divisés puisqu'il n'existe que 4035 cantons et 342 arrondissements pour 36678 communes

des fichiers sont disponibles et libres de droit notamment le com_cant de la bnf (gallica) de mémoire carte cassini

Citation:

---

ou de stocker le graph simplement avec la distance entre commune sur les arretes, l'algo est alors trivial et efficace.

---

En fait, pas forcément besoin de stocker le graphe mais un seul tableau suffit. (c'est pour ça que je parlais de BDD)

Citation:

---

Il faudra ptet passer par une mega base de données

---

100 ou 150 villes, c'est pas énorme, tu peux tout stocker sans pb.

Citation:

---

Envoyé par AnjouWeb

Bonjour à tous,

j'ai réalisé un site internet pour un client de vente de biens immobiliers. On retrouve logiquement tous les biens à vendre, et un moteur de recherche de biens, suivant différents critères. Mon client souhaiterait pouvoir proposer aux internautes la possiblité de rechercher un bien sur une commune, mais ensuite de pouvoir étendre le rayon de recherche de 10, 20 ou 30 kilomètres autour!

---

en relisant, j'ai l'impression que ce que AnjouWeb veut c'est les distances a vol d'oiseau tout simplement, pour que le client puisse voir les propriete dans la region.

Salutations,

Gregoire

après vérification, j'ai 190 villes à rentrer, si je stocke la distance de chaque villes entre elles j'obtiens donc environ 36000 enregistrements dans ma table, c'est pas énorme c'est sûr mais je vais pas me les tapper à la paluche, il ne me reste plus qu'à voir avec un des commerciaux d'agence si dans la tete des acheteurs, c'est plus la distance réelle ou à vol d'oiseau, c'est quand même pas la région parisienne, mais autour de Saumur (49) et je ne suis pas sûr que les gens pensent vraiment à faire la différence entre 10 kilomètres à vol d'oiseau, mais 15 kilomètres via la route. Conceptuellement, c'est moins propre, dans les faits c'est peut-être suffisant!

Une personne pour me remémorer ce que c'est O(n) rapidement?

Manu

Citation:

---

Envoyé par PRomu@ld

En fait, pas forcément besoin de stocker le graphe mais un seul tableau suffit. (c'est pour ça que je parlais de BDD)
..
100 ou 150 villes, c'est pas énorme, tu peux tout stocker sans pb.

---

il faut juste etre conscient que ca prendra N^2 enregistrement soit 10'000 pour 100 communes.
Dans ce cas, tes enregistrements seront probablement de forme [commune1_id, commune2_id, dist]
L'aventage direct c'est que tu peux pretrier les donnes d'abord en fonction de commune1_id, puis de dist. Avec cela, tu obtiendras en un temps constant la liste des communes les plus proches.

Salutations,

Gregoire

Citation:

---

Envoyé par AnjouWeb

Une personne pour me remémorer ce que c'est O(n) rapidement?

Manu

---

deja repondu ;)


salutations,

Gregoire