„Warehouseman's Problem“ ist PSPACE schwer

Beitrag zum Seminar über Algorithmenvon:

Oliver Jelinski

Gliederung

(1) Einführung: Was ist „Warehouseman's Problem“?

(2) Vorschau: Weg des Beweises über drei Reduktionen

(3) Grundlage: PSPACE-vollständiges Rewriting-Problem

(4) 3 Reduktionen, aus denen folgt: „Möbelrücken“ ist PSPACE-schwer

(1) Was ist „Warehouseman's Problem“?

(1) Was ist „Warehouseman's Problem“

übersetzt: „Problem des Lagerarbeiters“

oder „Problem des Lagerverwalters“

Definition (1):

Es seien beliebige rechteckige Objekte in einem 2-dimensionalen rechteckigen Bereich.

Rechtecke dürften sich frei bewegen aber sich oder den Rand des Bereichs nicht

schneiden

Definition (2):

Problem: Ist eine Konfiguration unter diesen Voraussetzungen in eine andere überführbar?

Beispiel 1:

Kommt man von hier ...

Beispiel 1:

nach hier? Ja. (Einfach)

Beispiel 2:

Kommt man von hier ...

Beispiel 2:

... nach hier? Ja, wie wir sehen werden.

(2) Weg des Beweises

Grundlage

PSPACE-vollständiges Rewriting-Problem

1. Reduktion

RWP: PSPACE-vollständiges Rewriting-Problem

TPP: Transpositions- (bzw. Verschiebe-)-Problem für Zeichenketten

2. Reduktion

TPP: Verschiebe-Problem für Zeichenketten

2DO: Verschiebe-Problem für 2D-Objekte

3. Reduktion

2DO: Verschiebe-Problem für 2D-Objekte

WMP: Problem des Lagerarbeiters (Warehouseman's Problem)

daraus folgt:

Problem des Lagerarbeiters ist PSPACE-schwer

RWP≤PTPP≤P2DO≤PWMP

(3) PSPACE-vollständiges Rewriting-Problem

1. Zeichenkette: {S=S1S2S3...Sn} mit allen Sm aus einem Alphabet Σ.

2. Produktionen Pj; jeweils eine der folgenden Formen: AB -> AC oder AB -> CB mit A, B, C ∑.

1. auf jede Zeichenkette S' genau zwei Produktionen anwendbar: eine der Form AB -> AC, und eine der Form AB -> CB.

1. beide Produktionen in mindestens einem Zeichen überschneidend; wenn genau in einem, dann in dem, das sie beide verändern. (Also bei AB -> AC und DA -> EA das A)

Wie ein solchen System aussähe:

???Wichtig ist nur:

es ist PSPACE-vollständig!(s. Hopcroft, Joseph, Whitesides 1982)

(4.1) Reduktion auf TPP

Rewriting-System weit entfernt vom Problem des Lagerarbeiters, weil:

„Objekte“ (Zeichen) verschwinden und tauchen aus dem Nichts auf.

Dinge in Lagern verschwinden nicht!

Näher am Problem des Lagerarbeiters:

„Objekte“ (Zeichen), die irgendwo verschwinden, werden an anderer Stelle aufbewahrt.

Sie werden nicht überschrieben, sondern verschoben.

Was ist ein Verschiebesproblem für Zeichenketten?

Beispiel 1: einfach

ABC...AABBCC

B wird verschoben:

AC...AABBBCC

Was ist ein Verschiebeproblem für Zeichenketten?

Beispiel 2: einfache Simulation der Produktion AB -> AC

ABC...AABBCC->A C...AABBBCC->ACC...AABBBC

also, Ziel:

Simulation der Rewriting-Problems als Verschiebeproblem

1. Erfordernis: genügend Zeichen zur Verfügung

jedes Zeichen |S| mal vorhanden rechts des ursprünglichen S (ab hier:

signifikanter Teil von STPP) gespeichert:

STPP=ABCD...AA...ABB...BCC...CD.......

1. Erfordernis: alle Verschiebungen verboten, die nicht speziell erlaubt sind.

Regel: Es darf immer nur ein Zeichen verschoben werden

zwischen zwei Zeichen im signifikanten Teil darf sich die Anzahl der dazwischen stehenden Zeichen nicht verändern.

Damit: Jede Verschiebung verboten!

Dagegen: Erfordernis 2. eingeschränkt auf die Zeichen aus ∑.

Zeichen aus ∑ ab hier: Standardzeichen

Realisierung des Verbots:

Indizes: Standardzeichen indiziert: Si hat den Index i mod 3

Nachbarschaftsregel: In jeder Folge AjBkCl von Standardzeichen: j = (k-1 mod 3) und l = (k+1 mod 3)

A0B1C2D0E1...

Jedes Einfügen eines Standardzeichens X0, X1 oder X2 würde die Nachbarschaftsregel verletzen.

Folgen für die Gestalt der Zeichenkette:

Jedes Zeichen mit jedem Index |S|/3 mal (aufgerundet) speichern

Problem beim Speichern gleicher Zeichen hintereinander, wegen Nachbarschaftsregel.

Problem beim Speichern gleicher Zeichen hintereinander, wegen Nachbarschaftsregel:

Lösung: Klammerzeichen, für die die Nachbarschaftsregel nicht gilt:

ΛA0B1C2...Γ...[A0][A0]...[][A1][A1]...[A2][A2]...[B0][B0]...

Leere Klammerpaare für Zeichen vorhanden, die aktuell im signifikanten Teil sind:

ΛA0B1C2...Γ...[A0][A0]...[][A1][A1]...[A2][A2]...[B0][B0]...

Bis hier:

alle Voraussetzungen erfüllt jede Verschiebung im signifikanten Teil

verboten

Es fehlen:

erlaubte Verschiebungen

Realisierung von Verschiebungen:

3 Sonderzeichen Mi01, Mi

12, Mi20 für die i-te

Produktionsregel der Gestalt AB -> AC.

3 Sonderzeichen Nj01, Nj

12, Nj20 für die j-te

Produktionsregel der Gestalt AB -> CB.

Nachbarschaftsregel M:

Mijk, das zur Produktion AB -> AC gehört,

darf rechts von Aj stehen, und links von Bk oder Ck, oder links von jedem X(k+1 mod 3). (X ∑)

sonst nirgendwo zwischen Standardzeichen.

Nachbarschaftsregel N:

Nijk, das zur Produktion AB -> CB gehört, darf

links von Bk stehen, und rechts von Aj oder Cj oder rechts von jedem X(j-1 mod 3). (X ∑)

sonst nirgendwo zwischen Standardzeichen.

Also folgendes erlaubt:

...A0B1C2... -> ...A0Mi01B1C2... -> ...A0Mi

01C2... -> ...A0Mi

01C1C2... -> ...A0C1C2...

wenn M der Produktionsregel AB -> AC entspricht.

ähnlich bei Nijk

Damit Reduktion fast abgeschlossen, denn:

Rewriteproblem erfüllbar, genau dann, wenn Transpositonsproblem erfüllbar.

„=>“

Wenn im Rewriteproblem in S' genau zwei Produktionen möglich, dann im Verschiebeproblem im signifikanten Teil die diesen entsprechenden Verschiebungen mit Mi oder Nj möglich.

„<=“

Andere Verschiebungen als die mit Mi oder Nj nicht möglich.

Von beiden je nur eine möglich, weil im Fall des Einsetzens von Mi und Nj kein weiterer Fortschritt möglich wäre:

„<=“

1. Wenn Produktionen sich in mehr als einem Zeichen überschneiden, können gar nicht M und N eingesetzt werden, weil sie direkt nebeneinander gesetzt werden müssten – und das ist verboten.

„<=“

2. Wenn Produktionen sich in genau einem Zeichen überschneiden, folgendes möglich:

...A0Mi01B1Nj

12C2...

B darf jetzt aber nicht verschoben werden, weil sonst M und N nebeneinander

Also: zu einem Zeitpunkt in TPP genau die Verschiebungen mit Mi oder Nj möglich,

genau dann, wenn Produktionen i oder j in RWP möglich.

Reduktion abgeschlossen!

Zur Vollständigkeit: Mi und Nj werden in Klammerpaaren rechts des signifikanten Teils gespeichert.

ΛA0B1C2...Γ...[M1

01][M112][M1

20]...[Mi01][Mi

12][Mi20]...

[N101][N1

12][N120]...[Nj

01][Nj12][Nj

20]...[A0][A0]...[][A1][A1]...[A2][A2]...[B0][B0]...

Man sieht leicht, dass die Reduktion in poynomieller Zeit möglich ist. Also:

TPP ist PSPACE-schwer

RWP≤PTPP

(4.2) Reduktion auf 2DO

Verschiebe-Problem für Zeichenketten weit entfernt vom Problem des Lagerarbeiters, weil:

„Objekte“ sind abstrakte Zeichen.

Verschiebe-Problem für 2D-Objekte schon fast Problem des Lagerarbeiters,

außer dass die Objekte beim Problem des Lagerarbeiters rechteckig sein müssen.

also, Ziel:

Simulation des Verschiebe-Problems für Zeichenketten als Verschiebe-Problem für

2D-Objekte

1. Simulation des Verschiebens der Position eines 2D-Objekts innerhalb einer Reihe von 2D-Objekten

(wie TPP ohne Nachbarschaftsregeln)

kann folgendermaßen aussehen:

einfache Simulation blaugraue Objekte können beliebig

umgeordnet werden

immer, wenn Lücke an dieser Stelle, genau 2 Bewegungssequenzen mgl., so dass die Lücke wieder dort entsteht

1. Sequenz

1. Sequenz kann wiederholt werden, angezeigter Spalt wird verschoben:

2. Sequenz

2. Sequenz kann nicht wiederholt werden, nur ein blaues Objekt passt

beide Sequenzen sind genauso vorwärts wie rückwärts zu vollziehen

in Kombination positionieren sie beliebige blaue Objekte um

eine Art „Transportmaschine“

Beispiel: 1. Objekt an 3. Position

Beispiel: 1. Objekt an 3. Position fertig.

Problem:

bisher keine Nachbarschaftsregeln,

jedes Objekt darf neben jedes.

Lösung:

Einbuchtungen und Ausbuchtungen.

Lösung:

Einbuchtungen und Ausbuchtungen...

... von denen manche zusammen passen, andere nicht.

Die genaue Konstruktion spare ich mir, weil sie recht beliebig gewählt ist.

aber: Problem:

mit den Ausbuchtungen sind die Objekte breiter und passen nicht mehr in die Lücke.

Man muss die Lücke weiter machen.

Lösung: modifizierte „Maschine“

funktioniert so:

funktioniert!

Damit ist die Simulation komplett:

„=>“ Jedes Verschiebe-Problems von Zeichenketten ist eindeutig als Problem von 2D-Objekten darstellbar

„<=“ Jede Instanz von 2DO stellt eindeutig eine Instanz von TPP dar, weil: alle ungewollten Bewegungen ausgeschlossen (führen dazu, dass weitere Bewegungen nicht möglich sind)

Dass die Reduktion in polynomieller Zeit vonstatten geht, dürfte offensichtlich sein.

Also gilt:

Das Verschiebeproblem für 2D-Objekte ist damit PSPACE-schwer.

RWP≤PTPP≤P2DO

(4.3) Reduktion auf WMP

2DO ist schon fast Problem des Lagerarbeiters

Nur die signifikanten Objekte sind noch nicht rechteckig:

2DO ist schon fast „Möbelrücken“

Nur die signifikanten Objekte sind noch nicht rechteckig:

also Ziel:

signifikante Blöcke durch Rechtecke simulieren

alle ungewollten Bewegungen ausschließen

1. Blöcke durch Rechtecke simulierenAm Einfachsten durch horizontales Zerteilen:

Problem: Blöcke können nach links durchrutschen.

Beispiel: Der Block rechts sollte nicht passen.

Beispiel: Der Block rechts sollte nicht passen. Aber:

Lösungsansatz: Eine „Wirbelsäule“ zwischen die „Rippen“ schieben.

Funktioniert!

Reicht aber nicht hin:

Weitere ungewollte Bewegungen bei geöffneter Lücke:

Austausch von „Rippen“ zweier Blöcke

Austausch von Rippen innerhalb der linken bzw. rechten Seite eines Blocks

Voraussetzung der Lösung beider Probleme:

Zwischenblöcke („Spacer“) einfügen:

Zwischenblöcke sind mindestens doppelt so breit wie normale, passen also nie in die Transportmaschine.

Normale und Zwischenblöcke werden modifiziert, so das keine normalen Blöcke nebeneinander passen:

Trennlagen (rot), in denen Rippen der Zwischenblöcke kürzer, die normaler Blöcke länger sind:

Trennlagen (rot), in denen Rippen der Zwischenblöcke kürzer, die normaler Blöcke länger sind.

Deshalb passen zwei normale Blöcke nicht nebeneinander.

normale Lagen (grün), bei denen alle Blöcke ihre normale Breite haben

Deshalb bleiben die Regeln erhalten, nach denen zwei Blöcke Blöcke hintereinander passen, oder nicht. (Jetzt nur mit Zwischenblock)

blaue Lage passt, weil der linke Block ein-, der rechte ausgebuchtet ist, und der Zwischenblock normal.

Wäre der linke nicht eingebuchtet, würden die Blöcke auch weiterhin nicht passen.

um später Einfügen von Spezialzeichen simulieren zu können:

immer zwei Zwischenblöcke zwischen normalen Blöcken

Jetzt zurück zu den Problemen:

Weitere ungewollte Bewegungen bei geöffneter Lücke:

Austausch von „Rippen“ zweier Blöcke

Austausch von Rippen innerhalb der linken bzw. rechten Seite eines Blocks

1. Problem: Austausch von Rippen innerhalb der linken bzw. rechten Seite eines Blocks

Lösung: Einführung verschiedener Höhen der Lagen („Rippen“).

Wenn die unterste (0-te) Lage die Höhe h hat, dann die i-te die Höhe h/3i

jede Lage mehr als doppelt so hoch wie alle höheren zusammen

Weil sonst die Trennlagen nicht mehr in die Zwischenblöcke passten, Austausch ausgeschlossen.

1. Problem: Austausch von Rippen zwischen zwei Blöcken (nur, wenn sich einer der beiden in der Transportlücke befindet).

Lösung: Einführung minimaler Höhenunterschiede

Rippen in Trennlagen: minimal weniger hoch als die Lage

die anderen Rippen: minimal höher als die Lage

zwei Regeln für die Unterschiede:

Alle Rippen der rechten Seite eines Blocks zusammen genauso hoch wie der Block. (genauso links)

Keine andere Kombination von Rippen der beiden Blöcke ganz genau so hoch.

Deshalb ließe sich einer der beiden Blöcke mit ausgetauschten Rippen nicht mehr normal einpassen

Die Bewegung stoppte.

Damit alle ungewollten Bewegungen ausgeschlossen.

2DO ist damit eineindeutig simuliert. („=>“ und „<=“)

Die Reduktion ist vollständig.

Dass die Reduktion in polynomieller Zeit funktioniert, dürfte klar sein.

Einziges Problem: Die minimalen Unterschiede sind schwierig zu berechnen. Aber deren Zahl hängt nur von der Größe des Alphabets und der Menge der Produktionen (aus RWP) ab, nicht von der Eingabelänge. Also konstant.

daraus folgt:

Problem des Lagerarbeiters ist PSPACE-schwer

RWP≤PTPP≤P2DO≤PWMP

(5) Anhang

Literatur

(1) J.E. Hopcroft, J.T. Schwartz, M. Sharir, „On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE-Hardness of the „Warehouseman's Problem““, in: The International Journal of Robotic Research, 1984

(2) J.E. Hopcroft, D. Joseph, S. Whitesides, „Movement problems for 2-dimensional Linkages“, SIAM Journal Computing, 1984 (erstmalig 1982)

(3) Ingo Wegener, Theoretische Informatik – eine algorithmenorientierte Einführung, Stuttgart/Leipzig, 1999

(5) Anhang

Fragen?

(5) Anhang

Danke für die Aufmerksamkeit!

„Warehouseman's Problem“ ist PSPACE schwer

Documents

Infoabend für Schwangere Aller Anfang ist schwer · Aller Anfang ist schwer Still-Info-Seminar für schwangere Frauen Kursleiterin: Hebamme Angela Häfner Donnerstag, 29.09.2016,

Es ist so schwer, es zu verstehen, class wir dich niemals

Statische Prozessoptimierung/ Prozessoptimierung 1 · Wenn das originale Problem keine Ungleichungsnebenbedingungen hat, 4 ist das Problem das mit dem Newton-, dem Gradienten-oder

Trauern ist dieLösung, nicht das Problem!

Buchführung ist gar nicht so schwer

Bearbeitung von INOX und schwer zerspanbaren · PDF fileBearbeitung von INOX und schwer zerspanbaren Materialien Machining of Stainless ... und schwer zerspanbaren Materialien · Machining

„Du Schatz, mein Außenspiegel ist kaputt.“ „Na und, wo ist das Problem?“ „Das Auto liegt drauf.“

PLATONS DIALOGE UND PLATONS LESER Zum Problem einer Platon … · PLATONS DIALOGE UND PLATONS LESER Zum Problem einer Platon-Interpretation Unter den europäischen Philosophen ist

Die Eidelstedter Chronik - · PDF file3 Vorwort E ine lückenlose Chronik der Gemeinde nach Jahren aufzustellen ist schwer, besonders schwer, wenn die notwendigen Unterlagen für

Nutzung von Telematik zur Lösung von Transportproblemen · Das Problem „…entfiel fast ein Viertel (23,2 %) aller von Schwer lastkraftwagen zurückgelegten Fahrzeugkilometer in

Markus schwer jufo

Es ist nicht schwer, ihr Held zu sein - 9783957340719

Nominativ, Akkusativ, Dativ oder Genitiv? – Kein Problem! · NOMINATIV, AKKUSATIV, DATIV ODER GENITIV? – KEIN PROBLEM! 9 Deutsche Fälle Allgemein WAS IST EIN FALL? In diesem

4.3.8 Das Schleudertrauma – ein lösbares Problem · 2019. 9. 9. · Das Schleudertrauma – ein lösbares Problem B. Kügelgen, Koblenz Wohl kaum ein Krankheitsbild ist so lange

Warum ist es so schwer über Liebe zu sprechen? · Herzliche Einladung zur Premiere des Pilot-Theaterprojekts: Warum ist es so schwer über Liebe zu sprechen? Goethe meets Streetart

125 Jahre Alte Technik - lamp.tugraz.atlamp.tugraz.at/~karl/verlagspdf/Festschrift-125Jahre-AT.pdf · ein nur schwer zu lösendes Problem vor: der Raum-mangel. Im Lesliehof war man

Mit dem Alter wurde der Haushalt zu einem Problem. Besonders das Einkaufen fällt mir schwer

Quantencomputer – Kein Problem ist zu komplex · Quantencomputer – Kein Problem ist zu komplex Immer wieder hören wir von Supercomputern, die unglaublich komplexe Probleme mit

Conga - Es ist schwer, maßgeschneiderte Dokumente von Salesforce® zu erstellen

Buchtitel - MacKichan...Ubung 13 Dies ist eine Ubung. Lemma 14 Dies ist ein Lemma. Beweis. Dies ist ein Beweis. Notation 15 Dies ist eine Notation. Problem 16 Dies ist ein Problem