Heuristik mit der geringsten Anzahl von Umdrehungen

Question

Kann man irgendwie sicherstellen, dass die Heuristik der geringsten Anzahl von Umdrehungen durch irgendetwas anderes als durch eine Suche in der Breite zuerst erfüllt wird? Vielleicht wäre eine weitere Erklärung hilfreich.

Ich habe ein Zufallsdiagramm, das dem hier ähnelt:

0 1 1 1 2
3 4 5 6 7
9 a 5 b c
9 d e f f
9 9 g h i

Ausgehend von der linken oberen Ecke muss ich wissen, wie viele Schritte ich am wenigsten brauche, um zur rechten unteren Ecke zu gelangen. In diesem Zufallsdiagramm werden beispielsweise die drei 1en in der obersten Reihe als ein einziger Knoten betrachtet, und jeder benachbarte (nicht diagonale) verbundene Knoten ist ein möglicher nächster Zustand. Die möglichen nächsten Zustände sind also von Anfang an die 1 in der obersten Reihe oder die 3 in der zweiten Reihe.

Derzeit verwende ich eine bidirektionale Suche, aber die Explosivität der Baumgröße nimmt ziemlich schnell zu. Ich habe es beim besten Willen nicht geschafft, das Problem so anzupassen, dass ich den Knoten sicher Gewichte zuweisen kann und sie die geringste Anzahl von Zustandsänderungen gewährleisten, um das Ziel zu erreichen, ohne dass es zu einer Breitensuche wird. Wenn man sich das Problem wie einen Stadtplan vorstellt, wäre die Heuristik die geringste Anzahl von Abbiegungen, um das Ziel zu erreichen.

Es ist sehr wichtig, dass die geringste Anzahl von Umdrehungen das Ergebnis dieser Suche ist, da dieser Wert Teil der Heuristik für ein komplexeres Problem ist.

Answer 1

Sie haben selbst gesagt, dass jede Zahlengruppe einen Knoten darstellt und dass jeder Knoten mit benachbarten Knoten verbunden ist. Dann ist dies eine einfache kürzester Weg Problem, und Sie könnten (zum Beispiel) Folgendes verwenden Dijkstra-Algorithmus , wobei jede Kante das Gewicht 1 hat (für 1 Runde).

Answer 2

Das klingt wie Dijkstras Algorithmus. Der schwierigste Teil wäre es, den Graphen richtig einzurichten (zu verfolgen, welcher Knoten welche Kinder bekommt), aber wenn Sie einige CPU-Zyklen dafür aufwenden können, wäre es danach in Ordnung.

Warum wollen Sie keine Breitensuche?

Hier.. Mir war langweilig :-) Das ist in Ruby, aber vielleicht hilft es Ihnen auf die Sprünge. Wohlgemerkt, es ist nicht getestet.

class Node
  attr_accessor :parents, :children, :value
  def initialize args={}
    s = args[:parents] || []
    @children = args[:children] || []
    @value = args[:value]
  end

  def add_parents *args
    args.flatten.each do |node|
      s << node
      node.add_children self unless node.children.include? self
    end
  end

  def add_children *args
    args.flatten.each do |node|
      @children << node
      node.add_parents self unless node.parents.include? self
    end
  end
end

class Graph
  attr_accessor :graph, :root
  def initialize args={}
    @graph = args[:graph]
    @root = Node.new
    prepare_graph
    @root = @graph[0][0]
  end

  private

  def prepare_graph
# We will iterate through the graph, and only check the values above and to the
# left of the current cell.

    @graph.each_with_index do |row, i|
      row.each_with_index do |cell, j|
        cell = Node.new :value => cell #in-place modification!
        # Check above
        unless i.zero?
          above = @graph[i-1][j]
          if above.value == cell.value
            # Here it is safe to do this: the new node has no children, no parents.
            cell = above
          else
            cell.add_parents above
            above.add_children cell # Redundant given the code for both of those
            # methods, but implementations may differ.
          end
        end
        # Check to the left!
        unless j.zero?
          left = @graph[i][j-1]
          if left.value == cell.value
            # Well, potentially it's the same as the one above the current cell,
            # so we can't just set one equal to the other: have to merge them.
            left.add_parents cell.parents
            left.add_children cell.children
            cell = left
          else
            cell.add_parents left
            left.add_children cell
          end
        end
      end
    end
  end
end
     #j = 0, 1, 2, 3, 4
graph = [
         [3, 4, 4, 4, 2], # i = 0
         [8, 3, 1, 0, 8], # i = 1
         [9, 0, 1, 2, 4], # i = 2
         [9, 8, 0, 3, 3], # i = 3
         [9, 9, 7, 2, 5]] # i = 4

maze = Graph.new :graph => graph

# Now, going from maze.root on, we have a weighted graph, should it matter.
# If it doesn't matter, you can just count the number of steps.
# Dijkstra's algorithm is really simple to find in the wild.

Answer 3

Das sieht nach demselben Problem aus wie bei diesem Projektleiter http://projecteuler.net/index.php?section=problems&id=81

Die Komplexität der Lösung ist O(n) n-> Anzahl der Knotenpunkte

Was Sie brauchen, ist die Memoisierung.

Bei jedem Schritt können Sie aus maximal 2 Richtungen kommen. Wählen Sie also die Lösung, die billiger ist.

Es ist etwas wie (fügen Sie einfach den Code, der 0, wenn an der Grenze nimmt)

for i in row:
    for j in column:
         matrix[i][j]=min([matrix[i-1][j],matrix[i][j-1]])+matrix[i][j]

Und jetzt haben Sie die billigste Lösung, wenn Sie sich nur nach links oder unten bewegen

Die Lösung befindet sich in Matrix[MAX_i][MAX_j]

Wenn man auch nach links und oben gehen kann, dann ist der BigO viel höher (ich kann eine optimale Lösung finden)

Answer 4

Damit A* immer den kürzesten Weg findet, muss Ihre Heuristik die tatsächlichen Kosten immer unterschätzen (die Heuristik ist "zulassungsfähig"). Einfache Heuristiken wie die Verwendung des euklidischen oder des Manhattan-Abstands auf einem Gitter funktionieren gut, weil sie schnell zu berechnen sind und garantiert kleiner oder gleich den tatsächlichen Kosten sind.

Leider kann man in Ihrem Fall nicht viel tun, es sei denn, Sie können einige vereinfachende Annahmen über die Größe/Form der Knoten treffen. Betrachten Sie zum Beispiel den Weg von A nach B in diesem Fall:

B 1 2 3 A
C 4 5 6 D
C 7 8 9 C
C e f g C
C C C C C

Der kürzeste Weg wäre A -> D -> C -> B, aber die Verwendung räumlicher Informationen würde wahrscheinlich dazu führen, dass die heuristischen Kosten für 3 niedriger sind als für D.

Je nach den Umständen können Sie vielleicht mit einer Lösung leben, die nicht der kürzeste Weg ist, solange Sie die Antwort schneller erhalten können. Hier gibt es einen schönen Blogpost von Christer Ericson (Programmierer von God of War 3 für PS3) zu diesem Thema: http://realtimecollisiondetection.net/blog/?p=56

Hier ist meine Idee für eine unübersehbare Heuristik: Bewegen Sie sich vom Punkt aus horizontal, bis Sie auf gleicher Höhe mit dem Ziel sind, bewegen Sie sich dann vertikal, bis Sie es erreichen, und zählen Sie die Anzahl der Zustandsänderungen, die Sie vorgenommen haben. Sie können auch andere Testpfade berechnen (z. B. erst vertikal, dann horizontal) und den Mindestwert als endgültige Heuristik wählen. Wenn Ihre Knoten ungefähr gleich groß und regelmäßig geformt sind (anders als in meinem Beispiel), könnte dies recht gut funktionieren. Je mehr Testpfade man durchführt, desto genauer, aber auch langsamer wird es.

Ich hoffe, das war hilfreich. Lassen Sie mich wissen, wenn etwas davon keinen Sinn ergibt.

Answer 5

Diese ungetunte C-Implementierung der Breadth-First-Suche kann ein 100-mal-100-Gitter in weniger als 1 ms durchkauen. Sie können das wahrscheinlich besser.

int shortest_path(int *grid, int w, int h) {
    int mark[w * h];  // for each square in the grid:
                      // 0 if not visited
                      // 1 if not visited and slated to be visited "now"
                      // 2 if already visited
    int todo1[4 * w * h];  // buffers for two queues, a "now" queue
    int todo2[4 * w * h];  // and a "later" queue
    int *readp;            // read position in the "now" queue
    int *writep[2] = {todo1 + 1, 0};
    int x, y, same;

    todo1[0] = 0;
    memset(mark, 0, sizeof(mark));

    for (int d = 0; ; d++) {
        readp = (d & 1) ? todo2 : todo1;      // start of "now" queue
        writep[1] = writep[0];                // end of "now" queue
        writep[0] = (d & 1) ? todo1 : todo2;  // "later" queue (empty)

        // Now consume the "now" queue, filling both the "now" queue
        // and the "later" queue as we go. Points in the "now" queue
        // have distance d from the starting square. Points in the
        // "later" queue have distance d+1.
        while (readp < writep[1]) {
            int p = *readp++;
            if (mark[p] < 2) {
                mark[p] = 2;
                x = p % w;
                y = p / w;
                if (x > 0 && !mark[p-1]) {                // go left
                    mark[p-1] = same = (grid[p-1] == grid[p]);
                    *writep[same]++ = p-1;
                }
                if (x + 1 < w && !mark[p+1]) {            // go right
                    mark[p+1] = same = (grid[p+1] == grid[p]);
                    if (y == h - 1 && x == w - 2)
                        return d + !same;
                    *writep[same]++ = p+1;
                }
                if (y > 0 && !mark[p-w]) {                // go up
                    mark[p-w] = same = (grid[p-w] == grid[p]);
                    *writep[same]++ = p-w;
                }
                if (y + 1 < h && !mark[p+w]) {            // go down
                    mark[p+w] = same = (grid[p+w] == grid[p]);
                    if (y == h - 2 && x == w - 1)
                        return d + !same;
                    *writep[same]++ = p+w;
                }
            }
        }
    }
}