Modélisation d'un graphique en Python
j'essaie de résoudre un problème lié aux graphes en Python. Puisque c'est un problème de programmation comeptitive, Je n'utilise pas d'autres paquets de tierce partie.
Le problème présente un graphique sous la forme d'un 5 X 5 carré de la grille.
Un CET est supposé être à une position fournie par l'utilisateur sur le réseau. La grille est indexée (0,0) en haut à gauche et (4,4) en bas à droite. Chaque cellule de la grille est représentée par aucun de ces 3 personnages. ‘b’ (valeur ascii 98) indique la position actuelle du bot‘'d’ (ascii valeur 100) indique une cellule sale et ‘-‘ (valeur ascii 45) indique une propre cellule de la grille.
Par exemple, ci-dessous une grille d'échantillon où le bot est 0 0:
b---d
-d--d
--dd-
--d--
----d
Le but est de nettoyer toutes les cellules dans la grille, en nombre minimum d'étapes. Une étape est définie comme une tâche, où i) le bot change sa position ii) Le bot change l'état de la cellule (de d en -)
supposons qu'au départ le la position marquée comme b n'a pas besoin d'être nettoyé. Le bot est autorisé à se déplacer vers le haut, le bas, la gauche et la droite.
Mon approche
j'ai lu quelques tutoriels sur les graphiques,et j'ai décidé de modéliser le graphique comme une matrice de contiguïté de 25 X 25 avec 0 représentant aucun chemin, et 1 représentant des chemins dans la matrice (puisque nous pouvons nous déplacer seulement dans 4 directions). Ensuite, J'ai décidé de lui appliquer l'algorithme all pairs shortest path de Floyd Warshell, et ensuite résumer les valeurs de chemin. Mais j'ai le sentiment que ça ne marchera pas. Je suis dans une delimma que le problème est soit l'une des opérations suivantes:
i) Un Arbre de couverture Minimal (ce que je ne peux pas faire, car je ne suis pas capable de modéliser et de stocker la grille sous forme de graphique).
ii) une recherche de* (Encore une fois une supposition, mais le même problème ici, Je ne suis pas capable de modéliser la grille comme un graphe correctement).
je serais reconnaissant si vous pouviez proposer une bonne approche des problèmes comme ceux-ci. Aussi, un indice et psuedocode sur diverses formes de problèmes basés sur des graphes (ou des liens vers ceux-ci) serait utile. Merci
4 réponses
1. Comment représenter ce problème sous forme de graphique en Python?
comme le robot se déplace autour, il va se déplacer d'un carré sale à l'autre, parfois en passant par certains espaces propres le long du chemin. Votre travail est de trouver l'ordre dans lequel visiter les places sales.
# Code is untested and may contain typos. :-)
# A list of the (x, y) coordinates of all of the dirty squares.
dirty_squares = [(0, 4), (1, 1), etc.]
n = len(dirty_squares)
# Everywhere after here, refer to dirty squares by their index
# into dirty_squares.
def compute_distance(i, j):
return (abs(dirty_squares[i][0] - dirty_squares[j][0])
+ abs(dirty_squares[i][1] - dirty_squares[j][1]))
# distances[i][j] is the cost to move from dirty square i to
# dirty square j.
distances = []
for i in range(n):
distances.append([compute_distance(i, j) for j in range(n)])
# The x, y coordinates of where the robot starts.
start_node = (0, 0)
# first_move_distances[i] is the cost to move from the robot's
# start location to dirty square i.
first_move_distances = [
abs(start_node[0] - dirty_squares[i][0])
+ abs(start_node[1] - dirty_squares[i][1]))
for i in range(n)]
# order is a list of the dirty squares.
def cost(order):
if not order:
return 0 # Cleaning 0 dirty squares is free.
return (first_move_distances[order[0]]
+ sum(distances[order[i]][order[i+1]]
for i in range(len(order)-1)))
votre but est de trouver un moyen de réordonner la liste (range (n)) qui minimise les coût.
2. Comment puis-je trouver le nombre minimum de coups pour résoudre ce problème?
- le graphique est une grille.
- il y a au plus 24 carrés sales.
l'idée est de commencer à énumérer toutes les solutions possibles en utilisant une recherche en profondeur, comme suit:
# Each list represents a sequence of dirty nodes.
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 2]
[2]
[2, 1]
[2, 1, 3]
chaque fois que vous êtes sur le point de revenir dans une branche, vérifiez pour voir si cette branche est plus cher que la solution la moins chère. Si c'est le cas, vous pouvez sauter toute la branche.
si ce n'est pas assez efficace, ajouter une fonction pour calculer une limite inférieure sur le coût restant. Alors si cost ([2]) + lower_bound (set ([1, 3])) est plus cher que la solution la moins chère trouvée jusqu'à présent, vous pouvez sauter toute la branche. Plus le lower_bound () est serré, plus vous pouvez sauter de branches.
disons V={v|v=b or v=d}, et d'en obtenir un graphe connexe G(V,E). Vous pouvez calculer le coût de chaque bord dans E avec une complexité temporelle de O(n^2). Ensuite, le problème est exactement le même que: commencez par un vertex spécifié, et trouvez un chemin le plus court de G qui couvre V.
nous appelons cela Problème du voyageur de commerce(TSP) depuis 1832.
Le problème peut certainement être stockées sous forme de graphique. Le coût entre les noeuds (cellules Sales) est leur Manhattan distance. Ignorer le coût du nettoyage des cellules, parce que le coût total sera le même quelle que soit la voie empruntée.
Ce problème me semble que l' Minimum Rectiligne Steiner Tree problème. Malheureusement, le problème est NP dur, donc vous aurez besoin de venir avec une approximation (un arbre de enjambement Minimum basé sur la distance de Manhattan), si je suis correct.