Rendu 24 04 30

Finding Nemo

Overleaf

Installation

Veuillez cloner le référentiel

git clone https://github.com/untypequicode/finding-nemo.git

cd src/main/code

Pour exécuter le programme, vous devez disposer de Python 3.10 ou d'une version ultérieure. Vous pouvez installer Python à partir de python.org.

python main.py [fichier_données] [méthode] [OPTIONNEL] [fichier_sortie]

Paramètres

• [fichier_données] : Le chemin d'accès vers les fichiers de données au format TXT. Il est possible de fournir plusieurs dossiers contenant plusieurs fichiers de données. Il est également possible de fournir un nombre pour limiter le nombre de fichiers à traiter, ce qui traitera les n premiers fichiers du dossier. Il est possible de fournir un _ pour traiter tous les fichiers de tous les sous-dossiers.

• [méthode] : La méthode à utiliser pour résoudre le problème. Il est possible de fournir plusieurs méthodes en les mettant à la suite séparées par un espace. Les méthodes disponibles sont :

  • idiot : Méthode de résolution naïve.
  • ratio : Méthode de résolution basée sur le ratio entre les ressources et les besoins.
  • glouton : Méthode de résolution gloutonne.
  • ratio2 : Méthode de résolution basée sur le ratio entre les ressources et les besoins.
  • s_idiot : Méthode de résolution naïve avec secteurs.
  • s_idiot2 : Méthode de résolution naïve avec secteurs.
  • s_blur : Méthode de résolution floue avec secteurs.
  • s_magni : Méthode de résolution par magnification avec secteurs.
  • s_magni2 : Méthode de résolution par magnification avec secteurs.
  • affiche : Affiche les données du fichier de données (pour le débogage).
  • visualiser : Enregistre et affiche une visualisation du problème résolu ou non.
  • minorant : Calcule un minorant pour la valeur du TXT (sans résoudre le problème).
  • verifier : Vérifie si la solution fournie dans un fichier de sortie est correcte.

  Note : Les méthodes de résolution les plus fonctionnelles et à utiliser sont : idiot, ratio2, s_idiot et s_magni2.

• [OPTIONNEL] [fichier_sortie] : Le chemin d'accès vers les fichiers de sorties pour enregistrer la solution résolue.

  • Si la méthode visualiser est utilisée, il est possible de fournir un fichier solution pour visualiser le problème résolu.
  • Si la méthode verifier est utilisée, il est possible de fournir un fichier de sortie contenant la solution à vérifier sinon l'ensemble des solutions sera vérifié.

Exemples d'utilisation

python3 main.py ../instances/sort_instances/10_10/ ../instances/sort_instances/30_30/ ../instances/toy_instances/ s_idiot2
python3 main.py ../instances/instances/ s_idiot verifier visualiser
python3 main.py ../instances/toy_instances/ s_idiot2 visualiser verifier export/toy01_s_idiot2.txt
python3 main.py ../instances/sort_instances/_ s_magni visualiser verifier

Fonctionnement

Le script lit les fichiers de données, applique les méthodes de résolution spécifiées et enregistre les solutions dans des fichiers de sortie. Il peut également afficher les données, visualiser les solutions et vérifier leur validité.

Rendu 24 03 31

Finding Nemo

Overleaf

Installation

Veuillez cloner le référentiel

git clone https://github.com/untypequicode/finding-nemo.git

cd src/main/code

Pour exécuter le programme, vous devez disposer de Python 3.10 ou d'une version ultérieure. Vous pouvez installer Python à partir de python.org.

python3 main.py

Sortie pour toutes les instances

Lorsque l'utilisateur choisit d'exécuter tous les fichiers du dossier "instances_test", le programme affiche le pourcentage de fichiers traités, le nombre de fichiers traités, la durée totale de traitement et les temps moyens des différentes étapes de résolution. Chaque ligne représente le traitement d'un fichier.

Voici un exemple de sortie pour toutes les instances :

...
96.79 % - 332 fichiers traités sur 343 - 1154.91 secondes - 0.02 secondes - 0.06 secondes - 2.41 secondes
97.08 % - 333 fichiers traités sur 343 - 1155.16 secondes - 0.02 secondes - 0.06 secondes - 2.4 secondes
...
Temps total :  1242.6724437559988
Temps moyen minimal :  0.02707628248980636
Temps moyen idiot :  0.07159211618666317
Temps moyen heuristique3 :  2.52254837530026

Les informations affichées dans chaque ligne sont les suivantes :

• Pourcentage d'avancement : Le pourcentage de fichiers traités par rapport à l'ensemble des fichiers du dossier "instances_test".
• Nombre de fichiers traités : Le nombre de fichiers traités jusqu'à présent.
• Durée totale de traitement : La durée totale de traitement depuis le début de l'exécution du programme.
• Temps moyen de calcul de minorant : La moyenne des temps de calcul pour le calcul du minorant.
• Temps moyen de l'algorithme idiot : La moyenne des temps de calcul pour l'algorithme idiot.
• Temps moyen de l'heuristique : La moyenne des temps de calcul pour l'heuristique.

Sortie pour les 4 instances spécifiques

Lorsque l'utilisateur choisit de tester uniquement les 4 fichiers donnés, le programme affiche des informations détaillées sur chaque fichier traité, avec les informations sur le secteur, les étapes de résolution et les visualisations associées.

Voici un exemple de sortie pour l'instance TOY01.TXT :

TOY01.TXT
Sector size:                  4 4
Number of species:            3
Species requirements:         [11, 9, 26]
-----------------------------------
Minimum bound calculation    
Minimum bound:                3
Time:                         2.2059999992052326e-05
-----------------------------------
Resolution type:              IDIOT
Number of zones used:         6
Time:                         1.2259999948582845e-05
-----------------------------------
Check solution
Solution is valid:            True
Time:                         0.00033465800015619607
-----------------------------------
Visualization started
Time:                         0.3528760310000507
Visualization done
-----------------------------------
Resolution type:              HEURISTIC3
Number of zones used:         3
Time:                         0.00036784800022360287
-----------------------------------
Check solution
Solution is valid:            True
Time:                         0.0002658180001162691
-----------------------------------
Visualization started
Time:                         0.1976734699996996
Visualization done

La sortie pour les 4 instances spécifiques est la suivante :

TOY01.TXT
ARCHIPEL_2_10_10_2.TXT_HARD.TXT
LONG_ISLAND_10_500_500_7.TXT
LONG_ISLAND_10_500_500_7.TXT_HARD.TXT