salut tout le monde!
j'avais demandé de l'aide pour affiner mon TIPE sur ce topic https://www.jeuxvideo.com/forums/42-35-39473508-1-0-1-0-help-affiner-mon-tipe-classe-mp.htm
et j'ai donc passé l'oral devant les profs
donc ils m'ont donné quelque conseil pour la présentation de mon code ect... mais mon prof a soulever un point qui est extrèmement important selon lui que je n'es pas assez abordé : " lorsque la solution optimale
n'est pas calculable, comment peut-on estimer qu'un résultat rendu par l'algorithme aléatoire est proche ou non de la solution optimale que l'on ne connaît pas?"

donc j'ai réfléchi la dessus, à faire tourné plein de fois le programme aléatoire et tracé un graphique de chaque résultat renvoyé pour se faire une idée, mais ça sera juste expérimentale sans calcul

après je vois pas trop comment faire, parce que calculer la probabilité que l'algorithme aléatoire rende la solution optimale me semble un peu compliqué non?

l'algo fonctionne comme ça
je veux la liste des objet ayant une somme totale de valeur maximum avec un poids inférieur a 100
j'ai une liste d'uplet [valeur,poids]
je parcourt la liste, si le poids est inférieur à ce qu'il me reste j'ajoute l'objet sinon je passe au suivant

ça c'est mon algo principale

après je part du principe qu'il existe des combinaisons de ces objet qui fait que mon algo principale renvoit le bon résultat (par exemple, la liste des objet que je prend suivit des autres, elle marche forcément)

donc l'algo optimale teste sur toutes les combinaisons possible

mais si le nombre augmente on a plus le résultat optimale connu, je test donc sur des combinaisons aléatoire de mes uplets, plus le nombre de test augment plus je m'approche du résultat optimale

voilà en gros ce que fait mon algorithme

ba en gros j'ai une liste du tipe [[4,42],[7,53],[1,7],....]
je parcourt cette liste, si le poids de l'objet est plus petit que le poids totale restant je l'ajoute
ici j'ai 42<100 donc j'ajoute l'objet, 53<100-42=58 donc j'ajoute, 7>58-53=5 donc j'ajoute pas... jusqu'à la fin de la liste

et donc pour l'aléatoire, je mélange aléatoirement ces uplet un certain nombre de fois, et à chaque fois je test avec mon algo principale, et je garde la meilleur des solutions testé

quel genre de configuration? pour moi l'aléatoire a toujours bien marché

ouai je les ordonne parce que j'ai pas le temps de tout repensé, j'ai essayé mais le résultat non ordonné est beaucoup plus long d'application (je sais pas pourquoi j'ai du mal programmé, j'ai pourtant du 2^n au lieu de n! mais le temps d'exécution est 10 fois plus long)

ouai je vois mais bon ce genre d'exemple sont des cas un peu spéciaux, à chaque fois que je test, ma liste d'uplet est généré aléatoirement, et le poids total est toujours 100 dans mes programmes, donc bon je peux considéré que des exemples comme le tient ont quand même très peu de chance de se produire
enfin on va le dire comme ça

Ça risque d'être assez difficile d'avoir une garantie sur la qualité de l'approximation, avec cet algorithme là. Comme dit bluepoint, ça revient juste à choisir des objets au hasard et les mettre dans le sac, sauf qu'en plus tu le fais de manière pas très efficace (tu mélanges toute ta liste d'objets à chaque tentative, alors que tu vas peut être regarder que les deux objets de devant et donc ça servait à rien d'avoir mélangé le reste...).

Ce que ton prof attendrait, ça serait une garantie du style "Si la solution optimale a pour valeur V, mon algo renvoie une solution de valeur > V/k avec probabilité p", où de préférence k est petit et p est grand.

Là avec ton algorithme, l'efficacité va beaucoup dépendre de ce à quoi ressemble ta liste d'objets. Typiquement, s'il y a 10 000 gros cailloux et une pièce d'or dans ta liste, ton algo aléatoire va avoir du mal à trouver une bonne solution.

Ce que tu pourrais dire, c'est que si les objets se ressemblent (par exemple, si le rapport valeur/poids ne varie pas trop d'un objet à l'autre), alors ton algo renvoie des trucs pas trop mal. Mais c'est pas très convaincant comme garantie parce que "le rapport valeur/poids ne varie pas trop" veut juste dire que quoi que tu fasses, tu vas pas trop t'éloigner de la solution optimale...

Au final je vois deux solutions à ton problème :

• Faire des graphiques pour dire "ça marche bien en pratique", et ne pas aller trop en profondeur dans l'analyse pour pas que l'examinateur se rende compte que ton algo est nul
• Changer d'algorithme

Une idée un peu moins pessimiste :

Tu gardes ce que tu as codé pour l'instant, mais tu rajoutes une deuxième solution qui consiste à trier ta liste d'objet de façon à avoir un rapport valeur/poids décroissant, puis lancer ton "algorithme principal" sur cette liste triée. Ça te donne une 2-approximation ( cf http://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm ), ce qui rend ton prof content.

Après, tu peux faire des graphiques pour confronter tes deux solutions, en mesurant l'efficacité de la solution, et le temps d'exécution. A priori la méthode "triée" sera plus rapide (vu que tu ne fais qu'un essai au lieu de plein d'essais aléatoires), reste à voir si la méthode "aléatoire" renvoie des solutions un peu meilleures en pratique.

http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos#Algorithme_glouton
Le lien en français est plus complet que celui en anglais, pour une fois

ouai je me rend compte que l'algo est pas top dasn la théorie, mais comme le dit lowenheim en pratique il donne des résultats concluants, parce que justement le rapport valeur/poids est en effet pas beaucoup différent d'un objet à l'autre en général puisque c'est généré aléatoirement

après franchement je me vois pas tout recoder, je préfère me concentré sur les math/physique avant les oraux, et j'ai déjà essayé un algo qui en théorie est beaucoup plus rapide (ne prend pas en compte l'ordre des objet mais juste si un objet est dans le sac ou pas, donc 2^n, mais comme je l'es dis, il ne marche pas mieux que mon premier algorithme surement par une programmation trop lourde)
du coup je veux pas forcément perde tout ce que j'ai fait et mon temps pour ça, je pense quand même gardé cet algo même si il est pas tip top, il renvoie encore une fois de bon résultats graphique, donc j'essaierai de faire illusion

bon j'avais déjà cette version de calcul par le rapport valeur/poids, mais j'avais pas le fait que la borne inférieur est m/2, c'est compliqué a prouvé ce résultat?

Non en fait c'est pas une 2-approx, le lien en français explique que ça peut renvoyer un résultat arbitrairement mauvais. La 2-approx, c'est dans le cas où on considère que chaque objet est disponible en quantité illimitée, mais là kilagg a juste un exemplaire de chaque.

A mon avis faut pas qu'il parle de k-approximations, même si c'est le genre de trucs qu'attendait son prof, à moins de tout recoder ce qui n'est pas très avisé juste avant les oraux, son algo n'en sera pas une. Je dirais que coder l'algo glouton et faire une étude comparative en pratique des deux solutions ça demande pas trop de temps au niveau code (ça prend littéralement une ligne si t'utilises List.sort en caml, un peu plus si tu recodes le tri toi même), et ça peut rendre ton tipe significativement plus intéressant.

okay dac je vais pas en parlé alors, de toute façon si j'en parle, les profs m'aurait branché dessus pour les question, et je sais pas jusqu’où j'aurais pu répondre