Nur ein Test, ich bin schon lange raus.

K x p¹⁴ = 2 x K x 1,07⁶
p¹⁴ = 2 x 1,07⁶

folglich:
p = 14. Wurzel aus 2 x 1,07⁶

Taschenrechner sagt p=1,08167101

Gegenrechnung:
K= 10000
K x p¹⁴ = 10000 x 1,08167101¹⁴ = 30014,60719
2 x K x 1,07⁶ = 2 x 10000 x 1,07⁶ = 30014,60704

Abweichung ab der vierten Nachkommastelle. Passt


Oder ist da wieder ein ganz gravierender Denkfehler drin?

Zitat von »Lord_Overflowed«

...Logarhytmus (wird das so geschrieben)...

Nö. -> Logarithmus

ich seh nur noch zahlen und ralle nix : ;D

Zitat von »powerslide«

logarithmus hä??

überlegt euch lieber mit welchem logarithmus man das travelling salesman problem löst

zum eigentlichen problem enthalt ich mich mal

Häh, was dat denn?

Er meint Algorithmus...
Das Travelling Salesman Problem (zu Deutsch: Das Handlungsreisenden-Problem) ist ein Optimierungs-Problem, das in der Technik oft vorkommt. So sind die Probleme beim computergestützten Platinenlayout (Autorouting) auch eng verwandt.

Die Uni Kaiserslautern vermeldet:
Das Problem des Handlungsreisenden ist ein sogenanntes Optimierungsproblem, das heißt, es reicht nicht, bei der Suche eine Lösung zu finden, sondern man möchte die bestmögliche (oder zumindest eine sehr gute) haben.
Die Formulierung des Problems ist sehr einfach: Ein Handlungsreisender muß Kunden in einer Reihe von Städten besuchen und zwar in jeder Stadt genau einen. Da er möglichst wenig unterwegs sein möchte, will er die kürzest mögliche Route für seine Tour zusammenstellen. Er kennt die kürzesten Entfernungen zwischen je zwei Städten.
Im nebenstehenden Bild sehen wir das Problem für fünf Städte graphisch umgesetzt mit zwei möglichen Touren. Bei so wenigen Städten sieht das Problem noch relativ leicht aus. Betrachtet man aber 100 oder sogar 1000 Städte, so stellt man schnell fest, daß eine systematische Suche sehr aufwendig ist.
Bisher ist es noch niemandem gelungen, ein Verfahren anzugeben, das nicht exponentiell in der Größe der Eingabe (das sind im wesentlichen die Entfernungsangaben) aufwendiger wird. Man vermutet sehr stark, daß es gar kein Verfahren gibt, das nicht mindestens dieses exponentielle Verhalten zeigt, konnte das allerdings bisher nicht beweisen. Man konnte allerdings beweisen, daß das Problem des Handlungsreisenden ein Muster für eine Menge von Problemen mit diesem exponentiellen Verhalten (die Klasse NP) ist. Dies ist der Grund, warum sich viele Forschungsgruppen in der Informatik mit diesem Problem beschäftigen, da gute Verfahren auf andere Probleme übertragen werden können.

Traveling Salesman hab ich erst vorletzte Woche programmiert ;D

Zitat von »Limbachnet«

Er meint Algorithmus...
Das Travelling Salesman Problem (zu Deutsch: Das Handlungsreisenden-Problem) ist ein Optimierungs-Problem, das in der Technik oft vorkommt. So sind die Probleme beim computergestützten Platinenlayout (Autorouting) auch eng verwandt.

Die Uni Kaiserslautern vermeldet:
Das Problem des Handlungsreisenden ist ein sogenanntes Optimierungsproblem, das heißt, es reicht nicht, bei der Suche eine Lösung zu finden, sondern man möchte die bestmögliche (oder zumindest eine sehr gute) haben.
Die Formulierung des Problems ist sehr einfach: Ein Handlungsreisender muß Kunden in einer Reihe von Städten besuchen und zwar in jeder Stadt genau einen. Da er möglichst wenig unterwegs sein möchte, will er die kürzest mögliche Route für seine Tour zusammenstellen. Er kennt die kürzesten Entfernungen zwischen je zwei Städten.
Im nebenstehenden Bild sehen wir das Problem für fünf Städte graphisch umgesetzt mit zwei möglichen Touren. Bei so wenigen Städten sieht das Problem noch relativ leicht aus. Betrachtet man aber 100 oder sogar 1000 Städte, so stellt man schnell fest, daß eine systematische Suche sehr aufwendig ist.
Bisher ist es noch niemandem gelungen, ein Verfahren anzugeben, das nicht exponentiell in der Größe der Eingabe (das sind im wesentlichen die Entfernungsangaben) aufwendiger wird. Man vermutet sehr stark, daß es gar kein Verfahren gibt, das nicht mindestens dieses exponentielle Verhalten zeigt, konnte das allerdings bisher nicht beweisen. Man konnte allerdings beweisen, daß das Problem des Handlungsreisenden ein Muster für eine Menge von Problemen mit diesem exponentiellen Verhalten (die Klasse NP) ist. Dies ist der Grund, warum sich viele Forschungsgruppen in der Informatik mit diesem Problem beschäftigen, da gute Verfahren auf andere Probleme übertragen werden können.

Für die Lösung dieses mathematischen Problems gibts übrigens nen Preisgeld von über eine Mio $.
Also haltet euch ran!

Naja, im Prinzip ist es gelöst:
Alle Möglichkeiten ausprobieren und die beste auswählen.

Solche Brute-Force-Algorithmen sind aber nicht für große Probleme geeignet, da ihre Laufzeit meistens exponentiell mit der Anzahl der Knoten wächst.

Ich nehme an, hier wird eine bessere Lösung gesucht...
Wofür bekomme ich die Million? Für Polinominale oder lineare oder logarithmische Laufzeit?

Gruß
god0815

Zitat von »god0815«

Naja, im Prinzip ist es gelöst:
Alle Möglichkeiten ausprobieren und die beste auswählen.

Solche Brute-Force-Algorithmen sind aber nicht für große Probleme geeignet, da ihre Laufzeit meistens exponentiell mit der Anzahl der Knoten wächst.

Ich nehme an, hier wird eine bessere Lösung gesucht...
Wofür bekomme ich die Million? Für Polinominale oder lineare oder logarithmische Laufzeit?

Gruß
god0815

ka so genau stand das nicht in der zeitung, und ja deine annahme ist richtig, brute force sollte es nicht sein.....
kannst ja evtl mal googeln, ist eins von ner handvoll matherätsel die mal irgendeine stiftung mit so nem üermathematiker ausgewählt hat für das preisgeld.
und nu arbeitet die halbe welt an der lösung von den dingern.....bzw die mathematiker auf der halben welt

das problem ist in der klasse der np-vollständigen probleme. innerhalb der klasse kannst du die lösung eines problems auf ein anderes mit polynomialem aufwand übertragen... kurz: löst du eines, löst du alle. brute force ist natürlich nicht brauchbar, weil du aufgrund des exponentiellen aufwandes schnell mehr möglichkeiten probieren müsstest, als das gesamte universum atome hat
um die komplexität in den griff zu bekommen, liegt der fokus stark auf neuronalen netzen und evolutionären algorithmen, beides vielversprechende forschungsgebiete...

Zitat von »capt«

um die komplexität in den griff zu bekommen, liegt der fokus stark auf neuronalen netzen und evolutionären algorithmen, beides vielversprechende forschungsgebiete...

Die KI-Verfahren liefern zwar gute Lösungen, aber praktisch NIE die optimale Lösung.
Das Problem des Handlungsreisenden ist ja schon ANNÄHERND gelöst (schließlich sind Platinenlayouter doch recht effektiv ) aber man kann bei diesen _schnellen_ Algorithmen immer davon ausgehen, dass sie die optimale Lösung übersehen.

Neuronale Netzte, Support-Vector-Machines, evolutionäre Algorithmen, Fuzzy-Logic und wie sie alle heißen sind nicht dazu da um Lösungen zu mathematischen Problemen zu suchen (dafür gibts den 'universal problem solver' {leider hat der auch exponentielle Laufzeit}) sondern um Probleme der realen Welt näherungsweise zu lösen.

Z.B. sind die effektivsten Spamfilter (die lernenden Bayes-Filter) meines Wissens Implementierungen von SVMs.

Gruß
god0815

Zitat von »god0815«

Die KI-Verfahren liefern zwar gute Lösungen, aber praktisch NIE die optimale Lösung.

darüber bin ich mir sehr wohl im klaren, ich wollte nur alternativen aufzeigen. und brute force ist ja definitiv keine

die wege des forums sind unergründlich