Angenommen, ich habe ein Labyrinth mit einem Start- und einem Endpunkt, die jeweils mit Orange und Rot markiert sind, und mein Ziel ist es, den Mindestabstand zwischen ihnen zu finden. Der blockierte Pfad wird durch schwarze Farbe und der offene Pfad durch weiße Farbe dargestellt. Es werden jedoch zwei Änderungen daran vorgenommen.

Es gibt einige zu besuchende Zellen, die grau markiert sind.Jede Zelle kann beliebig oft besucht werden (auch Start, Ziel und Besuchspunkte)

zB B = Schwarz, W = Weiß, G = Grau, R = Rot, O = Orange

         BBBBBB                 BBBBB
         BBGBBB                 BWGGB
MAZE1 => BOWGRB     MAZE2  =>   BOBBB
         BBGBBB                 BWWRB
         BBBBBB                 BBBBB

Hier wird in diesem Fall ans sein

MAZE1 => M[2][1] => [2][2] => [1][2] => [2][2] => [3][2] => [2][2] => [2][3] => [2][4]  = 7
MAZE2 => M[1][1] => [1][2] => [2][2] => [3][2] => [3][3] => [3][2] => [2][2]            = 6

Wie Sie sehen, werden die Knoten mehrmals angezeigt

Zuerst dachte ich an die Verwendung von Rekursionstechnik (Backtracking), konnte aber nicht zu einem Algorithmus kommen. und

Also habe ich mir überlegt, wie ich das machen soll.

Ich werde alle Koordinaten der Pflichtbesuchspunkte, Start- und Endpunkte verfolgenFinden Sie den Abstand zwischen jedem Knoten (wie bei der Auswahlsortierung vergleichen wir jeden Begriff, so erhalten wir den Mindestabstand zwischen jedem Knoten (mit BFS))Wenden Sie dann einen Mindestabstandsalgorithmus an. Ich dachte an TSP, aber es heißt, dass Knoten genau einmal besucht werden müssen. Hier kann es mehrere Male sein. Ich habe ein chinesisches Briefträgerproblem gefunden, weiß aber nicht, ob es hier angewendet werden kann. Der Floyd Warshall-Algorithmus ist vorhanden, enthält jedoch nicht jeden Punkt

Wie soll ich vorgehen, irgendeine Idee?