homotopy_shortest_paths — DRIVE `braidpath` op

• Datenarten: image2d × any × any → table

• Aufruf: import fullseye as fs; fs.ledger.homotopy_shortest_paths(grid, start, goal, k=4, obstacles=None, angle=0.1, max_states=400000, max_cost=None) (die Implementierung direkt: import braidpath; braidpath.homotopy_shortest_paths(grid, start, goal, k=4, obstacles=None, angle=0.1, max_states=400000, max_cost=None); aus dem Register: opsdrive.get("homotopy_shortest_paths"))

• GPU: nein (nur CPU-Referenzimplementierung)

Verwendung

Auf einem Gitter (True = befahrbar, 4er-Nachbarschaft) die k kürzesten Pfade von start nach goal in verschiedenen Homotopieklassen, kürzeste zuerst.

Zustand = (Zelle, Dynnikov-Koordinaten des Zopfes). Hindernispunkte gelten als unbewegliche Stränge; bei jedem Zug wird der Kreuzungsbuchstabe angehängt und die Koordinaten werden aktualisiert (die Koordinaten sind eine vollständige Invariante der Klasse, daher wird jedes (Zelle, Koordinaten) nur einmal expandiert). Dijkstra expandiert dieses „nach Klassen geliftete“ Gitter in Kostenreihenfolge, daher ist die Reihenfolge, in der goal mit neuen Koordinaten erreicht wird, die aufsteigende Reihenfolge der kürzesten Pfade je Klasse.

Parameters

obstacles : repräsentative Punkte der Löcher (M, 2). Ohne Angabe grid_hole_points (ein Punkt je blockierter Komponente, die den Rand nicht berührt).

max_states / max_cost : Obergrenzen für die Zahl expandierter Zustände und für die Kosten (es gibt unendlich viele Klassen —— ein Loch lässt sich beliebig oft umrunden).

Returns: dict paths (je Klasse eine (L, 2)-Folge von (row, col), kürzeste zuerst), costs, words (Zopfwörter einschließlich der Hindernisse), keys, obstacles, states (Zahl der expandierten Zustände), complete (ob alle k Pfade gefunden wurden).

Referenzen (Beispieldaten, Literatur)

• Katalog der Beispieldaten (Download-URLs / Lizenzen) — 2-D nutzt skimage.data (BSD/Public Domain) plus synthetische Bilder, 3-D nennt Download-URLs echter Datenquellen (Stanford, PDS, …).

• Herkunft und Literatur der Operatoren — die Quellen der Forschung/Verfahren, auf denen diese Operatorfamilie beruht.

• Der kanonische Algorithmus (Autor, Jahr) und seine Anwendungen stehen im Familienleitfaden oben.

Ausführbare Beispiele (verifizierte Samples, die diesen Operator wirklich aufrufen)

• poc_braid_homotopy_classes — py -3.11 examples/poc_braid_homotopy_classes.py

Typkompatible Folge-Operatoren (nehmen `table` als Eingabe)

course_layout · course_occupancy · course_contains · world_build · world_camera · world_move · lidar_scan · rss_longitudinal_same

Gleiche Kategorie (`braidpath`)

braid_from_trajectories · braid_reduce · braid_artin_images · dynnikov_coordinates · dynnikov_act · braid_equivalent · homotopy_class_compare · pairwise_winding

*Provenance: braidpath.py — DRIVE Operator-Registry. Diese Notiz wird von tools/opdocs.py md erzeugt (nicht von Hand bearbeiten).*

homotopy_shortest_paths — DRIVE braidpath op