livrable-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center style=\"text-decoration:underline;\">Livrable 1</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contexte et présentation du problème\n",
    "\n",
    "Avec la nécessité de prendre en compte l'écologie, des mesures sont à prendre afin d'optimiser les processus de livraison. Nous représentons une entreprise nommée CesiCDP dont l'objectif est de trouver des solutions pour aider à la transition écologique et technologique. L'ADEME propose des financements pour les entreprises proposant des solutions de mobilité plus écologiques et responsable. Il s'agirait pour notre entreprise d'arriver à trouver une solution algorithmique permettant de calculer sur un réseau routier une tournée permettant de relier entre elles un sous-ensemble de villes, puis de revenir à son point de départ, de manière à minimiser la durée totale de la tournée.\n",
    "\n",
    "<center><img src=\"img/projet_1.png\"/></center>\n",
    "\n",
    "Le schema ci-dessus montre les routes que nous devons optimiser."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problème de décision :\n",
    "\n",
    "Pour mieux comprendre le projet et les demandes, nous allons écrire le problème de décision associé aux demandes. Pour ce faire, nous allons avoir besoin de décrire d’abord les données en entrées. \n",
    "Les données en entrées sont des données représentant un graphe. Le meilleur moyen de représenter un graphe est la matrice d’adjacence. En effet, nous aurions pu utiliser une liste d’adjacence, mais celle-ci est optimale dans les cas où le graphe est peu dense. Or, dans notre cas, le graphe risque d’être dense, nous priorisons donc une matrice d’adjacence. Cette matrice d’adjacence ``A`` de dimension ``n * n``, où ``n`` est le nombre de sommets du graphe. Chaque élément ``A[i][j]`` indique le poids de l'arête entre les sommets ``i`` et ``j``, avec ``A[i][j] = 0`` si aucune arête n'existe entre ``i`` et ``j``.\n",
    "Après avoir défini les données, nous allons décrire le problème de décision :\n",
    "\n",
    "<center style=\"font-weight:bold;\">Existe-t-il un cycle C qui passe par tous les sommets tel que la somme des poids des arêtes de C soit ≤k ?</center>\n",
    "\n",
    "Nous pouvons trouver un problème d’optimisation, permettant de trouver une solution encore plus optimale :\n",
    "\n",
    "<center style=\"font-weight:bold;\">Trouver un cycle C qui passe par tous les sommets tel que la somme des poids des arêtes de C soit minimale.</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classe de complexité :\n",
    "\n",
    "Le problème à résoudre est NP-complet. Pour le prouver, il faut montrer que :\n",
    "\n",
    "- Le problème se vérifie en temps polynomial.\n",
    "- Le problème peut être réduit de façon polynomiale à un autre problème. \n",
    "\n",
    "Pour prouver que le problème se vérifie en temps polynomial, il faut regarder ce que renverra notre algorithme, et les données en entrée. Le programme retournera une chaîne de caractères ou une liste, représentant le cycle retourné. De plus, le poids total du cycle est retourné, représentant le nombre de kilomètres parcourus pour retourner jusqu’au point de départ.\n",
    ">Par exemple :\n",
    ">\n",
    ">[\"A\", \"D\", \"B\", \"C\", \"E\", \"A\"], 15\n",
    "\n",
    "Ici, on a un cycle qui commence par le point ``A`` puis passe par le ``D`` puis le ``B`` puis le ``E`` et reviens au ``A``. Le poids total (dont la valeur représente des kilomètres), est de 15.\n",
    "Pour vérifier que le problème est vérifiable en temps polynomial, il faut regarder si ce chemin est un cycle valide. Pour ce faire, nous pouvons parcourir les sommets retournés et vérifier si tel et tel sommet sont bien connectés par une arête grâce aux données en entrée (le graphe). De plus, pendant le parcours de ce cycle, si l’arrête est correcte, on additionne le poids de l’arête a un poids total. Cela permettra de vérifier à la fin du parcours, si en plus de savoir que le cycle est valide, que le poids correspond bien au poids du chemin. Le parcours de cycle dans le cadre de graphe se fait en temps polynomial. La première étape est donc vérifiée.\n",
    "La deuxième étape consiste à faire une réduction polynomiale de ce problème. Pour ce faire, il faut trouver un autre problème NP-complet. Il se trouve que notre problème s’apparente à un autre problème, le problème du voyageur. En effet, le problème du voyageur consiste à trouver un circuit le plus petit qui passe exactement une fois par chaque ville (représentée par des sommets) et revient au sommet de départ. La seule différence étant que dans notre cas, nous pouvons repasser plusieurs fois sur un sommet, si nécessaire. Par exemple, nous serons forcés de repasser par le sommet de départ (ou ville de départ), car pour atteindre certaines villes, il faut repasser par celle-ci. Le problème reste néanmoins une réduction polynomiale du problème du voyageur."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion :\n",
    "\n",
    "Grâce aux problèmes de décision et d'optimisation, nous allons pouvoir concevoir un algorithme capable de répondre à ces types de problèmes. De plus, sachant que le problème est NP-complet, nous devons réfléchir à un algorithme approprié pour le résoudre. Étant donné que la complexité n'est pas en temps polynomial, il sera nécessaire de rechercher une solution optimale plutôt qu'une solution exhaustive."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}