Discussion :

[Basile le disciple]

slt à tous,

je bloque depuis plusieurs jours sur un exercice. Mon algorithme marche mais met trop de temps

je dispose d'un labyrinthe sous la forme d'un graphe pondéré orienté et je dois trouver, à partir d'un sommet déterminé, le chemin le plus bénéfique(maximum de points récoltés) en visitant un nombre déterminé de chemin... un exemple :



je dois partir au sommet n°1 et amasser les points en traversant 4 chemins (je peux aussi attendre à un sommet et récolté 0 points si c plus avantageux). La solution ici serait 15 avec le chemin 1-2 2-3 3-1 1-2

voilà ce que l'on me donne en entrée :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
4 8 1 4
1 2 5
1 3 3
2 1 -2
2 3 6
2 4 3
3 1 -1
3 4 -2
4 3 1

les 4 premiers nombres sont respectivement :

nbSommets : nombre de sommets
nbArcs : nombre d'arcs
debut : sommet de départ
temps : temps à disposition

les nbArcs lignes suivantes (sous la forme s1 s2 l) décrivent le graphe (s1 relie s2 avec un poid l)

et voici mes algos (en python):

une version récursive :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
import sys
 
def main():
  nbSommets,nbArcs,debut,temps = map(int,sys.stdin.readline().split())
  INFINI = 10**8
  #INFINI = 100  #<-- à supprimer
  voisin = [ [(i,0)] for i in range(nbSommets+1)]
  for _ in range(nbArcs):
    s1,s2,poid = map(int,sys.stdin.readline().split())
    voisin[s1].append( (s2,poid) )
 
  tabDynamique = [ [INFINI for i in range(temps)] for j in range(nbSommets+1)]
 
  def MeilleurChemin(T,s):
    if T ==0:
      return 0
    if tabDynamique[s][T-1] != INFINI:
      return tabDynamique[s][T-1]
 
    maxPoint = 0
    for v,bonus in voisin[s]:
      maxPoint = max(maxPoint,bonus + MeilleurChemin(T-1,v) )
 
    tabDynamique[s][T-1] = maxPoint
    return maxPoint
 
  print(MeilleurChemin(temps,debut))
 
 
 
main()

une version itérative :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
import sys
 
def main():
  nbSommets,nbArcs,debut,temps = map(int,sys.stdin.readline().split())
  INFINI = 10**8
  #INFINI = 100  #<-- à supprimer
  voisin = [ [(i,0)] for i in range(nbSommets+1)]
  visites = [False] * (nbSommets+1)
  visites[debut] = True
  scoresMax = [ [-INFINI for _ in range(temps+1)] for i in range(nbSommets+1)]
  scoresMax[debut][0] = 0
  scoreMax = -INFINI
  for _ in range(nbArcs):
    s1,s2,poid = map(int,sys.stdin.readline().split())
    voisin[s1].append( (s2,poid) )
 
  en_cours = [debut]
 
  for t in range(1,temps+1):
    for i in range(len(en_cours)):
      s = en_cours[i]
      for v,p in voisin[s]:
        #print(v,p)
        scoresMax[v][t] = max(scoresMax[v][t],scoresMax[s][t-1] + p)
        scoreMax = max(scoreMax,scoresMax[v][t])
        if not visites[v]:
          visites[v] = True
          en_cours.append(v)
 
  sys.stdout.write(str(scoreMax))
 
main()

mon problème est donc qu'ils prennent trop de temps et je poste pr savoir si qqn n'aurait pas une idée pr améliorer... Merci d'avance

[tbc92]

* Un peu de commentaire dans le code, ça ne ferait pas de mal.
* Ton traitement est trop long ? sur le jeu de données proposé, avec les 4 sommets et les 8 arcs, ou sur des données plus conséquentes ? Quel est le temps de traitement obtenu, et le temps de traitement maxi ?
* Si tu avais un problème du type : 50 sommets, 300 arcs, et un trajet de 53 arcs par exemple, est-ce que dans ton traitement, tu décomposerais 53 en base 2 : 53=32+16+0+4+0+1
Si tu pars sur cette base, tu es sur la bonne voie. Mais sinon, effectivement, je pense que ton algorithme ne va pas être performant du tout pour des longs trajets.

[Basile le disciple]

tt d'abord merci pr la réponse

Ton traitement est trop long ? sur le jeu de données proposé, avec les 4 sommets et les 8 arcs, ou sur des données plus conséquentes ? Quel est le temps de traitement obtenu, et le temps de traitement maxi ?

sur cet exemple le temps utlisé est de 0.02s et je dispose de 10s. Le problème étant qu'il peut y avoir 1000 sommets,10 000 arcs et 500 déplacements possibles. Je ne peux pas connaitre les temps quand mes alog sont trop longs...

Si tu avais un problème du type : 50 sommets, 300 arcs, et un trajet de 53 arcs par exemple, est-ce que dans ton traitement, tu décomposerais 53 en base 2 : 53=32+16+0+4+0+1

j'avoue que j'ai du mal à suivre, je ne vois pas en quoi décomposer le nb d'arc en base 2 pourra m'aider ds mon problème

[tbc92]

Pour un nombre d'arcs maxi de 500, tu vas décomposer 500 comme indiqué : 500= 256+128+64+32+16+0+4+0+0
Tu recenses tous les chemins de longueur 1 (facile, c'est la liste de tous les arcs)
Puis tous les chemins de longueur 2
Puis tous les chemins de longueur 4
Puis tous les chemins de longueur 8
Puis tous les chemins de longueur 16
Puis tous les chemins de longueur 32
Puis tous les chemins de longueur 64
Puis tous les chemins de longueur 128
Puis tous les chemins de longueur 256, et pour ceux là, tu peux te contenter de ceux qui commencent par le point qui t'a été donné.
Et ensuite tu cherches les chemins de longueur 384 ( en croisant les 2 derniers groupes) ...etc etc.
A chaque étape, tu dois recenser tous les chemins possibles, mais tu as intérêt à lancer une autre procédure juste après. Par exemple, quand tu as les chemins de longueur 2, si tu as un chemin ABD qui rapporte 20 jetons, et un autre ACD qui rapporte 25 jetons (plus de jetons, même point de départ, et même point d'arrivée), alors inutile de garder le chemin ABD pour la suite des traitements.

Ceci dit, 10 secondes pour les volumes que tu donnes,ce n'est pas gagné !

[Basile le disciple]

je vais essayer mais j'ai bien peur que ce soit perdu d'avance avec le temps disponible. Quoi qu'il en soit merci de prendre du temps pr m'aider

[Basile le disciple]

j'ai essayé une méthode se basant sur la décomposition en base 2 mais ça a pris trop de temps (sans doute l'ai-je mal comprise)

mais j'ai enfin réussi, il fallait tout simplement partir de tous les sommets pr arriver au sommet debut et non le contraire

si ça interesse qqn voici le code :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
import sys
 
def main():
  nbSommets,nbArcs,debut,temps = map(int,sys.stdin.readline().split())
 
  predecesseur = [ [] for i in range(nbSommets+1)]
  for _ in range(nbArcs):
    s1,s2,poid = map(int,sys.stdin.readline().split())
    predecesseur[s2].append( (s1,poid) )  
 
  tabDynamique = [ [0 for t in range(temps+1)] for i in range(nbSommets+1)]
 
  for t in range(temps-1,-1,-1):
    for s in range(1,nbSommets+1):
      for p,l in predecesseur[s]:
        tabDynamique[p][t] = max(tabDynamique[p][t],tabDynamique[s][t+1] + l)
 
  print(tabDynamique[debut][0])

je mets donc résolu

[tbc92]

BRAVO !!!!

Ma solution est à peu près 100 fois plus lente

Mais je répète... des commentaires dans le code , ça sert TOUJOURS.