Archiv verlassen und diese Seite im Standarddesign anzeigen : P=np?
Hi MP
Aufgrund der chaotischen Bedingungen müsste man wohl alles von Beginn an simulieren.
So habe ich das auch begruendet.
Das ist genauso wie bei NP-vollständigen Problemen. Die kann man leider auch noch nicht lösen.
Doch, das geht mit neronalen Netzwerken. Ein Kohonen Netztwerk loest das Problem des Handlungsreisenden innerhalb weniger Minuten.
Das Netzwerk ist so einfach, dass man es leicht selber Programmieren kann.
Und auf Grossrechnern werden z,B Kollisionen von Galaxien simuliert.
Aber wahrscheinlich ist meine Idee auch nicht neu.
Im Sonnensystem ist zudem fast die gesamte Masse innerhalb der Sonne konzentriert, während sich bei einer Galaxie die Hauptmasse nicht aufs Zentrum beschränkt.
Das hatte ich in der Ueberlegung auch beruecksichtigt. Ebenso die voellig anderen Zeitmaßstaebe. Und im Zenrum jeder Galaxie soll es ein schwarzes Loch geben.
Klar letzendlich sind Sonnensystem und Galaxien nicht voellig miteinander vergleichbar.
Es war nur eine Ueberlegung wie der Endzustand von Galaxien aussehen koennte, wenn ich sie mit einem Sonnensystem vergleiche.
Schwarze Loecher die um ein zenrales schwarzes Loch kreisen.
Welche Prognosen stellen hier eigentlich die serioesen Wissenschaftler ?
Viele Gruesse
Doch, das geht mit neronalen Netzwerken. Ein Kohonen Netztwerk loest das Problem des Handlungsreisenden innerhalb weniger Minuten.
Hi richy,
Mit diesem Trick kann auch "nur" eine Annährung des Problems des Handlungsreisenden erreicht werden. Es gibt aber nur eine Lösung - die kürzeste Strecke. Selbst wenn man mit solchen neuronalen Netzwerken den Weg durch 50 Städte berechnen würde, hätte man immer noch Millionen von möglichen Lösungen, welche aber alle (zufällig könnte sich natürlich auch der heilige Gral darunter befinden) nur Annährungen des Problems sind.
Das soll natürlich nicht die Leistung solcher neuronalen Netzwerke schmälern. Es ist schon erstaundlich was in so kurzer Zeit damit erreicht werden kann - Annährung hin oder her.
Die derzeit einzigen Kandidaten um NP-Probleme in zumutbarer Zeit zu lösen, sind Quantenrechner bzw. deren Algorithmen.
Marco Polo
29.07.08, 21:21
Doch, das geht mit neronalen Netzwerken. Ein Kohonen Netztwerk loest das Problem des Handlungsreisenden innerhalb weniger Minuten.
Das Netzwerk ist so einfach, dass man es leicht selber Programmieren kann.
Hi richy,
Kohonen Netzwerk? Klingt interessant. Hast du da mehr Infos zu?
Ich denke aber, dass das Problem des Handlungsreisenden kein NP- vollständiges Problem ist, sondern lediglich ein NP Problem.
Wenn du z.B. 20.000 Knotenpunkte hast, dann soll das ein leicht zu programmierendes Netzwerk in so kurzer Zeit lösen können? Ich bin da eher skeptisch. Braucht man dafür nicht eher Grossrechner?
Gruss, Marco Polo
Hi!
Ich denke aber, dass das Problem des Handlungsreisenden kein NP- vollständiges Problem ist, sondern lediglich ein NP Problem.
Möglicherweise ist es nur ein P-Problem. Meines Wissen gibt es hier in der Mathematik unterschiedliche Auffassungen. Einmal hier: http://lexikon.meyers.de/meyers/Spezial:Zeitartikel/P%3DNP%3F?teaserID=100340, wonach das "Problem des Handlungsreisenden" als NP-Problem dargestellt wird, - andererseits finde ich plausibler, dass dies nur ein 'P-Problem' ist, da es in 'vernünftiger Zeit' proportional zu n-Rechenschritten offenbar zu lösen ist, wie richy bereits erwähnt hat. Primzahlfaktorisierungen würden hier demgegenüber wahre NP-Probleme darstellen, da die erforderlichen Rechenschritte hier exponentiell zunehmen.
Ein 'NP-Vollständiges Problem' wäre demnach ein Algorithmus der das Faktorisierungsproblem löst. Und so einer ist nicht bekannt.
Möglicherweise ist es nur ein P-Problem.
Hi Gandalf,
Möglich. Aber Spekulationen sind bei solchen Problemen fehl am Platze. Die Knacknuss ist ja, es zu beweisen bzw. zu widerlegen. Raten kann jeder.;)
andererseits finde ich plausibler, dass dies nur ein 'P-Problem' ist, da es in 'vernünftiger Zeit' proportional zu n-Rechenschritten offenbar zu lösen ist, wie richy bereits erwähnt hat.
Eine Annäherung ist noch keine Lösung.
Kohonen Netzwerk? Klingt interessant. Hast du da mehr Infos zu?
Hab hier etwas dazu gefunden. Im Java-Applet unten kann man sogar die einzelnen Annäherungen in einer Animation beobachten.
http://www.htw-dresden.de/~iwe/Belege/Boerner/
Hallo Lorenzy,
Intermezzo
Eine Annäherung ist noch keine Lösung.
Tailorreihe, Regulafalsi oder Newtonverfahren ... sind (Lösungen der Numerik), ja sicherlich Nährungen ... aber ohne die, hätte ich zu meiner Schulzeit nicht mal ein Tafelwerk besessen. Kennst Du noch einen Rechenstab? Zu meiner Zeit "Schätzeisen" genannt? Ob Taschenrechner, PDA oder Klapprechner ... wo man hin sieht, Polynome ...
Kosmologie interessiert mich eigentlich sehr, aber irgenwie habe ich auf dem falschem Bahnsteig gestanden (bzw. ich war lange nicht vor Ort) ... Der Zug scheint weg.
Tailorreihe, Regulafalsi oder Newtonverfahren ... sind (Lösungen der Numerik), ja sicherlich Nährungen ... aber ohne die, hätte ich zu meiner Schulzeit nicht mal ein Tafelwerk besessen. Kennst Du noch einen Rechenstab? Zu meiner Zeit "Schätzeisen" genannt? Ob Taschenrechner, PDA oder Klapprechner ... wo man hin sieht, Polynome ...
Hi Wusel,
Ich wolllte damit ausdrücken, dass man dem Problem N=NP? mit einer Annährung auch nicht näher kommt.;)
Hallo Lorenzy,
Ja. Ziemlich OT hier. Die Lösung hierzu heisst MP.
könntest Du bitte mal einem älteren Mann aufs Pferd helfen.
Hü, wusel
Marco Polo
30.07.08, 00:32
Ja. Ziemlich OT hier. Die Lösung hierzu heisst MP.:)
Du sagst es Lorenzy. :D
Obige Beiträge wurden auf Anregung von Lorenzy hierhin verschoben.
Ausser den Beitrag von richy. Den habe ich kopiert, da er nicht OFF-Topic war,
aber dennoch teilweise hier reinpasst.
Hi Marco Polo,
Das ging ja schnell. War wohl kein NP-Problem.;)
könntest Du bitte mal einem älteren Mann aufs Pferd helfen.
OT ist die offizielle Abkürzung für Off Topic (vom Thema abweichen)
MP ist die inoffizielle Abkürzung für Marco Polo (Moderator)
Ich hoffe du sitzt jetzt bequem.
Marco Polo
30.07.08, 00:45
Hi Marco Polo,
Das ging ja schnell. War wohl kein NP-Problem.;)
Doch, es war ein NP-Problem.
Ich habe aber schnell ein Kohonen-Netzwerk programmiert. :D
Gruss, Marco Polo
Marco Polo
30.07.08, 00:56
In der JULI-Ausgabe der Spektrum der Wissenschaft, gibt es einen Bericht "Grenzen der Quantencomputer", der sich auch mit P und NP Problemen beschäftigt. Vielleicht stelle ich am Donnerstag eine kurze Zusammenfassung hier rein. Vorher komme ich leider nicht dazu.
Gruss, Marco Polo
@ Lorenzy
Mein Dank eilt dem Pferd voraus.
also Danke, wusel
Hi
Den Rechenaufwand fuer eine numerische Aufgabenstellung laesst sich oft durch effiziente Programmiereung reduzieren. Meist gelangt man dabei von einer polynomalen Rechenaufwand wie n^2 (n ist die Zahl der Objekte, beim Handlungsreisenden die Anzahl der Kunden) zu einem Rechenaufwand ln(n)*n.
Zum Beispiel ueber die Teile und Herrsche Methode.
Man kann also nicht pauschal sagen, dass ein Problem p oder np ist, denn
es gibt vielleicht die Moeglichkeit ueber ein geeignetes Verfahren den Aufwand zu reduzieren.
Anschinend ist man sich nicht sicher ob das Problem des Handlungsreisenden effizient programmieren laesst.
http://www.uni-kl.de/AG-AvenhausMadlener/tsp-ger.html
WIKI :
http://de.wikipedia.org/wiki/Handlungsreisendenproblem
Da dem Handlungsreisenden in jedem Schritt die Städte zur Auswahl stehen, die er noch nicht besucht hat, gibt es (n-1)! mögliche Touren für ein asymmetrisches und (n − 1)! / 2 Touren für ein symmetrisches TSP. Die Größe des Suchraums hängt also überexponentiell von der Anzahl der Städte ab.
Das Problem des Handlungsreisenden ist sowohl für den allgemeinen als auch für den symmetrischen oder metrischen Fall NP-äquivalent. Unter der allgemein vermuteten, bisher aber unbewiesenen Annahme, dass die Komplexitätsklassen P und NP verschieden sind (siehe P-NP-Problem), folgt daraus, dass keine deterministische Turingmaschine existiert, die das Problem für jede Instanz in polynomialer Laufzeit bezüglich der Anzahl der Städte löst.
Ueber das Kohonen Netzwerk gelingt die Naeherung ueber einen polynominalen Aufwand.
Ich habe solch ein Netzwerk auch mal dazu verwendet eine Triangulierung einer Punktmenge zu berechnen. Schade hab die Bilder leider nicht gescannt wie ich dachte. Und wie Marco schon bemerkte ist es leider nicht sicher, dass man wirklich die beste oder eine fehlerfreie Loesung erhaelt.
Aber im Fall einer Simulation einer Galaxie oder Staubwolke waere das wohl nicht so tragisch, da sicherlich auch die Anfangswerte nicht genau stimmen.
Diese ganzen neuronalen Netzwerke haben leider genauso wie die Chaostheorie etwas an ihrer Faszination b.z.w Beliebtheit verloren.
(Es sind nichtlineare Algorithmen, von denem man eigentlich nicht weiss wie sie konkret funktionieren. Wenigstens kann man sie analytisch nicht erfassen)
Dennoch sehr empfehlenswert und ausgesprochen verblueffend.
Sprach oder Texterkennung (bei der Post) wuerde ohne die Netzte sicherlich nicht in akzeptabler Rechenzeit funktionieren.
Java Applet :
http://fbim.fh-regensburg.de/~saj39122/begrolu/kohonen.html
(2000 Lernschritte, Neben "You wrote" mit Maus schreiben.)
Verblueffend oder ?
Die Bichstaben sind uebereinander im Netzwerk gespeichert. Wo kann man eigentlich nicht sagen. Aehnlich wie in einem Hologramm.
Und der Preis dafue dass es alle moeglichen Varianten erkennen kann ist leider die Ungenauigkeit.
Ich habe aber schnell ein Kohonen-Netzwerk programmiert
Das ist wirklich kein Aufwand. Irgendwo hab ich noch einen C Code davon.
Kann ich mal fuer experementierfreudige hier reinstellen.
Sprach oder Texterkennung (bei der Post) wuerde ohne die Netzte sicherlich nicht in akzeptabler Rechenzeit funktionieren.
Java Applet :
http://fbim.fh-regensburg.de/~saj39122/begrolu/kohonen.html
(2000 Lernschritte, Neben "You wrote" mit Maus schreiben.)
Verblueffend oder ?
Ich hab das gleiche auf dem iPod. Funktioniert aber nicht so gut und ist auch nur eine Spielerei. Dasselbe Prinzip kommt wohl auch bei der Bilderkennung von autonomen Fahrzeugen zum Zug.
Marco Polo
30.07.08, 03:14
Bei mir funktioniert das Programm net so recht.
Zuerst zeichne ich einen Buchstaben. Meinetwegen A.
Dann drücke ich die Learn-Taste.
Dann auf clear und nochmal den Buchstaben A zeichnen.
Bei drücken der recognize-Taste kommt dann B heraus. :confused:
Wahrscheinlich bin ich zu dusselig, das Programm zu bedienen. :o
Hi MP
Geht bissel anders :-)
Zuerst drueckst du "learn"
Dann lernt das Netz die auf der Seite abgebildeten Buchstaben.
Dann clear dann schreiben und recognice
clear schreiben recognice
clear schreiben recognice ....
Arbeitet aber nicht perfekt.
Anders bei der Post. Da wird rasend schnell die PLZ gelesen.
und die Fehlerquote ist im Lauf der Jahre sehr gering geworden.
vBulletin® v3.8.8, Copyright ©2000-2024, vBulletin Solutions, Inc.