kürzeste Pfade < Algorithm. Geometrie < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 13:10 Fr 14.04.2006 | | Autor: | Bastiane |
| Aufgabe | Wir betrachten die Ebene [mm] \IR^2 [/mm] mit polygonalen Hindernissen. Bezeichne [mm] \pi(p,q) [/mm] einen kürzestesn Pfad zwischen zwei Punkten p und q in der Ebene. Können sich zwei kürzeste Pfade [mm] \pi(p,q) [/mm] und [mm] \pi(p,r) [/mm] kreuzen, wenn
(i) der Schnittpunkt an einem Hindernis liegen darf?
(ii) der Schnittpunkt nicht an einem Hindernis liegen darf? |
Hallo!
Grübele gerade über obige Aufgabe nach, finde aber keinen richtigen Ansatz. Ich vermute, dass die Antwort in beiden Fällen "nein" ist, kann das aber nicht begründen.
Ich habe versucht, irgendwelche "Extrembeispiele" zu nehmen, wo sich zwei solche Wege kreuzen könnten. Aber mir fallen schon nicht so viele Möglichkeiten ein, wie es überhaupt mehrere kürzeste Wege geben kann. Und dann habe ich erst recht keine Idee, wie sich dann zwei Wege wie oben beschrieben kreuzen könnten.
Hat jemand irgendeine Idee, wie ich da weiter drüber nachdenken könnte und das evtl. "beweisen" könnte?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:28 Fr 14.04.2006 | | Autor: | Hanno |
Hallo Christiane.
Meinst du zwei kürzeste Pfade zwischen zwei festen Punkten $p,q$ oder einen Pfad zwischen $p,q$ und einen zwischen $p,r$ (wie im Posting angegeben)?
Wenn letzteres der Fall ist, musst du die Definition von "Schnitt" präzisieren. Ansonsten wären beide Fragen mit Ja zu beantworten; um dies einzusehen, wähle drei verschiedene Punkte $p,q,r$, die in dieser Reihenfolge auf einer Geraden im [mm] $\IR^2$ [/mm] liegen. Dann ist [mm] $\pi(p,q)$ [/mm] die Strecke von $p$ nach $q$, und [mm] $\pi(p,r)$ [/mm] die von $p$ nach $r$; erstere ist eine Teilmenge (wenn man die Strecken als Teilmengen des [mm] $\IR^2$ [/mm] auffasst) letzterer; wenn man die Schnitteigenschaft über die von 0 verschiedene Mächtigkeit der beiden Punktmengen, die die Wege beschreiben, auffasst, schneiden sich beide Strecken.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:27 Fr 14.04.2006 | | Autor: | Bastiane |
Hallo Hanno!
Schon mal vielen Dank für deine Mitteilung. 
> Meinst du zwei kürzeste Pfade zwischen zwei festen Punkten
> [mm]p,q[/mm] oder einen Pfad zwischen [mm]p,q[/mm] und einen zwischen [mm]p,r[/mm]
> (wie im Posting angegeben)?
Ich hatte zuerst auch gedacht, es seien nur zwei feste Punkte p und q, aber so wie es da steht, müssen es ja wohl drei Punkte p,q,r sein (wenn das kein Druckfehler ist).
> Wenn letzteres der Fall ist, musst du die Definition von
> "Schnitt" präzisieren. Ansonsten wären beide Fragen mit Ja
> zu beantworten; um dies einzusehen, wähle drei verschiedene
> Punkte [mm]p,q,r[/mm], die in dieser Reihenfolge auf einer Geraden
> im [mm]\IR^2[/mm] liegen. Dann ist [mm]\pi(p,q)[/mm] die Strecke von [mm]p[/mm] nach
> [mm]q[/mm], und [mm]\pi(p,r)[/mm] die von [mm]p[/mm] nach [mm]r[/mm]; erstere ist eine
> Teilmenge (wenn man die Strecken als Teilmengen des [mm]\IR^2[/mm]
> auffasst) letzterer; wenn man die Schnitteigenschaft über
> die von 0 verschiedene Mächtigkeit der beiden Punktmengen,
> die die Wege beschreiben, auffasst, schneiden sich beide
> Strecken.
So ungefähr (nur mit einem etwas komplizierteren Beispiel) hatte ich mir das auch schon gedacht. aber dann wäre es doch eigentlich zu einfach, oder? "Schnitt" haben wir nicht definiert, ich vermute aber (nach dem, was wir in der Vorlesung sonst gemacht haben), dass es sich nur um einen Schnittpunkt handeln soll. In der Aufgabenstellung heißt es ja auch "wenn der Schnittpunkt...".
Viele Grüße
Bastiane
|
|
|
|
