Pour la classe, nous avons une grille et un tas de carrés sur la grille que nous devons détecter et parcourir. Nous commençons à (0,0). Nous scannons de minuscules régions de la grille à la fois (pour des raisons concernant notre structure de données, c'est obligatoire), et quand nous détectons des carrés que nous devons parcourir, puis nous voyageons. Il y a 32 emplacements sur la grille, mais nous avons seulement besoin de voyager 16 fois, et aussi vite que possible (nous courrons avec quelqu'un d'autre).Battre un algo avide
L'algo de Dijkstra trouverait le chemin le plus court de notre emplacement actuel à notre prochain emplacement. Ceci est sous-optimal cependant, parce que notre prochain emplacement peut être vraiment loin de l'emplacement après cela. Il serait plus utile de pouvoir déterminer la densité des emplacements lorsque nous numérisons, puis de choisir d'aller dans un endroit très dense et de parcourir tous les endroits dans cette zone.
Existe-t-il un algorithme mieux adapté à une situation comme celle-ci? Je sais que l'heuristique gloutonne n'est pas optimale. A * et Dijkstra sont ceux auxquels nous avons pensé au début, mais nous espérons qu'il y aura une solution complètement différente.
PS cela se fait dans l'assemblage, malheureusement.
Avez-vous un contre-exemple exact pour expliquer pourquoi l'approche de Dijkstra n'est pas optimale? Je n'arrive pas à trouver quelque chose. – IVlad
Est-ce que tous les emplacements que vous devez parcourir pour vous connecter les uns aux autres? La distance d'un endroit à l'autre est-elle égale à la distance euclidienne, sqrt (dx^2 + dy^2)? Ou y a-t-il des routes (arêtes) et des distances (poids) spécifiées entre les emplacements? – LarsH
Assemblée? Pauvre toi. :( – st0le