Zitat von
Pelzi:
Hi,
Ich habe das Problem, dass ich in einem Graphen nicht einen Knoten finden, sondern möglichst viele Knoten besuchen, ohne einen doppelt zu besuchen, möchte.
Also einen möglichst langen weg ohne einen Knoten doppelt zu besuchen und ohne ein festes Ziel. Ich ahb mer schon Tiefensuche, Breitensuche und A*- Suche angesehen, die scheinen aber nciht gegeinet, da sie immer einen Knoten suchen.
Aber die Algorithmen kannst Du doch leicht abwandeln! Schau Dir einfach mal die Idee genauer an und Du solltest es fast sehen. Nimm einfach die Tiefensuche, merk Dir alle besuchten Knoten und die besuchte Tiefe um zu einem Knoten zu gelangen. Dann schaust Du dir an, ob Du einen neuen Knoten erreichen kannst (eben noch nicht besucht). Ist dies der Fall, besuchst Du den (und merkst ihn Dir + erhöhst die Tiefe). Irgendwann gelangst Du zu einem Blatt oder einem Knoten, der nur bereits besuchte Nachbarn hat. Hier schaust Du Dir nun die Tiefe dieser Tour an, ist sie höher als die bisher max. hast Du eine bessere Lösung gefunden. Der Rest ist Rekursion.
Ist vielleicht nicht der schönste Weg, gibt bei Graphen eigentlich immer eine ganze Menge Algorithmen (und deren Einsatzgebiet), die sich leicht finden lassen sollten, aber man kann halt schon mit den von Dir genannten Verfahren meist sehr sehr viel erreichen.
Gruß Der Unwissende