Mes test intermédiaires me montrent qeu la solution se trouve lorsque le nombre d'éléments de chaque côté d'un cable est près de la motié du nombre total de noeuds. Je vais voir si je ne peux pas propager ce minimum dans les retours d'appel en commençant avec un minimum de N
edit: J'ai réussi à le faire, mais je ne sais pas si c'est plus efficace: - class Node: def __init__(self): self.arrows = [] def add(self, node): arrow = Arrow(self, node) self.arrows.append(arrow) node.arrows.append(arrow) # class Arrow: def __init__(self, left, right): self.left = left self.right = right self.flow = 0 # def travel(node, minimum): total = 0 for arrow in node.arrows: if arrow.flow == 0: arrow.flow = -1 son = arrow.right if son == node: son = arrow.left minimum, access = travel(son, minimum) maxSon = N - access if maxSon < access: maxSon= access if maxSon < minimum: minimum = maxSon total += access return minimum, total + 1 # N = int(input()) nodes = [Node() for i in range(N)] for _ in range(N-1): p, s = map(int, input().split()) nodes[p].add(nodes[s]) if N <= 1: nodes[0].add(nodes[0]) minFlow, access = travel(nodes[0], N) print(N - minFlow)
- Edité par PierrotLeFou 12 mai 2022 à 2:18:34
Le Tout est souvent plus grand que la somme de ses parties.
Alors, c'est peine perdue ... Je pense que ma dernière solution est la plus rapide. Avec des classes, c'est comme des pointeurs, et c'est en général très rapide. Une fois le réseau généré, je pourrais faire sautter la liste nodes et pouvoir me promener tout de même dans le réseau si j'ai gardé un noeud.
head = nodes[0] del(nodes) minFlow, access = travel(head, N)
- Edité par PierrotLeFou 12 mai 2022 à 15:25:52
Le Tout est souvent plus grand que la somme de ses parties.
Je n'arrive pas à comprendre quel est le problème en fait.
En entrée, on voit N lignes de 2-tuple d'entier qui correspondent aux arcs entre 2 sommets. Mais, ces entrées sont écrites aléatoirement, exigées par IOI, ou une autre méthode ? Parce que le nombre de combinaisons de N-1 arcs dans un ensemble de N sommets peut vite devenir énorme, si on teste toutes combinaisons.
De façon triviale, et je me trompe peut-être, j'ai jugé utile de commencer par les sommets qui ont leurs degrés les plus élevés.
Je n'essaie pas de considérer toutes les combinaisons. Je construit tout simplement un graphe. Ensuite, je me "promène" dans le graphe et je ramène le nombre d'éléments passant par un cable.
J'explore tous les embranchements non déjà visités.
Il est dit dans l'énoncé qu'il n'existe qu'un chemin pour aller d'un noeud à tout autre. Je ramêne vers le point de départ le flot de l'arête la plus fragile du réseau.
- Edité par PierrotLeFou 13 mai 2022 à 3:27:19
Le Tout est souvent plus grand que la somme de ses parties.
Certes, mais tu dois bien tester pour chacun des noeuds la possibilité qu'il soit la racine; ce qui augmente considérablement le nombre de combinaisons possibles. Non?
En fait, je ne connais pas encore assez l'implémentation des classes pour bien comprendre l'idée de tes derniers programmes. Tu pourrais me la présenter vue de haut?
CristianoRolando a écrit:
Je n'arrive pas à comprendre quel est le problème en fait.
En entrée, on voit N lignes de 2-tuple d'entier qui correspondent aux arcs entre 2 sommets. Mais, ces entrées sont écrites aléatoirement, exigées par IOI, ou une autre méthode ? Parce que le nombre de combinaisons de N-1 arcs dans un ensemble de N sommets peut vite devenir énorme, si on teste toutes combinaisons.
De façon triviale, et je me trompe peut-être, j'ai jugé utile de commencer par les sommets qui ont leurs degrés les plus élevés.
Les entrées sont imposées par l'exercice. Effectivement, mon programme (que j'ai présenté plus haut) ne passe pas tous les tests de la plateforme France IOI pour cause de lenteur, certainement car ces tests portent sur des cas de réseaux aux quantités importantes d'ordinateur.
Comment sais-tu les degrés des différents sommets avant de les calculer? Les chiffres qui identifient les PC ne sont rien d'autres que des 'noms' qui n'informent pas du tout sur la hiérarchie des ordinateurs dans le réseau.
Dans mon code, il n'y a pas tout à fait la notion de racine. J'entre dans le réseau n'impoorte où.
J'ai choisi d'entrer au noeud nommé "0", mais j'aurais pu entrer ailleurs.
Le numéro (ou nom) des noeud ne me sert que lors de la construction du réseau.
Le nom ne fait pas partie de la définition de la classe Node. Ce que je propage est le flot entre les noeuds sur les arêtes. Je me rend compte que ce n'est pas évident à expliquer ... En fait la récursivité m'amène aux "extrémités" du réseau et le retour des appels me ramène les informations dont j'ai besoin. On peut voir les classes comme une façon de créer des objets et ce qqu'on manipule est comme "l'adresse" de ces objets.
Je crée deux types d'objets, des noeuds et des arêtes. C'est pour cela que je pourrais faire sauter la liste noeuds en gardant au moins un noeud, donc son adresse. Petit test: >>> L=[[1, 2, 3], [4, 5, 6]] >>> N=L[0] >>> del(L) >>> N [1, 2, 3] Ensuite, je me promène d'adresse en adresse dans mon réseau. Je passe d'un noeud à une arête, et d'une arête à un autre noeud.
Ce que je place dans l'arête est le nombre de noeuds rencontrés d'un côté et je peux calculer le nombre de l'autre côté.
Et ceci précisément parce qu'il n'y a "qu'un" chemin d'un noeud à un autre.
- Edité par PierrotLeFou 13 mai 2022 à 15:28:43
Le Tout est souvent plus grand que la somme de ses parties.
Ces N-1 lignes sont stockées dans quoi ? Et c'est quel type (str ?) ? Il y a 10 essais avec N variable à chaque essai, donc, si je comprends bien il faut parcourir les N-1 lignes et construire le graphe puis le tester, c'est ça ?
Je laisse tomber, même avec mon compte IOI, je comprends que dalle, les entrées sont purement arbitraires, c'est n'importe quoi.
Ok, il faut faire des input(). Je m'y mets. Pour les input() quand N est élevé, par exemple 10000. L'utilisateur doit vraiment taper 9999 séries d'entiers séparés par une espace ?
- Edité par CristianoRolando 13 mai 2022 à 22:07:31
Ce n'est pas l'utilisateur qui entre les 10000 ou 100000 connexions, c'est France IOI qui les fournit. C'est bien deux entiers séparés par un espace. Les valeurs vont de 0 à N-1. Si tu regardes le sujet, Zèbre et moi avons essayé toutes sortes de possibilités: + liste de listes + liste de dictionnaires + dictionnaire de dictionnaires. J'avais toujours un problème de mémoire. Je suis donc passé aux classes. Pour parler dans le jargon de C, je construit un tableau de "pointeurs" vers des structures. Les instances de classes se comportent vraiment comme des pointeurs. Des pointeurs vers des objets comparables à des structures. > construire le graphe puis le tester, c'est ça ? Tout à fait. Je construit avec la méthode add() de ma classe Node. Les deux noeuds existent déjà (construits au début) et je leur associe une arête que je construit à ce moment et je la relie aux deux noeuds. Comme je l'ai dit, je peux partir de n'importe où et parcourir tout le graphe. > les entrées sont purement arbitraires, c'est n'importe quoi. Ça n'est justement pas n'impoorte quoi. C'est un réseau faiblement connexe dans lequel il n'y a aucune boucle. Je l'ai déjà mentionné, il n'y a qu'un chemin (une arête ou plus) entre deux noeuds. Un détail est que je n'ai qu'une arête entre deux noeuds, contrairement à mon dictionnaire de dicionnaires. Il y a tout de même deux valeurs associées à chaque arête. Une valeur que j'appelle "flow" et son complément N-flow. Ceci me donne en fait le nombre de noeuds de chaque côté de cet arête.
edit:
Je viens de revoir mon code pour savoir ce que ça donnerait en C, et je constate que je ne place pas de flot dans le champs flow.
Il ne me sert que de flag pour ne pas boucler sur soi-même.
Je ramène vers les instances appelantes de la fonction les valeurs désirées.
reedit:
Si on veut vraiment optimiser la mémoire, c'est un défi même en C. Je ne dis pas que je ne le ferai pas ...
- Edité par PierrotLeFou 14 mai 2022 à 7:10:45
Le Tout est souvent plus grand que la somme de ses parties.
nombre_de_pc_en_reseau = int(input("Combien de PC sont connectés en réseau ? "))
retrait_unitaire = 1
matrice_reseau = [[None] * nombre_de_pc_en_reseau for _ in range(nombre_de_pc_en_reseau)]
for i in range(nombre_de_pc_en_reseau - retrait_unitaire):
ligne_en_liste = input().split(' ') # ['15', '85']
matrice_reseau[int(ligne_en_liste[0])][int(ligne_en_liste[1])] = True
matrice_reseau[int(ligne_en_liste[1])][int(ligne_en_liste[0])] = True
# la matrice est maintenant complète
for ligne in matrice_reseau:
print(ligne)
On dit que le nombre maximum de PC peut être 100000. On aura donc une matrice de 10 milliards de composantes. Ce qui dépasse largement la limite permise de 32 Mb C'est une matrice creuse qui contiendra des None pour plus de 99.999 % des cas.
Le Tout est souvent plus grand que la somme de ses parties.
Et c'est pire que j'ai dit: >>> from sys import getsizeof >>> l=100000 >>> m=[[0] for _ in range(l)] >>> len(m) 100000 >>> getsizeof(m) 800984 >>> s=getsizeof(m) >>> s*(l+1) 80099200984
edit: Et le temps de génération dépasse largement les 0.5 seconde comme limite de temps.
- Edité par PierrotLeFou 20 mai 2022 à 4:21:18
Le Tout est souvent plus grand que la somme de ses parties.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.