BuK/IIm10/BuK-Kreativaufgabe05 G2

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
= POSTsches Korrespondenzproblem =

== Aufgabe ==
Entwickeln Sie ein Scheme-Programm, das eine zugehörige Indexfolge mit den im Problem gegebenen Eigenschaften findet, falls eine solche Indexfolge existiert.


==Lösung ==

Das POSTsche Korrespondenzproblem lautet:
 
Gegeben ist eine endliche Liste von Paaren <math>(({x}_{1},{y}_{1}), ({x}_{2},{y}_{2}), ..., ({x}_{k},{y}_{k}))</math> mit <math>{x}_{i},{y}_{i} \in {A}^{*}. </math> A ist ein beliebiges Alphabet.

Gesucht ist eine (endliche) Indexliste <math>({i}_{1}, {i}_{2}, ..., {i}_{n})</math>, mit <math>{i}_{j} \in I = \{1, 2, ..., k\}</math> und <math>n\geq 1</math>, sodass <math>{x}_{{i}_{1}} \circ {x}_{{i}_{2}} \circ ... \circ {x}_{{i}_{n}} = {y}_{{i}_{1}} \circ {y}_{{i}_{2}} \circ ... \circ {y}_{{i}_{n}}. \circ</math> steht für die
bekannte Verkettungsoperation in <math>{A}^{*}</math>.

Für einfache Beispiele kann man Lösungen durch probieren herstellen.  Aber für große Indexlistes muss man systematisch suchen. Auf dieser Seite soll die Lösung des Problems mittels Breitensuche dargestellt werden. 

Die Tiefensuche eignet sich nicht, da in diesem Fall die Indexliste nur aus unendlich vielen Einsen bestehen würde: <math>(1,1,1,1,...)</math>. Mit der Breitensuche hingegen, werden alle Indexlisten einer Größe gebildet und geprüft, d.h. alle mit Länge 3, dann mit Läünge 4, usw. .

Dazu werden in jedem Iterationsschritt alle Folgeglieder gebildet und an eine "TODO-Liste" angehängt. Diese Liste enthält die gesuchten Indexlisten. Von der "TODO-Liste" wird das erste Element entnommen und auf die Richtigkeit geprüft. Ist die Indexliste korrekt, dann ist die Suche beendet. Andernfalls muss das nächste Element hinzugezogen werden.  

Wenn allerdings keine Lösung existiert, dann terminiert der Algorithmus nicht. Somit ist das POSTsche Korrespondenzproblem nicht entscheidbar. Es ist semi-entscheidbar.


<code id="4dbf0ee65d619" hidden>
(define liste '())
(define todo-list '())

;help procedures  
(define bound
  (lambda ()
    (define todo-list-new '())
     (do ((i 0 (+ i 1))) ((> i (- (length todo-list) 1)))
       (if (not (= 0 (length todo-list))) 
    (if (string-equal? (expand-listA (list-ref todo-list i) "")(expand-listB (list-ref todo-list i) ""))
    (set! todo-list-new (append todo-list-new (list (list-ref todo-list i))))
       #f)
       #f)
)
    (set! todo-list todo-list-new)
    ))
  

(define string-equal? 
 (lambda (s1 s2)
   (if (= 0 (string-length s1))
       #t
       (if (= 0 (string-length s2))
           #t
           ;else
           (if (equal? (string-ref s1 0) (string-ref s2 0))
               (string-equal? (substring s1 1) (substring s2 1))
               #f)))
))

(define list-correct?
  (lambda (res)
    (if (= 0 (length res))
     #f
     (equal? (expand-listA res "")(expand-listB res ""))
    )
))
  
;creates a string from an index-list
(define expand-listA
  (lambda (res in)     
    (if (not (= 0 (length res)))
        (and 
          (set! in (string-append in (car (list-ref liste ( - (car res) 1)))))
          (expand-listA (cdr res) in))
        in 
    )))

(define expand-listB
  (lambda (res in)     
    (if (not (= 0 (length res)))
        (and 
          (set! in (string-append in (cdr (list-ref liste (- (car res) 1)))))
          (expand-listB (cdr res) in))
        in
    )))


</code>

<code id="4dbf0ee65d691">
(define pcp
  (lambda (res)
   
 ; (display  res)
 ; (newline) 
    
    ;remove first element
    (if (not (= 0 (length todo-list))) 
        (set! todo-list (cdr todo-list))
        #f)    
       
    (if (list-correct? res) 
        res;correct result-list 
        (and  ;#f: branch, Breitensuche
        (do ((i 0 (+ i 1))) ((> i (- (length liste) 1)))
           (set! todo-list 
                 (append 
                     todo-list
                    (list (append res (list ( + i 1))))
                 )
           )
          )
        (bound);bound
        (pcp (car todo-list))
        )
        )
    ))
</code>
Zunächst wird die Paarliste gesetzt und dann die Prozedur aufgerufen und mit dem erwarteten Ergebnis verglichen.
<run id="4dbf0ee65d722">
(set! liste  '(("1" . "101")("10" . "00")("011" . "11")))
(equal? 
   (pcp '())   '(1 3 2 3))
</run>

Ein weiteres Beispiel:
<run id="4dbf0ee65d79b">
(set! todo-list '())
(set! liste '(("01" . "0")("110010" . "0")("1" . "1111")("11" . "01"))) 
(equal? 
   (pcp '())
   '(1 3 2 4 4 3))
</run>

Bei dieser Paar-Liste dauert die Suche sehr lang, da die resultierende Indexliste 66 Elementen enthält. Auch mit dem Branch ("Schranke") wo unnötige Zweige nicht weiter verfolgt werden benötigt die Suche eine lange Zeit.
<run id="4dbf0ee65d80c">
;(set! todo-list '())
;(set! liste '(("001" . "0")("01" . "011")("01" . "101")("10" . "001"))) 
;(equal? 
;    (pcp '()) '(2,4,3,4,4,2,1,2,4,3,4,3,4,4,3,4,4,2,1,4,4,2,1,3,4,1,1,3,4,4,4,                 2,1,2,1,1,1,3,4,3,4,1,2,1,4,4,2,1,4,1,1,3,4,1,1,3,1,1,3,1,2,1,4,1,1,3))

</run>