L'algoritmo di Dijkstra può superare una stella, in termini di vertici controllati?

Question

So che l'algoritmo di Dijkstra può essere visto come un caso specifico di una stella, quando l'euristica della stima usata semplicemente ritorna 0, quindi so che una stella con questa specifica euristica non può controllare più vertici dell'algoritmo di Dijkstra. Quello che sto chiedendo comunque è il seguente. Dato un algoritmo a stella con un po 'di euristica che non è l'euristica che ritorna 0, potrebbe eventualmente controllare più vertici dell'algoritmo di Dijkstra?

La mia intuizione è sì e mostrerò perché. Considera la figura sotto, in cui consideriamo una grande quantità di punti discreti in questo piano, che rappresentano i vertici del grafico e collegando gli archi con il costo 1 tra tutti i punti adiacenti, creando un grafico a griglia. Supponiamo che l'euristica usata da una stella sia la distanza euclidea e supponga che molte pareti curve come quelle che ho disegnato nel mezzo esistono in questo modo, non solo i tre che ho disegnato. Una stella in questa situazione sarebbe "ingannata" per andare tra le pareti, poiché l'euristica la guiderebbe vicino al punto, solo per scoprire che è un vicolo cieco (o un ottimo locale di qualche tipo se vuoi), e Ciò accadrebbe quante volte ci sono muri. Dijkstra non sarebbe ingannato in questo modo. L'unico problema con il mio esempio qui è che Dijkstra probabilmente lo farà non Superformare una stella qui. Quindi, la mia intuizione è sbagliata o fare istanze più intelligenti di quanto esista in cui Dijkstra può effettivamente superare una stella in termini di vertici controllati?