myCSharp.de - DIE C# und .NET Community
Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 
 | Suche | FAQ

» Hauptmenü
myCSharp.de
» Startseite
» Forum
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Suche
» Regeln
» Wie poste ich richtig?
» Forum-FAQ

Mitglieder
» Liste / Suche
» Wer ist wo online?

Ressourcen
» openbook: Visual C#
» openbook: OO
» Microsoft Docs

Team
» Kontakt
» Übersicht
» Wir über uns

» myCSharp.de Diskussionsforum
Du befindest Dich hier: Community-Index » Diskussionsforum » Entwicklung » Rund um die Programmierung » Wie implementiert man am Besten eine Rekursion in einer Breitensuche?
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | Thema zu Favoriten hinzufügen

Antwort erstellen
Zum Ende der Seite springen  

Wie implementiert man am Besten eine Rekursion in einer Breitensuche?

 
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
TinyToon TinyToon ist weiblich
myCSharp.de-Mitglied

Dabei seit: 24.07.2019
Beiträge: 7


TinyToon ist offline

Wie implementiert man am Besten eine Rekursion in einer Breitensuche?

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Wie implementiert man am Besten eine Rekursion in einer Breitensuche.

Der Sinn ist nach jedem gefundem Knoten in der Breitensuche, die Breitensuche erneut von diesem Knoten zu starten. Leider hat die Queue immer 2 Einträge nach der ersten Suche...
24.07.2019 11:29 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Th69
myCSharp.de-Poweruser/ Experte

avatar-2578.jpg


Dabei seit: 01.04.2008
Beiträge: 3.314
Entwicklungsumgebung: Visual Studio 2015/17


Th69 ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hallo,

sprichst du von einem Binärbaum (wegen der 2)?
Schonmal in  Breitensuche geschaut?
Das "4. Wiederhole Schritt 2." unter "Algorithmus (informell)" kannst du als Rekursion auffassen (wenn auch nicht nötig). Warum möchtest du es denn rekursiv ausführen?
24.07.2019 12:22 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Urza Urza ist männlich
myCSharp.de-Mitglied

Dabei seit: 28.05.2019
Beiträge: 23
Entwicklungsumgebung: VS 2017, VS 2019, ReSharper


Urza ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Hi,

grundsätzlich wären etwas mehr Informationen schön.
Bspw.:
- Wie sieht dein Algorithmus derzeit aus?
- Wie sieht deine Test-Datenstruktur aus?
- ....

Wozu brauchst du eine Queue? Das sieht mir ehr wie ein Überbleibsel einer iterativen Lösung aus.
Für die Rekursion würde ich der rekursiven Funktion das Suchziel (string/int/was auch immer) und eine Liste der Knoten (Input-Knoten) die zu untersuchen sind übergeben.
Enthält die Liste bereits deinen Zielknoten gebe diesen zurück.
Enthält die Liste den Zielknoten nicht, rufe die rekursive Funktion erneut auf, dieses mal mit allen Child-Knoten aller Input-Knoten.
usw.........
Sind die Input-Knoten leer wurde das Ziel nicht gefunden und du musst die Rekursion abbrechen.
24.07.2019 12:33 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Urza Urza ist männlich
myCSharp.de-Mitglied

Dabei seit: 28.05.2019
Beiträge: 23
Entwicklungsumgebung: VS 2017, VS 2019, ReSharper


Urza ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat:
Das "4. Wiederhole Schritt 2." unter "Algorithmus (informell)"

Ich sehe gerade, dass unter "Algorithmus (formal)" der erste Algorithmus die rekursive Variante ist...
24.07.2019 12:39 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
TinyToon TinyToon ist weiblich
myCSharp.de-Mitglied

Dabei seit: 24.07.2019
Beiträge: 7

Themenstarter Thema begonnen von TinyToon

TinyToon ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Es geht darum ein pacman Spiel zu programmieren. Mit der einfachen Breitensuche läuft er aber logischerweise immer nur einen Pfad ab, würde man nun am nächsten Punkt(Knoten) erneut die Suche starten(Rekursion?) dann sollte er irgendwann alle Punkte erreicht haben.
24.07.2019 12:46 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
ThomasE. ThomasE. ist männlich
myCSharp.de-Mitglied

avatar-178.gif


Dabei seit: 26.11.2013
Beiträge: 437
Entwicklungsumgebung: Visual Studio 2015Pro/2017Ent


ThomasE. ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Wozu brauchst du dann eine Breitensuche?

Meine Idee wäre, das Spielfeld in einen (unsichtbaren) Raster darzustellen, jede Figur bewegt sich pixel für pixel in den nächsten Raster...

In dem Fall (aber auch sonst) kann dir die Breite egal sein, da du so oder so eine fixe Spielfeldgröße benötigst, somit hast du schon mal das Maß und nach dem kann man alles andere richten...

Alles so rein aus dem Kopf heraus ;)
24.07.2019 12:59 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
TinyToon TinyToon ist weiblich
myCSharp.de-Mitglied

Dabei seit: 24.07.2019
Beiträge: 7

Themenstarter Thema begonnen von TinyToon

TinyToon ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Die Breitensuche benötige ich um hinterher ein backtracking laufen zu lassen, der pacman soll alle Leckerchen alleine finden...
24.07.2019 13:32 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Alf Ator
myCSharp.de-Mitglied

avatar-586.gif


Dabei seit: 30.10.2007
Beiträge: 586
Entwicklungsumgebung: VS2005 / VS2008


Alf Ator ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat von TinyToon:
Es geht darum ein pacman Spiel zu programmieren. Mit der einfachen Breitensuche läuft er aber logischerweise immer nur einen Pfad ab, würde man nun am nächsten Punkt(Knoten) erneut die Suche starten(Rekursion?) dann sollte er irgendwann alle Punkte erreicht haben.

Hallo TinyToon

Kann es sein, dass du die Breitensuche mit der Tiefensuche verwechselst?
".. läuft er aber logischerweise immer nur einen Pfad ab .." ist doch nur bei der Tiefensuche möglich (korrigiert mich bitte wenn ich falsch liege).

Bei der Breitensuche durchsucht er alle Pfade ebenenweise gleichzeitig. In etwa so wie Urza das beschrieben hat.

Gruß
Alf
24.07.2019 13:34 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
TinyToon TinyToon ist weiblich
myCSharp.de-Mitglied

Dabei seit: 24.07.2019
Beiträge: 7

Themenstarter Thema begonnen von TinyToon

TinyToon ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

richtig, er geht nach den Ebenen... er muss sich also für eine der 4 Richtungen entscheiden und zwar jene die zuerst in die Queue eingetragen wird usw.die anderen besucht er aber nicht, würde er allerdings jedesmal neu suchen, dann müsste er theoretisch alle finden
24.07.2019 13:50 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Alf Ator
myCSharp.de-Mitglied

avatar-586.gif


Dabei seit: 30.10.2007
Beiträge: 586
Entwicklungsumgebung: VS2005 / VS2008


Alf Ator ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat von TinyToon:
richtig, er geht nach den Ebenen... er muss sich also für eine der 4 Richtungen entscheiden und zwar jene die zuerst in die Queue eingetragen wird usw.die anderen besucht er aber nicht, würde er allerdings jedesmal neu suchen, dann müsste er theoretisch alle finden

Wenn ich das richtig verstanden habe, entscheidet er sich bei der Breitensuche eben nicht für eine der 4 Richtungen, sondern geht alle Richtungen, bis das Ziel erreicht ist.
24.07.2019 14:00 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
TinyToon TinyToon ist weiblich
myCSharp.de-Mitglied

Dabei seit: 24.07.2019
Beiträge: 7

Themenstarter Thema begonnen von TinyToon

TinyToon ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

das stimmt, die Breitensuche tut das, aber der Pacman kann nur in eine Richtung laufen
24.07.2019 15:19 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Alf Ator
myCSharp.de-Mitglied

avatar-586.gif


Dabei seit: 30.10.2007
Beiträge: 586
Entwicklungsumgebung: VS2005 / VS2008


Alf Ator ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Zitat von TinyToon:
das stimmt, die Breitensuche tut das, aber der Pacman kann nur in eine Richtung laufen

Also willst du eigentlich keine Breitensuche machen, sondern du willst das dein Packman durch den Dungeon läuft, aber nicht immer den gleichen Weg nimmt?
24.07.2019 16:13 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
TinyToon TinyToon ist weiblich
myCSharp.de-Mitglied

Dabei seit: 24.07.2019
Beiträge: 7

Themenstarter Thema begonnen von TinyToon

TinyToon ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

ich will, dass der pacman durch sein Feld läuft und alle Leckerchen frißt, natürlich gibts auch Hindernisse in dem Feld also er muss ausrum laufen...das ganze aber automatisch...am besten mit der Breitensuche, ich muss ihm ja irgendwie zeigen wo es lang geht
24.07.2019 16:30 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Alf Ator
myCSharp.de-Mitglied

avatar-586.gif


Dabei seit: 30.10.2007
Beiträge: 586
Entwicklungsumgebung: VS2005 / VS2008


Alf Ator ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

Wenn ich das richtig verstanden habe, dann willst du, dass Packman jeweils ein Feld läuft, dann ausrechnet, welche möglichen Lösungswege es gibt, davon einen auswählt und dann wiederum die neuen Lösungswege ausrechnet? Und sollen dabei die Geister berücksichtigt werden?


[Edit: typo]

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Alf Ator am 24.07.2019 16:40.

24.07.2019 16:39 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
TinyToon TinyToon ist weiblich
myCSharp.de-Mitglied

Dabei seit: 24.07.2019
Beiträge: 7

Themenstarter Thema begonnen von TinyToon

TinyToon ist offline

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

genau...ohne Geister...er soll nur alle Leckerchen fressen
24.07.2019 16:53 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Baumstruktur | Brettstruktur       | Top 
myCSharp.de | Forum Der Startbeitrag ist älter als ein Monat.
Der letzte Beitrag ist älter als ein Monat.
Antwort erstellen


© Copyright 2003-2019 myCSharp.de-Team | Impressum | Datenschutz | Alle Rechte vorbehalten. | Dieses Portal verwendet zum korrekten Betrieb Cookies. 24.08.2019 06:19