Le trajet le plus rentable

Date 28 mars 2016 Catégories Algorithmique / Developpement par VulgaireDev

C'est un défi que j'ai trouvé sur www.codingame.com.

On dispose d'un robot et d'un bâtiment possédant plusieurs salles. Chacune possède un numéro, une somme d'argent, et deux portes menant chacune soit vers une autre salle, soit vers la sortie. On ne peut passer les portes que dans un seul sens, et la structure du batiment fait qu'il est impossible au robot de passer deux fois par la même salle (absence de cycle). Quel est la somme maximale d'argent que peut récolter le robot ?

On peut modéliser cette suite de salles par un graphe orienté acyclique.

Modélisation du problème (E pour Exit), sans avoir noté les sommes d'argent

 

On peut tenter une première approche qui fait un parcours en profondeur (DFS), et qui trouve le chemin maximisant l'argent ramassé, mais pour le passage à l'échelle on risque d'avoir des problèmes de performances.

On voit aussi qu'on a un DAG, donc on pourrait le trier par ordre topologique, puis prendre les sommets dans l'ordre, et mettre à jour la longueur max de chaque sommet en prenant le max des liens arrivant vers ce sommet + la valeur du noeud courant. En écrivant ces lignes, je me dis que ce serait une approche intéressante à tester, peut-être plus concise que la mienne.

J'ai eu une approche un peu différente, j'ai plutôt pensé programmation dynamique. En fait j'ai trouvé que ce problème ressemblait beaucoup à la pyramide de nombre (voire premier exemple sur le lien Wikipédia).

L'idée est donc de retourner notre graphe orienté, et de résoudre le problème de manière "bottom-up", avec l'idée suivante : "le score d'un noeud correspond au max des ses fils (dans le graph non retourné) + son score". Ainsi, en partant de tous les "E" sur le schéma, on propage l'information vers le haut (grâce à un BFS par exemple), et on arrive finalement avec le score maximal pour le noeud 0.

NB : Dans l'algo qui suit, on laisse la possibilité de repasser par des points où on est déjà passé. En effet dans le cas contraire, si on regardait le noeud 1, l'algo risquerait de mettre à jour sa valeur en prenant celle du E et celle du 6, mais cette dernière n'est pas encore définitive, puisque l'algo ne serait peut-être pas passé par le 6 ! On laisse donc la possibilité de mettre à jour les valeurs des noeuds.

Voici le code :

import sys
import math
from copy import deepcopy

n = int(input())
rooms = []
adja = {}
reverse_adja = {}
money_room = {'E':0}

for i in range(n):
    room = [i for i in input().split()]
        
    rooms.append(room)
    
    #we keep the money corresponding to a room
    money_room[room[0]] = int(room[1])
    
    #we build the adja list and reverse_adja
    adja[room[0]] = [room[2], room[3]]
    
    if room[2] in reverse_adja:
        reverse_adja[room[2]].add(room[0])
    else:
        reverse_adja[room[2]] = {room[0]}
    if room[3] in reverse_adja:
        reverse_adja[room[3]].add(room[0])
    else:
        reverse_adja[room[3]] = {room[0]}


#we try with a bfs-dp
next_nodes = ['E']
score_max_nodes = deepcopy(money_room)

while(len(next_nodes) != 0):
    current_node = next_nodes.pop(0)
    if current_node != '0':
        try:
            for node in reverse_adja[current_node]:
                #we append the ascending nodes, 
                if not ( node in next_nodes) :
                    next_nodes.append(node)
        except KeyError:
            pass
        
    if current_node != 'E':
        score_max_nodes[current_node] = max([score_max_nodes[i]+money_room[current_node] for i in adja[current_node]])

print(score_max_nodes['0'])

La propriété sur laquelle est basée l'algo correpond à la dernière ligne avant le print().

Commentaires

blog comments powered by Disqus