Giter Club home page Giter Club logo

alg-100's Introduction

Algorithme du chemin le plus efficace d’un chasse neige à Montréal

Objectif :

À partir d'une liste de décimaux, représentant l'emplacement de maison dans la ville de Montréal, trouver une approximation du chemin le plus efficace pour un chasse neige, afin de limiter le temps d'attente moyen pour chaque maison.

Définition du temps d'attente : avec la liste suivante : 0,2,3,-1, le temps d'attente moyen serait de (2+1+6)/3=3, alors que dans avec celle-ci : 0,-1,2,3, il serait de (1+3+1)/3≈2.

Algorithmes envisagés :

Nom Bruteforce
Complexité O(n!)
Avantage Trouve le meilleur chemin
Inconvénient Complexité plus qu'exponentielle, ne marche pas sur des instances de plus de 10 éléments.

Le problème ressemblant assez au problème du voyageur de commerce, il aurait été tentant d'utiliser des méthodes permettant d'approximer une solution pour ce problème.

Or, on peut trouver de bonnes approximations de solutions au problème du voyageur de commerce avec un arbre de poids minimum puis le parcours en pré-ordre de l'arbre obtenu. Mais on se rend alors compte que ce problème n'est pas compatible avec le nôtre.

  • Une solution pour le problème du voyageur de commerce permettrait d'avoir le chemin le plus rapide pour explorer tous les points, mais sans prendre en compte le temps moyen d'attente avec l'exploration.

Une solution trouvée pour résoudre le problème du chasse neige est alors la suivante :

Explication

Pour diminuer le temps d'attente moyen dans ce problème, une des solutions est de créer des regroupements de maison, des « quartiers », et d'explorer en premier les quartiers les plus « denses », c'est à dire ceux avec l'écart type le plus faible. Sachant que l'on travaille avec des listes de 10 éléments, il est possible d'utiliser l'algorithme de bruteforce sur le dernier élément visité + le quartier pour déterminer le meilleur ordre de visite.

Enfin, plutôt que de visiter les quartiers dans l'ordre d'écart type, il est intéressant de visiter ceux qui sont présent sur la route et de les supprimer de la liste des quartiers à visiter.

Implémentation

L’implémentation utilise le langage Scala, choisi pour sa capacité à faire de la programmation fonctionnelle : Utilisation des tuples, de la récursion finale et possibilité d’utiliser des monades et des accumulateurs.

Utilisation

  • Concernant les arguments, il n'est pas nécessaire de rajouter le 0 à la liste des maisons, il est inclue de base dans l'algorithme
  • Le format des nombres accepté : 1 1.0 1.1

Via IntelliJ

  • Importez le projet SBT, puis lancez le programme depuis la classe Main

Via SBT

  • sbt run 1 2 3 4

Via le fichier compilé

  • java -jar ProjetFinalAlgo.jar 1 2 3 -10 2.3

Compilation

  • sbt compile packageBin

Exemple d'utilisation

java -jar ProjetFinalAlgo.jar -10 2.2 3.2 4.2
# 0.0,4.2,3.2,2.2,-10.0
java -jar ProjetFinalAlgo.jar 2 3 4 -10
# 0.0,4.0,3.0,2.0,-10.0

Fonctionnement

Liste de maison -112,-89,-45,-40,-25,-24.5,-24,-23,-15,8,15,18,120,121,122,125 Avec TAILLE_QUARTIER_MAXIMUM=4

On divise la liste d'entrée en sous listes de 4 éléments chacunes, puis on calcul l'écart type de chacune.

# Liste Ecart Type
1 -112,-89,-45,-40 30.17035
2 -25,-24.5,-24,-23 0.73951
3 -15,-8,15,18 16,46207763
4 120,121,122,125 2,160246899

Une fois fait, on trie les listes par écart type croissant

# Liste Ecart Type
2 -25,-24.5,-24,-23 0.73951
4 120,121,122,125 2,160246899
3 -15,-8,15,18 16,46207763
1 -112,-89,-45,-40 30.17035

On a un premier chemin qui se dessine, qui serait 2-4-3-1 Mais, pour aller de 2 à 4, il y a 3 sur la routes, il devient intéressant d'ajouter la liste au chemin final.

On obtient alors à la fin le chemin 2-3-4-1. Enfin, pour minimiser le temps d'attente au sein d'un quartier, on appelle la fonction bruteforce de la manière suivante :

  bruteforce((dernierNoeudVisité :: listeAVisiter).permutations)

Ainsi, on obtient la meilleure permutation à ajouter dans le chemin final.

alg-100's People

Contributors

navispeed avatar

Watchers

 avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.