Menu
EtoileAbonnementRSS
jeuxvideo.com  /  Tous les forums  /  Forum principal Informatique  /  Forum Programmation  / 

Topic Problèmes algorithmiques avancés

Sujet : Problèmes algorithmiques avancés

Page suivanteFin
bonplanpizza
bonplanpizza
MP
12 octobre 2015 à 17:00:51

Bonjour à tous,

Si vous aimez les problèmes algorithmiques dont il n'est pas possible de trouver la solution optimale en temps fini, n'hésitez pas à faire un tour sur http://primers.xyz ! C'est un site inspiré de la compétition du Google Hash Code où l'objectif est de faire le meilleur score possible sur chaque problème.

godrik
godrik
MP
12 octobre 2015 à 19:17:49

ah c'est rigolo ca. C'est des problemes d'algo classiques reformule pour etre plus "sexy". Merci du lien.

Delgan
Delgan
MP
12 octobre 2015 à 19:34:27

Hey, c'est super sympa comme site, merci du partage ! :)

Triple14
Triple14
MP
13 octobre 2015 à 14:06:56

Ca a l'air cool !

Qui est chaud pour m'affronter sur l'un des problèmes ? :banzai:

Triple14
Triple14
MP
13 octobre 2015 à 15:04:59

Arf je viens de commencer le Agar.IA.

Par contre, on est d'accord que, les instances des problèmes étant des entités finies, rien n'empêche quelqu'un de faire une brute force et de trouver la meilleur solution de cette manière ? Et du coup il a le meilleur score, étant donné que la performance de l'algo entre pas en compte. Je sais que c'est pas l'esprit du site, mais on est bien d'accord ?^^

Message édité le 13 octobre 2015 à 15:05:21 par Triple14
godrik
godrik
MP
13 octobre 2015 à 15:06:06

pour art, en premiere solution ca donne furieusement envie de construire un quadtree et de n'utiliser que fill.

en deuxieme solution tu rajoute une heuristique a chaque noeud qui soit fait le truc du quadtree soit fill toute la zone et clear les pixels qui ne vont pas.

c'est bizarre comme probleme parceque clear n'est pas en carre, mais en pixel...

collax
collax
MP
13 octobre 2015 à 15:21:30

Pour art optimal,vu que la seule contrainte c'est de faire le minimum d'operations de Fill et de Erase, une solution peut être de faire du backtracking, d'attendre 10 ans et de lui donner la solution optimale à la fin :hap:

Triple14
Triple14
MP
13 octobre 2015 à 15:34:07

Colllax : ==> c'est ce que je dis. Après j'ai pas étudié la complexité précise du problème, si ça se trouve même sur une machine parallèlle l'instance du problème est pas bruteforcable en moins de quelques années ^^

godrik
godrik
MP
13 octobre 2015 à 15:51:55

Triple14, compte tenu que ca vient d'un concours de google, j'imagine qu'ils ont penser a se proteger du bruteforce.

NdM: Ca vous dirait de faire un topic par probleme qui vous interesse et de debattre d'algo pour les resoudre?

godrik
godrik
MP
13 octobre 2015 à 17:54:29

Ouais, il y a des problemes qui ont l'air interessant. je pense que je regarderai ca d'un peut plus pres quand j'aurais un peu plus de temps. (La semaine prochaine peut etre.)

En plus, j'ai un cluster de GPU sous la main, donc si j'ai envie de bruteforcer des bouts, ca pourrait bien se faire.

Vous savez si il y a une version anglaise du truc?

NdM: J'ai mis le topic dans la liste des topics a ne pas manquer.

Message édité le 13 octobre 2015 à 17:55:11 par godrik
-MrPocolo
-MrPocolo
MP
13 octobre 2015 à 18:06:19

En anglais il y a projecteuler.net que la plupart des gens ici connaissent probablement déjà, c'est plus ou moins la même chose mais avec beaucoup plus de problèmes et le côté "mignon" en moins.

godrik
godrik
MP
13 octobre 2015 à 19:47:08

Si quelqu'un traite le problem d'art, il pourrait etre interessant d'avoir une visualization de comment l'algo se deroule. une simple visualization des iterations serait suffisante. Quelqu'un motive pour faire ca?

Triple14
Triple14
MP
14 octobre 2015 à 00:01:47

Je veux bien faire celui du coloriage.
Mais après avoir amélioré mon score au Agar.IA :sournois:
Avec un bête algo greedy on arrive facilement à 991... mais après c'est plus dur^^

Chnapy
Chnapy
MP
14 octobre 2015 à 00:21:14

Dans le même style il y a codingame.com

godrik
godrik
MP
14 octobre 2015 à 21:37:49

Ca ressemble a des probleme de theorie des codes.

Il y a une famille de descente locale evidente:
1/ "trouve l'interupteur qui si tu le switch change allume le plus de lumiere supplementaire"
2/ "trouve la pair d'interrupteur qui si tu le switch ..."
3/ "trouve le triplet d'interrupteur, ..."

Mais concretement un truc comme ca, ca donne furieusement envie d'essayer des algo genetiques.

_bluepoint
_bluepoint
MP
14 octobre 2015 à 22:31:23

Ouais, si on échange les 0 et les 1, je dirais que ça revient à trouver la distance minimale d'un code linéaire..

Sinon avec un bête mélange d'aléatoire et de glouton on tape déjà dans le 140+, même avec des trucs pas rapides en python.
Ptet envisager une approche plus mathématique pour la suite :)

Ah sinon si vous voulez faire des tests simples avec matlab vous pouvez utiliser gf(truc,2) qui fait que truc est considèré comme élément de GF(2) et donc toutes les opérations seront faites modulo 2

_bluepoint
_bluepoint
MP
14 octobre 2015 à 23:14:02

C'est ce qu'a dit godrik :)

Egounet
Egounet
MP
15 octobre 2015 à 17:32:12

Salut, sympa ce petit concours ! :)
J'en suis à 3546 sur art optimal (gratté par un certain Ismael) avec une méthode assez barbare en deux passes :

- 1ère passe, on parcours tous les pixels à dessiner, un par un, et on regarde la taille max du carré qu'on peut faire à partir de ce pixel (le carré s'étend en +x et +y) donc sans dépasser du dessin. Si le carré est intégralement compris dans un carré précédent on ne le garde pas, ça fait un premier tri.

- 2nde passe, on parcours chaque carré ainsi créée, et on regarde si en le supprimant, les autres carrés comblent sa surface. Si c'est le cas on le supprime, sinon ça veut dire qu'au moins un pixel du carré est "unique" à ce carré.

C'est vraiment loin d'être optimal, il n'y a pas d'analyse c'est fait à la volée. Le résultat change selon le sens ou on parcours les pixels et où on crée les carrés, peut-être qu'Ismael utilise le même genre de truc avec un sens optimisé pour cette image. J'ai quand fait un petit programme pour visualiser la chose : http://dl.free.fr/fE9WcsjBp

J'ai aussi un score sur agar.ia, mais là aussi c'est du bricolage :nonnon: Les autres m'inspirent moins... Partagez si vous avez des astuces sur les problèmes.

bonplanpizza
bonplanpizza
MP
16 octobre 2015 à 23:32:05

Super merci à tous pour le feedback !

Bonne idée pour la visualisation des carrés sur Art optimal, j'ai ajouté sur le site une représentation de la solution lorsqu'on en soumet une sur ce problème (et aussi sur Glaces à gogo) :)

Si vous avez des idées de problèmes ou des suggestions pour le site n'hésitez pas :)

godrik
godrik
MP
16 octobre 2015 à 23:48:54

Ben oui, du coup j'aurais une question, c'était quoi le problème théorique qui était censé être derrière illuminations ? J'ai l'impression qu'il y a eu un petit soucis au moment de le convertir en problème pratique.

Ca ressemble a un probleme de theorie des codes. Compte tenu un code lineaire (genre de haming), construit une entree du probleme qui produit une sortie particuliere.

Pasque je croyais que le but du jeu c'était de trouver des solutions approchées à des problèmes, euh, difficiles au niveau combinatoire.

(c'est quoi l'équivalent français de computationally hard ?)

Je ne sais pas si il y a un vrai equivalent. Quand je parles a des informaticiens, j'utilise "NP-Hard". Et quand je parles a des non-informaticien, j'utilise juste "combinatoire"; un coup de google montre que certains ont l'air d'utiliser "fortement combinatoire".

Page suivanteFin
Répondre
Prévisu
?
Victime de harcèlement en ligne : comment réagir ?
Infos 0 connecté(s)

Gestion du forum

Modérateurs : godrik, LGV
Contacter les modérateurs - Règles du forum

Sujets à ne pas manquer

Boutique
Nintendo Switch avec paire de Joy-Con Rouge Néon et Bleu Néon Amazon 299,98€
Luigi's Mansion 3 Amazon 60,69€
Ring Fit Adventure pour Nintendo Switch Amazon 59,99€