BlackBoard | Druckvorschau: Access, Abfrage Frage ;-)

Geschrieben von Exekutor am 25.04.2008 um 18:56:

Access, Abfrage Frage ;-)

Hallo an alle, ich habe schon recht lang nichts mehr mit Access gemacht und hätte eine Frage:
Also es geht um ein Browser Spiel, wurde gebeten da eine DB zu basteln:
Es gibt Wurmlöcher, mit Anfang und End-Koordinate bspw. 4785<->1025
und davon habe ich ganz viele Paare in einer Tabelle (oder besser in 2, soll ja in beiden Richtungen funktionieren.

So, ich bin jetzt in sagen wir mal 4780 und möchte nach 1024, nun soll die Anfrage alle Paare durchgehen und die kürzeste Verbindung ausgeben, also es soll so rechnen:

Startpunkt --> kürzeste Verbindung zum WL Start -->WL Ende --> Kürzeste Verbindung zum Zielpunkt.

Ist sowas möglich muss zugeben das ich gerade auf dem Schlauch stehe

Vl weiss ja einer Rat.

Ciao Exe

Geschrieben von phlox81 am 25.04.2008 um 19:10:

Hm, ist wohl eher ein Programmierproblem als ein Softwareproblem.

Als allererstes: du solltest eine vernünftige DB nehmen, Access ist z.b. weder Plattformunabhängig und auch sein SQL ist recht speziell. Eine Portierung wird recht teuer dann.

Zum Problem:
Es gibt also eindimensionale Koordinaten, welche von 0 -> 100000 z.b. geht?

Denke mal du hast eine Tabelle Wurmloch: INT,INT z.B.

Dann wäre das z.b. mit einem SQL möglich:
SELECT wurmloch.id FROM wurmloch WHERE (start < 4780 AND end > 1024) OR (start > 4780 AND end < 4780)

Müsstest du jetzt noch entsprechend Sortieren, damit man das Ergebnis hat. Allerdings ist es natürlich nicht universell.

Generell ist Wegfindung aber ein weites und schwieriges Feld.
Evtl googlest du mal nach A* (A-Star) Algorithmus.

phlox

Geschrieben von Exekutor am 25.04.2008 um 19:22:

Hab sogar noch die Rechte zum verschieben

Hmhm ja werd mal sehen, irgendwie muss es ja klappen

Falls wer noch Ideen hat immer her damit.

Ciao Exe

Geschrieben von phlox81 am 25.04.2008 um 19:45:

Zitat:

Original von Exekutor
Hab sogar noch die Rechte zum verschieben

Hmhm ja werd mal sehen, irgendwie muss es ja klappen

Falls wer noch Ideen hat immer her damit.

Ciao Exe

Wie sind deine Ideen?
Und wie ist die genaue Datenstruktur?

Geschrieben von Exekutor am 25.04.2008 um 20:11:

(Eingabe.Start < WL Start.WL Start & Eingabe.Ziel > WL End.WL End) OR (Eingabe.Start > WL Start.WL Start & Eingabe.Ziel < WL End.WL End)

Kann es sein das du dich oben verschrieben hast? 2 Mal4780am Ende macht für mich keien Sinn.

Struktur:
Tabelle Eingabe mit Feldern Start und Ziel
Tabelle WL Start mit Feld WL.Start
Tabelle WL End mit Feld WL End

sollte doch zunächst so funktionieren oder?

Ciao Exe

Geschrieben von Exekutor am 25.04.2008 um 20:34:

Also das ganze ist jetzt erst rudimentär, ich will erst einmal das zum laufen bekommen und dann nach und nach erweitern. Nur zur Info.

Ciao Exe

Geschrieben von phlox81 am 25.04.2008 um 21:20:

Also die Aufgabe ist garnicht so trivial, wenn du wirklich den optimalen Weg finden willst.

Ich nehme jetzt mal an das die Wurmlöcher eine Gewichtung von 0 haben, sprich die Reise Zeit ist minimal. Die "normale" Reisegeschwindigkeit spielt dann auch keine Rolle, da ja für normale Strecken gleich, also Gewichtung erstmal -> 1.

D.h:
reisedistanz = start - ziel;

Jetzt müsstest du vom startpunkt und endpunkt aus alle Wurmlöcher in der reisedistanz die anschauen, ob sie dies erfüllen:

Ende innerhalb dieser Zone ist irrelevant für die Perfektion, würde aber die Zahl der Möglichkeiten einschränken. Eigentlich müsste man jetzt iterativ vorgehen, und jedes WL abchecken, ob es die Reisedistanz verkürtzt. Und dann das kürzerste nehmen.
Schwierig wird es natürlich wenn du auch über mehrere WL routen willst. Wäre ja ein möglicher Fall.

phlox

Geschrieben von CDW am 25.04.2008 um 23:57:

wegen Routing:
Naja, über mehrere Knoten würde nach Graphentheorie und kürzestem Weg schreien:
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
wobei dann die Entfernung=Gewichtung wäre und man dann wohl (wenn ich das Problem richtig sehe) alle End und Startpunkte der Wurmlöcher miteinander Verbinden müsste, um wirklich alle Möglichkeiten zu haben. Das Ganze könnte man vielleicht per SQL hinbiegen (zumindest per Kreuzprodukt die Start/Endpunkte verbinden) - aber ab da wird es hässlich

Geschrieben von Exekutor am 26.04.2008 um 08:48:

Danke dir CDW, war wohl gestern Abend zu verkopft, eben in 2 Minuten die Abfrage erstellt die mir das beste WL-Paar ausgiebt:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:

SELECT 
[WL Start].[WL Start], [WL End].[WL End], Eingabe.Start
FROM 
Eingabe, [WL End] INNER JOIN [WL Start] ON [WL End].ID = [WL Start].ID
WHERE 
((([WL Start].[WL Start])<=([Eingabe].[Start]))) AND ([WL End].[WL End] <= [Eingabe].[Ziel])
ORDER BY 
[WL Start].[WL Start];

So.. nu gehts weiter.
Hm.. werd mit den Algo mal anschaun, wenn jemadn Denkansätze für eine SQL Umsetzung hat darf er hier gerne posten.
Danke euch schon einmal alle!

Ciao Exe

Geschrieben von phlox81 am 26.04.2008 um 13:10:

Ich hab mir mal gedanken gemacht, und wie CDW denke ich das man für performante Lösungen wohl einen Graphen aufbauen muss.

Was du gestern gesagt hast, war ja das es pro woche 1000 Wurmlöcher gibt, auf einem Spielfeld von 0 - 9999.

Um dies nun in einen Graphen zu überführen, müsstest du die start-ende werte von Wurmlöchern als Kanten im Graphen ansehen, da sie ja effektiv Verbindungen sind. Du hättest also 10000 Knoten, und dazwischen 1000 Wurmloch kanten, und jeweils eine Kante zu den beiden Nachbarn.

code:
1: 2: 3: 4: 5: 6: 7: 8:	class Kante { int start, end, weight; }; class Knoten {int pos;}; class Graph { list<Knoten> knoten; list<Kanten> kanten; };

Darauf könntest du dann den A* z.B. ansetzen.
In C++ gibts das schon fertig, als Library.

phlox

Geschrieben von Exekutor am 28.04.2008 um 19:13:

So wir haben mal eine Minismalslösung mit Excel hinbekommen, nur ein WL weit aber es funktioniert:

RUNDEN(WURZEL(((B9-$C$1)^2)+(C9-$D$1)^2);0)+RUNDEN(WURZEL(((D9-$C$2)^2)+(E9
-$D$2)^2);0)

Also eine WL Koordinate mit 4 Stellen wird in 2 2er paare aufgeteilt
also 4567 --> 45 67

Spalten B und C sind Startkoordinate, D und E End. Zeile 1 sind die eingegebenen Koords für Start und Ziel der jeweiligen Abfrage.

Ciao Exe

Geschrieben von phlox81 am 28.04.2008 um 19:55:

Zitat:

Original von Exekutor
So wir haben mal eine Minismalslösung mit Excel hinbekommen, nur ein WL weit aber es funktioniert:

RUNDEN(WURZEL(((B9-$C$1)^2)+(C9-$D$1)^2);0)+RUNDEN(WURZEL(((D9-$C$2)^2)+(E9
-$D$2)^2);0)

Also eine WL Koordinate mit 4 Stellen wird in 2 2er paare aufgeteilt
also 4567 --> 45 67

Spalten B und C sind Startkoordinate, D und E End. Zeile 1 sind die eingegebenen Koords für Start und Ziel der jeweiligen Abfrage.

Ciao Exe

Hm, müsste das nicht zum gleichwertigen Ergebnis führen? :

code:
1:	RUNDEN((B9-$C$1)+(C9-$D$1));0)+RUNDEN((D9-$C$2)+(E9-$D$2);0)

Falls ja, ist es auch um einiges Performanter.

phlox

Geschrieben von Exekutor am 28.04.2008 um 20:35:

Also ich hab mir mal ein paar Infos von der mächtigsten Ally und deren Coder geholt.. er hat es mit Java realisiert und zwar mit vielen Schleifen, und wohl die Datenmenge sukzessive verringert, d.h. nach jedem Schritt alle Entfernungen größer 10 rausgeworfen.

Ciao Exe

Geschrieben von CDW am 28.04.2008 um 20:45:

@phlox81: hm. Ich vermute, es wird versucht den Abstand der zwei Punkte auszurechnen. Das wäre in R² für gewöhnlich |x-y| -> und dann die Norm anwenden. Bei R² kennt man das vielleicht als Euklidische Norm
http://de.wikipedia.org/wiki/Euklidischer_Raum
das wäre WURZEL(x1^1+x2^2)
hier werden häufig aufgrund der "hoch 2" die Betragsstriche weggelassen.
Aber die Wurzel sollte man nicht weglassen können

Allerdings verwirrt mich hier die Formel etwas:
Wenn ich nicht total alles vergessen habe, sollte man den Abstand zweier Punkte so ausrechnen können: |vektor1-vektor2|=ergebnisvektor
wurzel(x1^2+x2^2...) (x1, x2 usw sind einzelne "Komponenten" des Vektors).

Bsp: V1(1,1) V2(4,8)
|V1-V2|=(|1-4|,|1-8|) =(3,7) (die Beitragsstriche kann man ja weglassen, da anschließen hoch 2 genommern wird)

Länge des Vektors: (3^2+7^2)^(1/2)=9+49=Wurzel(56)=7,irgendas=> das wäre der Abstand zwichen v1 und v2 (oder eben start und endpunkt eines Wurmlochs)

Hier sehe ich allerdings eine Aufspaltung in Wurzel(blub)+Wurzel(blub). K.A ob man das so machen darf, aber rein intuitiv würde ich sagen: nein.
Denn Wurzel(5^2)+Wurzel(5^2)=Wurzel(25)+Wurzel(25)=10 ist nicht dasselbe wie Wurzel(5^2+5^2)=Wurzel(50)

Geschrieben von phlox81 am 28.04.2008 um 21:06:

Zitat:

Original von CDW
@phlox81: hm. Ich vermute, es wird versucht den Abstand der zwei Punkte auszurechnen.

Ja denke ich auch.

@CDW Ich bezog mich hier auf die von exe gepostete Formel.

Und für mich ist die Formel ein simpler Pythagoras:
WURZEL(a²+b²) + WURZEL(c²+d²)
Nu kannst du dir hier das Wurzelziehen zumindest sparen, weil es den Betrag nur verringert, liefert zwar das nicht ganz korrekte Ergebnis, aber für die Bestimmung der kürzesten Strecke ist das ja irrelevant.

phlox

Geschrieben von Exekutor am 28.04.2008 um 21:06:

Hm, klingt schlüssig was du da sagst, aber die Berechnung funktioniert.. also wir habens ausgetestet für mehrere Koordinaten.

Ciao Exe

Geschrieben von CDW am 28.04.2008 um 23:32:

also kann sein, dass mich nur diese Excelformel verwirrt

ich sehe das als:
Wurzel( (B-C)²+(C-D)²)+Wurzel((D-C)²+(E-D)²)
wobei BC die Startkoordinaten und DE die Endkoordinaten sind.

Hab mal probeweise durchgerechnet: von 1,1 zu 99,99
nach der Formel wäre das:
B=1,C=1; D=99,E=99
Wurzel(0²+98²)+Wurzel(0²+98²)=98+98=196

nach Euklid wäre das:
(1,1)-(99,99)=(98,98)->Länge des Vektors: Wurzel(98²+98²)=138
also schon ein etwas "heftiger" Unterschied

Nach Pythagoras wäre das ja auch:
a²+b²=c²
abstand zwischen den beiden X koordinaten=a
abstand zwischen den beiden Y koordinanten=b
abstand zwichen den beiden Punkten wäre die Strecke c
Wurzel((x1-x2)²+(y1-y2)²)
http://de.wikipedia.org/wiki/Satz_des_Pythagoras#Kartesisches_Koordinatensystem

also c=Wurzel aus a²+b²
(a²+b²)^(1/2)
also a=(1-99)=98; b=(1-99)=98
Wurzel(98²+98²)=138
Hätte mich auch gewundert, wenn Pythagoras etwas anderes ergeben hätte

Wegen der Begründung, dass es zwar ungenau ist, aber trotzdem klappt:
Bsp wo das in die Hose geht:
WL1 von (1,80) zu (1,1)
und WL2 von (60,60) zu (1,1)

nach pythagoras/euklid überbrückt WL1 =79, WL2=83 Streckeneinheiten
also WL1 Route besser als WL2

nach der "komischen"

Formel überbrückt WL1 =Wurzel(79²+79²)+wurzel(79²)=111+79=190 Einheiten

WL2 dagegen: Wurzel(0²+59²)+Wurzel(0²+59²)=118
also WL2 deutlich besser als WL1

Wie gesagt, kann sein dass ich die Formel falsch verstehe - oder auch die Berechnung im Spiel etwas "abendteurerlich" umgesetzt wurde

hab auch was nettes dazu gefunden:
http://www.nb-braun.de/mathematik/LinFunkNeu2/grundlagen/grund9.htm