Najkrótsza ścieżka na niekierowanym wykresie?

Pomyślałem więc, że należy do tego (choć nieco podstawowego) pytania:

Powiedzmy, że mam wykres wielkości 100 węzłów ułożonych we wzór 10x10 (pomyśl szachownica). Wykres jest nieukierowany i nieważony. Poruszanie się po wykresie wymaga przesunięcia o trzy pola do przodu i jedno pole w prawo lub w lewo (podobnie do ruchu rycerza szachowego po planszy).

W przypadku stałego węzła początkowego, jak znaleźć najkrótszą ścieżkę do dowolnego innego węzła na planszy?

Wyobrażałem sobie, że między węzłami, które są wykonalnymi ruchami, będzie tylko krawędź. Biorąc pod uwagę te informacje, chciałbym znaleźć najkrótszą ścieżkę od węzła początkowego do węzła końcowego.

Początkowo myślałem, że każda krawędź jest ważona wagą 1. Jednak wykres nie jest przekierowany, więc Djikstras nie byłby idealnym dopasowaniem. Dlatego postanowiłem to zrobić przy użyciu zmienionej formy głębokiego pierwszego wyszukiwania.

Jednak nie potrafiłem sobie wyobrazić, jak uzyskać najkrótszą ścieżkę za pomocą wyszukiwania.

Inną rzeczą, którą próbowałem, było umieszczenie wykresu w postaci drzewa z węzłem początkowym jako korzeniem, a następnie wybranie najwcześniejszego (najniższego numeru wiersza) wyniku, który dał mi pożądany węzeł końcowy ... działało, ale było niesamowicie nieefektywne, a zatem nie działałby na większym wykresie.

Czy ktoś ma jakieś pomysły, które mogłyby wskazać mi właściwy kierunek?

Dziękuję Ci bardzo.

(Próbowałem wprowadzić wizualizację wykresu, ale nie byłem w stanie tego zrobić z powodu mojej niskiej reputacji)

Jeśli krawędzie na wykresie reprezentują tylko prawidłowe ruchy między niektórymi pozycjami, użycie Dijkstry działałoby dobrze. Ponieważ wykres jest nieważony, byłoby to przesadą. Proste wyszukiwanie w pierwszej kolejności da optymalną odpowiedź.

Nicholas udzielił już idealnej odpowiedzi. Pozwól mi jednak zająć się twoją pierwotną próbą użycia wyszukiwania w pierwszej kolejności.

Po pierwsze, albo Dijkstra (która działa dobrze z nieważonymi węzłami, jak zauważył Nicholas Mancuso), albo szerokie wyszukiwanie powoduje wykładnicze marnowanie pamięci. Ich zaletą jest jednak to, że nigdy nie rozszerzają żadnych węzłów, podczas gdy mają gwarancję znalezienia optymalnych rozwiązań. Niestety ich ograniczenie jest dość ważne i nie należy oczekiwać, że skalują się odpowiednio.

$d_{max}$$k$$i$$d_{max} + i\times k$$d_{max}=k=1$ wtedy masz gwarancję znalezienia optymalnego rozwiązania, używając pamięci liniowej w głębi rozwiązania.

$\frac{b}{b-1}$$b$

Twoje zdrowie,