Menu
EtoileAbonnementRSS
jeuxvideo.com  /  Tous les forums  /  Forum principal Informatique  /  Forum Programmation  /  Topic Problèmes algorithmiques avancés  / 

Topic Problèmes algorithmiques avancés - Page 3

Sujet : Problèmes algorithmiques avancés

DébutPage précedente
Page suivanteFin
godrik
godrik
MP
18 octobre 2015 à 21:49:39

ouais, quadtree, ca ne marche pas tres bien. ici...

dark_drow
dark_drow
MP
18 octobre 2015 à 21:54:17

ça faisait longtemps que je voulais explorer un truc ac les quadtree car il y a quelques applications sympa pour tout ce qui est 2D... par contre bof bof pour une solution optimale effectivement, je pense que c'est faisable de descendre à 10k avec des patterns mais je vois pas comment passer sous les 5k :o

Message édité le 18 octobre 2015 à 21:54:41 par dark_drow
godrik
godrik
MP
18 octobre 2015 à 21:58:13

mon premier run de quadtree etait vers 14000, j'ai laisse tombe une approche purement quadtree rapidement. Je fais un genre de truc hybride maintenant.

Egounet
Egounet
MP
18 octobre 2015 à 23:22:11

mon algo bloque à 2948, je vois qu'Ismael a pas dit son dernier mot il me rattrape petit à petit, il vient de passer la barre des 3000.

une petite astuce pour gagner quelques opérations d'entrée de jeu : boucher les trous de 1 pixels (diagonale pas prise en compte) et ajouter une commande erase en file d'attente. j'ai essayé de boucher les trous de n pixels mais il n'y a que 1 pixel qui est rentable.

Egounet
Egounet
MP
18 octobre 2015 à 23:23:00

Ah ben voila Ismael m'a gratté :rire: Il est temps de répliquer :diable:

godrik
godrik
MP
18 octobre 2015 à 23:25:51

C'est ce que je suis entrain de regarder. Mais tout les trous de 1 ne sont pas rentable je pense.

Egounet
Egounet
MP
18 octobre 2015 à 23:31:18

j'ai essayé les trous de 1 à 50 pixels et il n'y a que 1 qui fait gagner des opérations, à moins de développer un truc local peut-être...

godrik
godrik
MP
18 octobre 2015 à 23:42:28

nan, il y en a plusieurs, mais je ne sais pas comment il se combine.

godrik
godrik
MP
19 octobre 2015 à 01:29:31

un coup de postprocessing et me voila en 3eme place avec 3151

godrik
godrik
MP
19 octobre 2015 à 05:41:56

J'ai pose la question sur le site web aussi. Je ne vois pas de facon simple pour avoir une borne inf raisonnable.

Triple14
Triple14
MP
19 octobre 2015 à 14:34:18

Tcho, j'ai soumis ma solution pour Agar.IA.
1008, 8eme place (Thor3D) :(

Beaucoup d'effort par rapport à un simple greedy mais peu d'amélioration^^. Bon j'ai un algo à complexité linéaire, je suis content, et je peux maintenant chercher les paramètres optimaux...

Pour ceux que ça intéresse de visualiser la chose, voici une image du domaine + de la solution greedy (qui score 991) :

http://www.noelshack.com/2015-43-1445258028-mapagar.png

godrik
godrik
MP
19 octobre 2015 à 18:26:31

mmm, ca n'a pas l'air bien difficile ce Agar.IA, il faudrait que j'essaye.

Triple14
Triple14
MP
19 octobre 2015 à 21:26:50

mmm, ca n'a pas l'air bien difficile ce Agar.IA, il faudrait que j'essaye.

Je t'attend au tournant :noel:

godrik
godrik
MP
19 octobre 2015 à 21:37:25

bluepoint_, c'est souvent la base des algo d'approximation; c'est impressionant comment ca march ebien glouton.

Triple14, oui, il faut que je regarde les details. Mais j'avais plein de variantes pour TSP et VRP quand j'etais en DEA. Et la, ca n'a pas l'air tres different. Donc les memes approches devraient fonctionner.

Triple14
Triple14
MP
19 octobre 2015 à 21:45:05

Les acronymes à 3 lettres ne m'impressionnent pas^^
Non mais c'est vrai que ça ressemble énormément au TSP, et que du coup des algos "tout fait" sont peut-être facilement applicables, ce qui est dommage du point de vue du concours...

godrik
godrik
MP
19 octobre 2015 à 22:04:38

Les acronymes à 3 lettres ne m'impressionnent pas^^

Deosle, la force de l'habitude :)

Non mais c'est vrai que ça ressemble énormément au TSP, et que du coup des algos "tout fait" sont peut-être facilement applicables, ce qui est dommage du point de vue du concours...

Ces problemes ne sortent jamais vraiment de nul part. C'est pour ca que j'ai commence par "art optimal", c'est le seul qui ne me disait rien a priori. Les autres sont des problemes de pavages, des problemes de graphes biparti ou des problemes de clustering

Et en vrai, "art optimal" c'est de la compression d'image, C'est juste que perso, je n'avais jamais vraiment regarder. On vera ce que je ferai le week en prochain (probablement pas le temps de regarder avant)

godrik
godrik
MP
19 octobre 2015 à 22:23:35

art optimal, je ne sais pas bien. Ca ressemble a des problemes de compression d'image bitmap sous forme vectoriel.
Voici tes primiives vectoriel, trouve les primitives qui vont produire cette image bitmap. Et parceque le rendering coute cher, trouve le minimum de primitive.

Ismael a dit qu'il avait calculer le minimum snas effacement a 3095. J'aimerait bien savoir comment il a atteint cette conclusion. J'ai pas trouve d'argument clair a ca...

Egounet
Egounet
MP
20 octobre 2015 à 03:24:03

J'en suis à 3103 minimum sans effacement. Je vois comment descendre encore mais je suis pas convaincu que ça donne un optimum pour autant. Je vais tenter voir si ça donne 3095.

J'ai essayé des trucs plus poussés mais pour l'instant, comme le dit _bluepoint la méthode "barbare" fonctionne mieux en moins de temps c'est quand même étonnant.

Triple14
Triple14
MP
20 octobre 2015 à 10:23:21

whiteapplex : tu sais à quoi correspondent les couleurs ? Bêtement l'état du score ?

Egounet
Egounet
MP
20 octobre 2015 à 13:51:14

Ismael a peut-être raison, j'arrive aussi à 3095 au minimum sans erase sur art optimal, sans être certain que c'est le mieux qu'on puisse faire. Par contre après il m'éclate...

whiteapplex j'ai tenté aussi la prédiction sur plusieurs cellules, j'y suis pas arrivé mais c'est clairement une piste à creuser. sinon comme idée peut-être essayer de se diriger en priorité vers les zones à forte densité, et éviter de se retrouver dans une zone vide (une zone qu'on vient de vider en fait...).

DébutPage précedente
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 44,99€
Dragon Ball Z: Kakarot (PS4) Amazon 51,90€