Diskussion:Suchverfahren

Letzter Kommentar: vor 8 Jahren von 85.178.160.217 in Abschnitt TSP als Suchproblem?

Übersetzung

Bearbeiten

Ist die Übersetzung des Abschnittes Optimierende Suche richtig? Insbesondere habe ich bei der Bezeichnung an sich meine Zweifel. --Ich hab hunga 01:26, 27. Jul 2004 (CEST)


besser Erklärung

Bearbeiten

Wie wäre es wenn jemand, ich kann´s nicht, genau erklärt, was O(n),O(1), O(log n) bedeutet.

Besser vielleicht O*n etc.? --88.67.199.31 19:45, 17. Dez. 2007 (CET)Beantworten

Eine Zeit/Speicherplatz Abschätzung. Siehe Landau-Symbole. -- Sulai 22:23, 17. Dez. 2007 (CET)Beantworten

Heuristik

Bearbeiten

Der Begriff Heuristik ist hier nicht richtig beschrieben. Weder sind Heuristiken ein Gegensatz zu einfachen Algorithmen - heuristische Algorithmen sind oft einfach, und nicht heuristische machmal ganz schön kompliziert - noch setzen Heuristiken notwendigerweise Wissen über den Anwendungsbereich voraus. Ich würde Heurische Verfahren eher im Gegensatz zu exakten Verfahren sehen. -- Mulno 20:25, 25. Mai 2005 (CEST)Beantworten

Hab den Abschnitt jetzt gelöscht, in dem Artikel steht aber leider noch viel Unsinn.
Mulno 17:51, 3. Sep 2005 (CEST)
Leider trifft das heute - 10 Jahre später! - immer noch zu. Viel zu viele vage, nur halbwahre bis falsche Behauptungen... Graf Alge (Diskussion) 17:35, 27. Okt. 2015 (CET)Beantworten

Heuristik 2

Bearbeiten

Heuristiken nicht kompliziert ist ok. Aber Wissen ist immer Voraussetzung, nur meist ist dieses Wissen zu simpel um umgangssprachlich erwähnt zu werden, dabei aber zu wage, als dass ein Naturwissenschaftler es in einen beweisbaren Algorithmus fassen würde.

Alpha-Beta-Pruning

Bearbeiten

Der Link 'Alpha-Beta-Pruning' sollte auf 'Alpa-Beta-Suche' umgelenkt werden.

Regularitäten

Bearbeiten

Wie nennt man Algorithmen, die nach Regelmäßigkeiten suchen (Wiederholungen etc.), die also für den String "abcegfjghugabcne" den Wert "abc" ausgeben, ohne dass konkret danach als Pattern gesucht wird?

Läuft das nicht unter dem Stichwort Korrelationen? Siehe dort. Da sucht man doch eher weniger, sondern macht eine Art statistische Auswertung und prüft dann, ob die Statistische Signifikanz groß genug ist. --PeterFrankfurt 21:41, 16. Jul 2006 (CEST)

Suche in Bäumen

Bearbeiten

BFS und DFS funktionieren in allen zusammenhängenden Graphen (Wenn man reinitialisiert auch in unzusammenhängenden) --goiken 00:57, 6. Sep. 2011 (CEST)Beantworten

TSP als Suchproblem?

Bearbeiten
„Viele Probleme der Graphentheorie können mit Hilfe von Suchalgorithmen gelöst werden. Beispiele für diese Probleme sind das Problem des Handlungsreisenden, …“

Zugegeben, fast jedes Problem der kombinatorischen Optimierung kann man als Suchproblem auffassen, aber gerade beim „Problem des Handlungsreisenden“ ist diese Auffassung (meines Erachtens) ziemlich nutzlos, da das naive Durchsuchen des Lösungsraums viel zu zeitaufwändig ist ( ). Auch handelt es sich bei diesem Problem – im Gegensatz zu den beiden anderen erwähnten Problemen Kürzeste Pfade und minimale Spannbäume – um ein NP‑schweres Problem. Umgekehrt könnte man natürlich fragen, ob der Algorithmus von Dijkstra für die Pfade oder die Algorithmen von Kruskal und Prim Suchalgorithmen im eigentlichen Sinne sind (und, wo wir von kürzesten Pfaden sprechen, der Bellman-Ford-Algorithmus).

Natürlich ist die Aussage richtig, dass alle drei Probleme durch Suchalgorithmen gelöst werden können, aber sind es deswegen geschickte Beispiele? Ich persönlich würde dafür plädieren, das Problem des Handlungsreisenden durch das Eulerkreisproblem (etwa mit dem Algorithmus von Hierholzer) zu ersetzen und eine Erläuterung einzufügen, die darauf hinweist, inwieweit die Bezeichnung der Lösungsalgorithmen der drei Probleme als „Suchalgorithmen“ gerechtfertigt ist. --85.178.160.217 16:12, 27. Feb. 2016 (CET)Beantworten

Falsche Darstellung zum TSP

Bearbeiten

"Heuristische Suchalgorithmen kommen auch dann zum Einsatz, wenn ein Algorithmus zur Problemlösung zu rechenintensiv ist. In diesem Fall wird ein gewisser Fehler in Kauf genommen – also auch eine nicht optimale Lösung akzeptiert – wenn dafür die eingesetzte Rechenzeit deutlich reduziert werden kann. Beispielsweise lassen sich Traveling-Salesman-Probleme bereits ab einigen Dutzend Knoten nicht mehr in realistischer Zeit exakt lösen."

Es gibt sehr viel wissenschaftliche Literatur dazu (z.B. "The Traveling Salesman Problem - A Computational Study" von Applegate, Bixby, Chvátal und Cook), wie man das Traveling Salesman Problem auch bei Instanzen mit tausenden und zehntausenden Städten in der Praxis optimal lösen kann; und selbst wenn die Zeit für eine optimale Lösung nicht reicht, so erhält man doch immerhin gute Schranken zur Abschätzung, wie weit man vom Optimum entfernt ist, was man bei Heuristiken eben nicht hat. Das Statement ist also so pauschal erst einmal missverständlich bzw. falsch.