  |
|
|
 |
 Access, Abfrage Frage ;-) |
Exekutor 
Dabei seit: 06.07.2001
Beiträge: 4.071
Herkunft: From the Other Side
 |
|
| 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
__________________
This is Europe, not L.A.!
Die Deutsche Rechtschreibung ist Freeware,du kannst sie kostenlos nutzen.Allerdings ist sie nicht Open Source,du darfst sie nicht verändern oder in veränderter Form veröffentlichen.
|
|
25.04.2008 18:56 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
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
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
25.04.2008 19:10 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
| 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?
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
25.04.2008 19:45 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
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
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
25.04.2008 21:20 |
|
|
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
|
|
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 
|
|
|
25.04.2008 23:57 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
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
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
26.04.2008 13:10 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
| 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
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
28.04.2008 19:55 |
|
|
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
|
|
@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)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von CDW: 28.04.2008 20:47.
|
|
|
28.04.2008 20:45 |
|
|
phlox81
Bote des Lichts und Moderator
Dabei seit: 19.10.2002
Beiträge: 3.028
Herkunft: Irgendwo im Nirgendwo
|
|
| 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
__________________
Intelligenz ist eine Illusion des Menschen
phlox81.de | codenode.de
|
|
|
28.04.2008 21:06 |
|
|
CDW
eine Simulation
Dabei seit: 12.10.2002
Beiträge: 1.329
Herkunft: CreateRemoteThread
|
|
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_Py...ordinatensystem
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/LinFun...agen/grund9.htm
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von CDW: 28.04.2008 23:43.
|
|
|
28.04.2008 23:32 |
|
|
|
|
|
|
|
