Fields... - Page 1

Petite question qui me trotte dans la tête au sujet d'Ingress.

Les points sont raccordés entre eux par des liens et 3 liens peuvent former un field.

La règle est assez simple : on ne peut pas croiser deux liens et on ne peut pas tirer un lien depuis l'intérieur d'un champ.

Si j'ai un triangle ABC avec un point D au milieu, pour optimiser, je peux faire AB, AD, DB, BC, CA, CD (et DC n'est pas possible vu que le champ existe déjà) et je me retrouve avec 4 champs (donc autant de points).

Sachant que depuis un point donné on ne peut tirer que 8 liens maxi, je me demandais s'il était possible de faire un petit programme qui à partir d'une liste de points (X, Y) soit capable de sortir le meilleur plan de fields et l'ordre des opérations pour le tisser.

je ne sais pas

Il faut des vrais matheux calés en théorie des graphes.

Et le problème est peut être indécidable...

Pareil, je suis pas assez matheux. Mais effectivement, ça ressemble fortement aux problèmes de théorie des graphes.
Par exemple : http://en.wikipedia.org/wiki/Delaunay_triangulation (mais je sais pas si ça respecte tes critères)

Y'a bien quelqu'un qui pourrait probablement t'aider, mais il aime pas les jeux propriétaires

Au passage, tu as combien de points ? C'est pour savoir si on peut utiliser de la force brute ou pas.

C'est pas que les points, c'est aussi pour la défense, y'a une mitigation en cas d'attaque entre les portails liés, et un bon maillage rend la structure plus solide.

Ouais, mais ça dépend : c'est quelques dizaines, quelques centaines, quelques milliers, plus ?

Et c'est quoi un "bon" maillage ? J'ai compris qu'il y avait un nombre maximum de segments qui partent d'un point, mais il y a quoi d'autre ? Faut maximiser la surface des triangles ?

un maximum de triangles, dont le maximum se recouvrent, parce que des règles précises qui permettent de les recouvrir si on crée les arêtes dans le bon ordre.

Voir une ébauche ici
http://ingress.wikia.com/wiki/Control_Field

Pour l'ordre de grandeur, Paris, c'est 10'000 portails, mais si je parvenais à le faire sur une centaine à la fois ça pourrait être largement suffisant

Y'a un truc qui m'échappe, je ne vois pas comment on peut concilier ça :

vince (./1) :
La règle est assez simple : on ne peut pas croiser deux liens et on ne peut pas tirer un lien depuis l'intérieur d'un champ.

et ça :

squalyl (./6) :
un maximum de triangles, dont le maximum se recouvrent,

Pour moi, avec les règles de Vince, on obtient que des triangles qui ne se recouvrent pas.

tu peux tirer un lien depuis un portail sur le bord d'un field existant, ils sont considérés comme a l'extérieur.

triangle ABC avec D au centre, tu linkes

A->B
A->C
B->C
A->D
B->D
C->D
(par ex et si j'ai bien compris, je ne suis qu'un padawan )

Oui c'est bien ça

On peut peut être tenter une triangulation de delaunay, ca donnerait un maillage triangulaire le plus "régulier"possible, mais sans superposition, puis détecter les situations où on peut faire des fields superposés.
Ou choisir manuellement les points "internes"qui servent a faire des fields superposés.

Je veux bien essayer de résoudre le problème mathématique, mais ne connaissant pas le jeu, je n'ai rien compris à vos descriptions (pas très mathématiques) du problème.

(Rien compris à la description du problème aussi)

lisez la page wikia. l'objectif est de faire un max de triangles sur un ensemble de points, avec des conditions qui autorisent a les superposer.

URL?

Le probleme est NP complet et pas simple a resoudre meme en brute force

[citation needed]

Mes propre recherches la dessus

Bon, prenons un exemple avec 5 portails (points) A B C D E.


Premier cas (en haut à gauche), pas très rentable (le premier point ne peut être à l'intérieur d'un field) :
AB
AE
AD
DE(on a créé le field AED)
DC
EB(on a créé le field ABE)
EC(on a créé le field CED)
CB(on a créé le filed BCE)

=> 4 fields

L'opération "correcte" est de faire plusieurs couches (en bas)
AE
AD
ED(on a créé le field AED)
AC
DC(on a créé le field ACD)
CE(on a créé les fields DEC et CAE) (je ne peux pas faire EC parce que E est à l'intérieur de ACD)
CB
AB(on a créé le field ABC)

Le bon schéma mais pas dans l'ordre peut tout gacher (en haut à droite) :
AE
AD
ED(on a créé le field AED)
AC
EC(on a créé le field AEC)
DC(on a créé le field DEC)
CB
AB(on a créé le field ABC)
=> 4 fields seulement alors que le schéma est le bon


Le problème consiste donc à trouver le bon maillage et en plus à indiquer quel ordre pour la création des liens.

Ah, j'oubliais, il y a une autre limite : depuis un portail on ne peut tirer que 8 liens alors que N portails peuvent tirer un lien vers le même.

(pour tirer un lien, il faut une "clé" du portail d'en face, on peut en droper jusqu'à 4 par portails en 4 heure de base, des mods sur le portail permettent d'augmenter le nombre maximal si y'a besoin)

Sans fixer une definition exacte, il est difficile de prouver qu'il est polynomial ou NP-difficile.

Comme le dit Kevin, il faudrait une description un peu plus formelle pour commencer a réfléchir sur la complexité du problème : utiliser un vocabulaire plus standard, définir l'objectif d'optimisation en ces termes, et lister les contraintes (règles) précises.

Je crois comprendre sur la page indiquée que l'adversaire peut annuler un triangle en retirant un seul sommet. Dans ce cas, un objectif n'est-il pas de minimiser le nombre d’arêtes par sommet ? nombre moyen ou nombre maximal ?
Si oui, le problème est multi-objectif : on a deux objectifs contradictoires (maximiser le nombre de triangles mais minimiser le nombre d'arêtes). C'est un champ de recherche encore jeune en optimisation combinatoire, et tous les problèmes pratiques de ce type sont NP-difficiles. Un algorithme optimal pour des graphes de taille 100 (taille évoquée par vince) prendrait des heures ou des jours, sinon des mois. Cependant, il peut y avoir des heuristiques qui donneraient des solutions très satisfaisantes.

La règle la plus simple quand tu prévois c'est de commencer par faire les triangles les plus grands possibles. C'est pas toujours le plus rentable, surtout en clefs, mais ça passe. Je sais qu'il y a un quartier en ville où je peux tirer une trentaine de fields simplement avec une base à 4 portails, mais il me faut une bonne quantité de clefs...

Après, personellement, j'utilise ingraph: http://atistar.net/~stepp/ingraph/

(Et balance ton pseudonyme en jeu )

Hors Sujet: ça fout quoi dans le sous forum TI ?x)

Un résumé des règles pour les matheux:

* Deux liens ne peuvent pas se croiser.
* Les liens ont une direction et un sens (en somme, ce sont des vecteurs, appelons les donc vecteurs)
* Un point ne peut pas être l'origine d'un vecteur si ledit point est dans un field.
* Le nombre de vecteurs maximum originant d'un point est de 8.
* On peut faire entrer un nombre infini de vecteurs sur un point.
* Trois points reliés entre eux en triangle forment un "field".

Je crois que je n'ai rien oublié.

On peut ignorer l'aspect farming de clef @vince, suffit de hacker le matin sur le chemin tous les jours :P Ou de taxer des clefs aux autres joueurs.

Warpten (./23) :
Hors Sujet: ça fout quoi dans le sous forum TI ?x)

C'est historique, la section Algo était dans le sous forum TI à la base, et la multi parentalité n'étant pas encore supportée...


Je ne connaissais pas ingraph, ça a l'air sympa

Omagad y'en a qui se sont vraiment posé la question

Tu nous diras si ca aide vince?

La source est en haskell ... x.x

squalyl (./25) :
Omagad y'en a qui se sont vraiment posé la question

Tu nous diras si ca aide vince?

Je regarderai ouais

Warpten : La variété des fonctions objectif proposées semble confirmer que le problème n'a pas de description définitive qui satisferait tout le monde.
Est-ce que, au moins pour certains objectifs, tu as une idée de la performance de cette heuristique (écart entre les solutions qu'elle donne et l'optimum) ?

Warpten (./26) :
La source est en haskell ... x.x

Et c'est probablement très adapté à la résolution de ce genre de problèmes.

./29 Mais je suis incapable de la lire

./28 Il y a différentes approches pour différentes situations, mais en général l'heuristique du "Save Flynn Event" est (curieusement, étant donné que la solution qui maximise le gain en AP est la plus recherchée) la plus proche du résultat réel.

En revanche sur un grand nombre de noeuds le programme crash simplement (typiquement, sur une 50 aine, j'ai eu un joli message d'erreur windows ^^)

à noter qu'il y a de toute façon plus d'une solution optimum pour ce type de problèmes.

C'est un problème intéressant mais je n'ai (malheureusement, étant joueur ) pas le bagage mathématique pour m'y attaquer moi-même.