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 2

Sujet : Problèmes algorithmiques avancés

DébutPage précedente
Page suivanteFin
bonplanpizza
bonplanpizza
MP
16 octobre 2015 à 23:59:43

Bravo bluepoint, en effet on avait pas remarqué que le problème consistait juste à trouver un élément du noyau d'une matrice. Désolé pour cette erreur ! On espère que les autres problèmes (à part Pokémon) sont de bons problèmes :)

N'hésitez surtout pas si vous avez des idées de problèmes. Toute la difficulté est de trouver des problèmes qui permettent d'obtenir une répartition des scores bien étalée, et en essayant de pas se gourrer comme ici ^^

bonplanpizza
bonplanpizza
MP
17 octobre 2015 à 00:14:31

Ils ont l'air de dire ici : http://math.stackexchange.com/questions/361046/minimum-distance-of-a-binary-linear-code que c'est difficile. Il faudrait rendre le problème amusant !

Sinon on a mis de côté les 2 problèmes où la solution optimale avait été trouvée, les scores ne comptant pas dans le classement.

bonplanpizza
bonplanpizza
MP
17 octobre 2015 à 00:26:58

Ah oui tu as raison ! Tu recommandes quels paramètres ?

Les gens vont perdre leurs scores du coup, j'espère qu'ils seront pas trop déçus.

bonplanpizza
bonplanpizza
MP
17 octobre 2015 à 00:40:47

:p ok je modifierai demain du coup, faudra qu'on en parle avec l'ami avec qui je crée le site :)

godrik
godrik
MP
17 octobre 2015 à 07:51:26

Bon, j'ai envoye mon papier. Peut etre que je vais regarder le probleme de l'image ce week end.

bonplanpizza
bonplanpizza
MP
17 octobre 2015 à 12:36:23

Super merci beaucoup c'est éclairant !

Une nouvelle version du problème est disponible ici : http://primers.xyz/6

n = 1000, k = 500, avec 300 interrupteurs indépendants

bonplanpizza
bonplanpizza
MP
17 octobre 2015 à 12:55:47

J'ai l'impression que c'est pas équivalent, mais ça a quand même l'air NP-dur non ?

En termes de codes linéaires ça revient à trouver un codeword de poids maximal, problème qui a l'air assez peu documenté.

Message édité le 17 octobre 2015 à 12:58:46 par bonplanpizza
bonplanpizza
bonplanpizza
MP
17 octobre 2015 à 13:13:43

C'est bien NP-complet ! (https://books.google.fr/books?id=s0RsCQAAQBAJ&pg=PA106&lpg=PA106&dq=codeword+of+maximal+weight&source=bl&ots=c1wBgVIldn&sig=1LAVVDilldHA6Hh2bijzhrwjI5w&hl=fr&sa=X&ved=0CDMQ6AEwAmoVChMIkq3zz6_JyAIVCJwaCh1TOgQA#v=onepage&q=codeword%20of%20maximal%20weight&f=false)

Ne pas changer l'énoncé est plus pratique :p et c'est moins perturbant pour tous ceux ayant déjà joué sur ce problème

[edit] Mmm quelqu'un a fait 1000...

Message édité le 17 octobre 2015 à 13:17:28 par bonplanpizza
bonplanpizza
bonplanpizza
MP
17 octobre 2015 à 14:08:18

Théoriquement il est très peu probable que le vecteur unitaire soit atteignable, et de même pour les vecteurs proches de celui-ci.

J'ai enlevé les 200 interrupteurs liés, pour ne garder qu'une famille libre de 300 interrupteurs, et on dirait que le problème est résolu.

Ça reste mystérieux pour moi, je ne comprends pas comment ajouter des interrupteurs liés peut rendre le problème plus facile. Il se peut que le problème vienne du code de génération de l'input, mais j'ai pourtant revérifié plusieurs fois !

godrik
godrik
MP
17 octobre 2015 à 16:21:05

Le plus simple pour generer des instances difficile est d'ecrire la reduction depuis un autre probleme et de choisir les reductions des instances qui sont connues pour etre difficile. (Ca serait encore mieux de prendre des problemes avec des "gap preserving reductions" pour aussi garder les prppriete sur les problemes d'optimization associes)

Si tu cherches des problemes rigolo, il y a aussi les problemes d'organisation de competition sportive qui peuvent etre rigolote (et qui sont ridiculement difficile).

bluepoint, le papier est sur des histoires d'evaluation de performance d'algo de graph sur GPU et cluster.

godrik
godrik
MP
17 octobre 2015 à 17:56:15

Ahah, je viens de faire ma premier soumission au probleme "art optimal". J'ai fait 84784 :) C'etait surtout pour verifier que je faisais mes IOs comme il faut.

godrik
godrik
MP
17 octobre 2015 à 18:53:46

whiteapplex, yep. Il faut bien tester tes IO a un moment donne! :) Je commence facil et on verra les trucs bizarre a faire.
Je ne vois pas bien quel genre de bornes inferieur on peut utiliser ici.

Tu as pris quel pseudo sur le siteweb?

Message édité le 17 octobre 2015 à 18:55:19 par godrik
godrik
godrik
MP
17 octobre 2015 à 20:53:08

bon, un petit coup de greedy et ca descend a 3350.

godrik
godrik
MP
18 octobre 2015 à 19:36:10

bon, j'ai travaille hier sur le probleme art optimal. Et punaise, ca devient difficile.

J'ai essayer des methodes constructives et je suis descendu a 3251. C'est un peu deprimant quand on voit que mon premier algo non naif faisait 35xx. Ca pourrait bien etre le moment de passer a des methodes plus bourines.
deux pistes:
-bruteforer les petites instances.
-des methodes d'optimisation locales.

dark_drow
dark_drow
MP
18 octobre 2015 à 20:01:15

Je m'en sort pas avec l'output à renvoyer, et pourtant quand je reconstruis ma sortie j'ai bien la même image qu'en entrée >.<

godrik
godrik
MP
18 octobre 2015 à 20:13:12

Si la solution n'est pas bonne, le site de soumission te donne les coordonne de 1 pixel qui n'est pas bien colorie. Tu as essayer de tracer ca ?

Donne un exemple de ta sortie pour voir.

dark_drow
dark_drow
MP
18 octobre 2015 à 20:25:35

oui, j'ai : l'image est mal peinte en 416,0
sauf que c'est écrit en dur "FILL,416,0,1" dans mon output et image[416][0] = "#" dans l'input
mais bon par contre je viens de remarquer que j'ai un bug :p

godrik
godrik
MP
18 octobre 2015 à 20:56:29

heu, non, 416,0 c'est vide. Tu as inverser les lignes et les colonnes je pense.

dark_drow
dark_drow
MP
18 octobre 2015 à 21:20:55

art oui je sens que c'est ça >.<
FILL,10,0,1 pour moi ça prenait la 11e ligne, 1er caractère (avec les indices qui commencent à 1)

dark_drow
dark_drow
MP
18 octobre 2015 à 21:30:36

double-post: effectivement c'était ça ! J'y ai passé l'après-midi mais ça m'a permit de développer un quad-tree basique en TDD (chose que je n'avais pas assez expérimenté) en python
Assez ludique la réponse du site, par contre j'ai du boulot, je commence à 18k instructions

Message édité le 18 octobre 2015 à 21:31:05 par dark_drow
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
Dragon Ball Z: Kakarot (PS4) Amazon 51,90€
Nintendo Switch avec paire de Joy-Con Rouge Néon et Bleu Néon Amazon 292,90€
Luigi's Mansion 3 Amazon 44,49€