Le 20 octobre 2015 à 12:46:09 whiteapplex a écrit :
J'arrive à 1051 en cherchant de façon idiote le plus court chemin entre deux points + de façon hasardeuse la prise du 2nd plus court chemin ou du troisième.

Tu veux dire que t'as fait un algo glouton qui de manière aléatoire va parfois au 2 ou 3eme point le plus proche de la position en cours (au lieu d'aller systématiquement au + proche) ?
Je l'ai fait et j'ai jamais réussi à battre le glouton non-aléatoire avec cette méthode Là j'en suis à 1026 de meilleur score, je rage :fu:

Mon plan pour agar.ia est:
-greedy pour avoir une idee
-greedy distance 3 pour avoir une meilleure idee.
-monte carlo pour cree des bouts de chemins pas trop con
-algo genetique pour faire de l'assemblage.

Testé agar.ia, pas réussi à faire mieux que 1034, sachant que mon algo regarde juste le chemin le plus court possible pour bouffer les 3 prochaines cellules parmi les 50 cellules les plus proches (si je me suis pas planté quelque part)

J'y connais pas grand chose en algorithmique (autodidacte et quasiment à 100% dans la programmation de jv), et par exemple quand ça parle de "greedy", "monte carlo" ou "algo genetique", j'y comprend absolument rien, pour citer les exemples du message de godrik

Donc je fais tout "au feeling" sans utiliser de méthodes déjà vues auparavant, et je me demandais si c'était seulement possible de trouver de vraiment bonnes solutions à ce genre de problème en étant dans ce cas, si vous faites aussi comme ça ou si vous vous servez de vos connaissances.

En gros pour être sur le podium niveau score, à votre avis, on est obligé de connaître des algos de base ou on peut tout déduire simplement avec de la persévérance et de la logique?

A note aussi que les approches a base de monte carlo ont ete tres efficace pour des problemes complique comme le jeu de Go par exemple. L'idee est que pour estimer la "force" d'une position, tu termines la partie en jouant des coups aleatoire. L'idee etant que si la position est forte pour joueur 1 alors statistiquement il devrait gagner plus souvent en finissant par des coups aleatoires.

Les algo genetiques, c'est simple en principe. Tu pars d'un pool de solution et tu essaye de les recombiner entre elles pour trouver une solution meilleur. L'idee est que tu pourrais avoir des solution qui sont bonne au debut de la solution et d'autre qui sont bonne a la fin de la solution. Et donc en les melageant tu pourrais obtenir une solution qui est bien partout.

Hexabeast, je ne sais pas si il faut imperativmeent connaitre ces trucs la pour bien s'en sortir. Mais ca aide beaucoup a guider les premieres approches que tu as.

Globalement je pense que des greedy sont pas mal pour commencer. Mais il faut quasiment toujours se tourner sur des algo plus "brutaux" pouraller plus loin.

Ok merci à vous deux pour ces infos

pour artoptimal j'avoue qu'une solution basique permet finalement d'arriver vers 4000. Par contre pour passer à 3000- ça à l'air plus coton

oh, tu peux voir l'historique de tes scores. Je ne savais pas ca...

Le 21 octobre 2015 à 13:32:29 whiteapplex a écrit :
Avec 20.000 points placés de façon aléatoire sur des positions allant de (-10k,-10k), à (+10k,+10k), quel est le nombre de points maximum pour avoir une distance cumulé de 100.000?

Ça dépend de comment ils sont placés, s'ils sont "par hasard" tous très proches on peut faire un score max de 20 000, et s'ils sont tous répartis de façon à être écartés le plus possible, de façon homogène, y'a un score max qui sera plus bas et qu'on peut certainement calculer.

Entre ces deux extremums le score max va varier selon les cas, il n'a pas de valeur fixée.

Donc la question c'est quel est le score max dans la disposition précise qu'on nous donne sur le site, et si on avait la réponse on aurait le meilleur score

20,000 points c'est pas forcement tant que ca. Les argument bornes inf/bornes usp sont assez puissants sur ces problemes la. Ca pourrait se brute forcer pas si mal que ca. Un branch and bound sur un ILP passe la plupart du temps a prouver qu'une solution est optimale plus qu'a trouver une meilleur solution. Perso, j'y crois assez
On verra ce week end ce que je fais.

CPlex en continue gere 400 millions de variable sans probleme. En entier, c'est plus chaud. mais note que quand tu en fixes une a 1, tu en fixe 19,999 a 0. Donc ca aide bien Aussi le probleme a des proprietes geometrique qui sont probablement utilisable pour simplifier les calculs. Il faut que je pose ca proprement.

Je ne parles pas de resoudre le probleme optimalement et avec garantie. Mais a mon avis tu peux faire quelque chose qui converge rapidement avec un gap-estimate faible.

Le 21 octobre 2015 à 16:16:43 whiteapplex a écrit :
Ouais hexa mais j'aurais cru qu'il y aurait des lois pour connaitre le maximum dans le cas général de points placés aléatoirement.
Et connaitre le nombre de points maximum atteignables ou son approximation implique pas forcement de connaitre la réponse x)
C'est l'inverse qui est forcement correct

Dans le cas d'un placement aléatoire justement il faut connaître le meilleur chemin possible pour connaître le nombre max de points atteignables, donc si on connais le max de points atteignables c'est qu'on a trouvé le plus court chemin possible, soit la réponse.

Et il n'y a pas de cas "général", sauf si tu cherches une loi de probabilité, et t'auras sûrement une courbe dans le style loi normale; sinon si tu cherches LE maximum ce sera que pour UN cas de placement de points en particulier et trouver le maximum équivaudra à trouver le chemin le plus court.

Oui c'est ça, c'est juste que tu disais "LE maximum" ou "LA valeur maximum" alors qu'en réalité si j'ai bien compris tu parles de l'espérance de la loi de probabilité en jeu ici, soit une valeur moyenne des maximums d'éléments atteignables (en se déplaçant de 100000 unités maximum) sur un très grand nombre de "positionnements d'éléments" différents.

Et comme tu dis c'est de l'approximation, donc ça permettrait absolument pas de trouver avec certitude le maximum dans le cas particulier du site, tout ce qu'on pourrait en retirer ce serait un intervalle de confiance qui ne serait de toutes façons toujours pas fiable à 100%

D'ailleurs je comprend ce que t'as voulu montrer avec ton raisonnement, mais vu comme c'est dit on dirait que ta distance M c'est la distance moyenne entre 2 éléments quelconques, ce qui rend la suite absurde (si je suis le seul a avoir d'abord interprété ça comme ça désolé du commentaire )
Donc si je me plante pas, ici M devrait être la distance moyenne séparant un élément et l'élément le plus proche de celui-ci, mais je suppose que c'est ce que t'as voulu dire. J'ai pas la certitude absolue que ce soit ça mais ce serait déjà bien plus logique.

C'est malin maintenant j'ai mal à la tête

Joli score whiteapplex ! Toujours un algo greedy-probabiliste ? Quand tu dis que c'est lent, ça veut dire quoi ?^^
Perso j'ai essayé de faire un greedy qui va à chaque fois vers le point de plus gros score, le score étant obtenu via une heuristique qui en gros est : distance_au_point_en_cours * score_de_clustering_du_point_cible. Mais c'es très lent, puisque la mise à jour dynamique des coeff de clustering de chaque point est en O(n²), l'algo au final est en O(n³)... J'ai 1061 de meilleur score seulement.

Mais c'es très lent, puisque la mise à jour dynamique des coeff de clustering de chaque point est en O(n²),

Mais non ! C'est en O(N), pense incremental! Au lieu de recalculer les coef de clustering de chaque point, ajuste la valeure qu'ils ont compte tenu que tu as retirer un point de la grille.

C'est ce que je voulais faire au début, et c'est vrai que je devrais essayer d'y revenir.
Le truc c'est que si le coefficient de clustering d'un point donné P ne tient compte que des K points les plus proches de lui, alors on peut plus penser incrémental car si un point parmi les K est enlevé, il va falloir aller chercher le nouveau. Et pour vérifier si le point Q enlevé faisant partie de l'ensemble des K points sur lesquels le clustering de P a été calculé, il faut checker parmi tous les N points du problème si Q faisait partie des des points ayant servi a calculer leur clustering.

En pratique j'ai obtenu de meilleurs résultats avec K ~ 1000, les plus grandes valeurs (jusqu'à 10'000) ne donnant pas de meilleurs résultats. Mais maintenant que j'ai rendu mon algo probabiliste, je devrais essayer de revenir à une version sans paramètre K (clustering sur les N points), ce qui permettrait de redescendre les mise à jour de clustering score en O(N)...

bah c'est pareil du coup. Tu construis le graph de k-Nearest-Neighboor. Tu transpose le graphe et ca te donne pour chaque point P la liste des point P' tel que P' est un des k-NN de P.

Ok mon algo sans clustering en est aussi à un chemin toutes les minutes je dirais... Je l'avais fait en python au début, puis réécrit en C++ juste pour voir, et j'ai pas observé de véritable différence de performance. Il tourne plutôt autour des 1010 en moyenne. J'en suis à 1080 de meilleur score. Mais j'ai encore des idées :p

1139

Godrik t'as eu le temps de t'y pencher ?

Bon alors je vais gentiment m'arrêter aussi. 1168, dernier score en date probablement.

Nan finalement j'ai pas regarder ca le week end dernier. J'avais des copies a corriger, j'ai fait un tennis. Pas eu le temps.
Et ce week end, je dois generer des instances d'un probleme de machine learning pour un collegue.