P=np?

[Lorenzy]

Hi Marco Polo,

Das ging ja schnell. War wohl kein NP-Problem.

[Lorenzy]

Zitat von wusel

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]

Zitat von Lorenzy

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.

Gruss, Marco Polo

[Marco Polo]

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

[wusel]

@ Lorenzy

Mein Dank eilt dem Pferd voraus.

also Danke, wusel

[richy]

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/~saj391...u/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.

[Lorenzy]

Zitat von richy

Sprach oder Texterkennung (bei der Post) wuerde ohne die Netzte sicherlich nicht in akzeptabler Rechenzeit funktionieren.
Java Applet :
http://fbim.fh-regensburg.de/~saj391...u/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]

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.

Wahrscheinlich bin ich zu dusselig, das Programm zu bedienen.

[richy]

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.