Breitensuche oder doch lieber ein anderer Algo

[dizzy]

Zitat von Flogo:

Ich will von einem "nil-Element" auf das nächste "nicht-nil-Element" kommen

Schlingel. Hätt's ja mal sagen können

Zitat von Flogo:

Ich werde also die Breitensuche nehmen.

Da bleibt dann wirklich nichts anderes mehr. Es sei denn, du musst nur ein Mal von einem nil-Feld ein nicht-nil-Feld finden, und alle weiteren gehen von da aus. Die ließen sich o.g. Verfahren wieder einsetzen.

Zitat von Flogo:

PS: wie kann man den A* dazu benutzen die Entfernungen zu allen Punkten festzustellen? Ich dachte damit findet man (fast) immer den schnellsten Weg?

Mit A* traversiert man einen Graphen dessen Kanten gewichtet sind. So einen Graphen würdest du mit der Speicherung aller Entfernungen + Koordinaten quasi erstellen, und die Entfernungen sind dann die Kantenwichtungen. Allerdings hatte ich einen kleinen Denkfehler drin: Um nur zum nächsten zu kommen ist A* viel zu viel - da reicht ja nen einfacher Vergleich. Allerdings könntest du mit A* auf kürzestem Wege zwischen nicht-nil-Feldern hüpfen. Aber auch hier ein Denk-"Lag" bei mir: Du kommst ja eh an sich von jedem Feld auf jedes andere... Also vergiss das mit A* . Dein Graph wäre komplett genug um ohne Suchalgo auszukommen...
Und: A* an sich findet immer den schnellsten/kürzesten (das muss nicht das selbe sein!) Weg. Der Knackpunkt dabei sind die Bewertungsroutinen, die die Kanten- und Knotenbewertungen machen. Das sind idR nur Schätzwerte, und je schlechter geschätzt, desto schlechter kann A* damit arbeiten.
Aber das ist ja eh hinfällig .

Mir kommt da grad noch eine (doofe) Idee. Mal sehen wie praktikabel das wird :
Stell dir jedes nicht-nil-Feld als schwarzen Pixel vor, und alle anderen als weisse Pixel. Nun lässt du die schwarzen Pixel "ausbluten", so wie mit einem Unschärfefilter. Ergebnis wäre also eine "Bitmap" (ein weiteres 2D-Array mit Zahlenwerten reicht ja), die einem "Gebirge" ähnelt: weiss=hoch; schwarz=tief. Nun, wenn du eine Koordinate hast, suchst du in Richtung des dunkelsten Nachbarwertes weiter. Damit "fällst" du quasi automatisch in die richtige Richtung, und landest zwangsläufig auf dem nächsten gültigen Feld, da das durch keine dunkleren Werte umgeben sein wird.
Allerdings wäre diese "Höhenkarte" auch immer wieder neu zu erstellen, wenn sich an der Struktur der Ausgangsdaten etwas ändert.

Aber die Idee ist doch innovativ, gell!? Vllt. lässt sich da ja echt was draus bauen - war grad ein Spontaneinfall der nicht bis in alle Details durchdacht ist. Ich bin ja fast drauf und dran das mal auszuprobieren... morgen .

Gruss, und danke für eine interessante Frage ,
Fabian

\\edit: kleinen Logikfehler ermordet... --- edit2: einen ähnlichen Kameraden entfernt...