Przeszukiwanie grafu wszerz bez iteracji

Otóż teraz, po przechodzeniu przeszukiwaniu grafu w głąb (tutu wątek), postanowiłem przejść przeszukać go wszerz. Jak poprzednio: iteracja mi się nie podobała, więc napisałem pseudokod bez.

Testy implementacji w JavaScripcie przechodzą (więc nie będę jej zamieszczać raczej). Jednak nadal nie jestem pewien, czy to na pewno jest przechodzenie przeszukiwanie wszerz, i czy jest poprawne. Może ktoś zanalizować pseudokod? Starałem się, by był jak najprostszy, ale mogło mi nie wyjść.

Pseudokod

BFS (vt, vVts, unvVts)
	if isGoal(vt)
	then return vt
	else
		newUnvVts <- concat(relativeComplement(getNbVts(vt), unvVts), unvVts) // <- tutu był bug; poprawione

		if empty(newUnvVts)
		then return nil
		else
			newVt <- newUnvVts[len(newUnvVts) - 1]
			newVVts <- concat(vt, vVts)

			return BFS(newVt, newVVts, newUnvVts)

Jako boczna uwaga: dziwna rzecz. Mój pseudokod BFS DFS wygląda na trudniejszy niż pseudokod DFS BFS. Wydaje mi się natomiast, że pseudokody, który widziałem, zachowują odwrotną relację (pseudokod DFS BFS trudniejszy niż pseudokod BFS DFS). Może żaden z moich pseudokodów nie jest ani ("czysty") BFS, ani DFS?

UPDATE: Oczywiście jest bug – rozjazd pseudokodu i implementacji w JS. Zaraz poprawię.

UPDATE2: Poprawiłem wyżej wspomniany bug.

UPDATE3: Poprawiłem literówki w "bocznej uwadze" pod koniec posta.

UPDATE4: Błąd – inne tytuły wątków ("przechodzenie" vs "przeszukiwanie"). Poprawię ten, żeby nie wprowadzać zamieszania.

UPDATE5: Poprawiona literówka: ifGoal na isGoal.

Tak wyglada pseudokod przeszukiwania grafu (dowolnego):

fun AFS(Graph, s):
	data_struct.add(s)
	while not data_struct.es_empty():
		v = data_struct.get()
		if not marked(v):
			mark(v)
			for w in neighborhood(v):
				data_struct.add(w)

I teraz, jeśli jako data_struct, Użyjesz LIFO, to Masz DFS, a jeśli FIFO - BFS.
W Twoim pseudokodzie nie widze struktury danych i, sorry, jest dla mnie nieczytelny, więc "wysmażyłem" swój.

https://github.com/lion137/Python-Graph

Dzięki za przykłady i za wskazówkę. Ona na pewno pomoże, bo właśnie cały czas myślę mimochodem nad unifikacją obu algorytmów.

Chętnie skorzystałbym też z pseudokodu... Tylko masz w nim pętlę. A ja jej chciałbym uniknąć, jak napisałem. Trudno mi porównywać kod z pętlą i bez niej.

Co konkretnie w moim pseudokodzie jest dla Ciebie nieczytelne? Może ulepszę, wyjaśnię.

chętnie skorzystałbym też z pseudokodu... Tylko masz w nim pętlę. A ja jej chciałbym uniknąć, jak napisałem. Trudno mi porównywać kod z pętlą i bez niej.

Jak przeszukiwac graf bez pętli? Przecież petla jest istotą algorytmu, jak wierzchołek nie jest "zamarkowany", to "markuje" go i w pętli powtarzam czynność dla jego otoczenia. Rekurencyjnie, Możesz zaimplementować DFS, ale też będzie z pętlą:

fun DFS(g, v):
    if g.is_marked(v) is False:
        g.mark(v)
        for w in g.adj_list(v):
            dfs(g, w)

Co konkretnie w moim pseudokodzie jest dla Ciebie nieczytelne? Może ulepszę, wyjaśnię.

Uzywasz czegoś o czym Ty tylko Wiesz, np.:
newUnvVts <- concat(relativeComplement(getNbVts(vt), unvVts), unvVts)

relativeComplement?

Bez pętli chyba można i DFS, i BFS – ale chodzi o to, że nie wiem. Spróbowałem. Moją próbę DFS masz tutaj: Przeszukiwanie grafu w głąb bez iteracji Obie implementacje w JS przechodzą testy. Jeśli pseudokod jest błędny, to może być, że albo (1) testy są złe, albo (2) testy nie uwzględniają pewnych przypadków, które są kluczowe dla poprawności.

Może też być, że inaczej rozumiemy pętlę. Mnie chodzi o to, żeby nie było iteracji = pętli. Czyli sama rekurencja (jak napisałem w pierwszym poście).

Jeśli zaś chodzi o relativeComplement, to jest to różnica zbiorów (tak jak opisane w tym artykule na Wikipedii). Uznałem, że wyrażenie "set difference" nie pasuje; zawiera słowo "set", a przecież wiadomo, że chodzi o zbiory, skoro podaję je jako argumenty. A wyrażenie "difference" wydało mi się "zbyt" wieloznaczne; ponieważ używam funkcji pomocnicznych oznaczających operacje z różnych dziedzin matematyki, uznałem, że mogłoby się z mylić ze zwykłą różnicą. Chętnie przyjmę jakąś alternatywę; może nawet być inna funkcja, realizująca tylko tę samą funkcjonalność.

Chciałbym tylko podkreślić, że zwykle rekurencje zamienia się na iterację, bo działa szybciej i nie ryzykujesz przepełnienia stosu, jeśli ona nie zostanie zoptymalizowana przez kompilator. Dla zabawy jak najbardziej można iść w tą stronę. Na codereview z miejsca bym odrzucił wersje rekurencyjne DFS i BFS, bo wersje iteracyjne tych algorytmów są tak samo proste.

@neves: Dzięki za uwagę. Przyda się. Zdaję sobie sprawę z pewnych ograniczeń rekurencji. Na potrzeby tej implementacji tego algorytmu przyjąłem założenie, by używać rekurencji, a nie iteracji.

Aktualizacja: ponieważ doszedłem do takiego rozumienia algorytmu przeszukiwania wszerz (a także w głąb), że wydaje mi się, że mi ono na razie wystarczy, to chciałbym zamknąć wątek. Aczkolwiek jeśli ktoś w przyszłości miałby jakieś uwagi (np. że kod jest niepoprawny), chętnie przeczytam. Obecną wersję pseudokodu (w rozumieniu tego wątku – ostateczną) załączam poniżej.

Pseudocode

BREADTH_FIRST_SEARCH (vt, vVts, unvVts)
	if isGoal(vt)
	then return vt
	else
		newUnvVts <- concat(
			relativeComplement(
				relativeComplement(
					nbVts(vt),
					unvVts
				),
				vVts
			),
			unvVts
		)

		if empty(newUnvVts)
		then return nil
		else return BREADTH_FIRST_SEARCH(
			last(newUnvVts),
			concat(vt, vVts),
			subarr(
				newUnvVts,
				0,
				len(newUnvVts) - 1 - 1
			)
		)