Aus ProgrammingWiki

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 mit A ist ein beliebiges Alphabet.

Gesucht ist eine (endliche) Indexliste , mit und , sodass steht für die bekannte Verkettungsoperation in .

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: . 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.

(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 )))

(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)) ) ) ))

Zunächst wird die Paarliste gesetzt und dann die Prozedur aufgerufen und mit dem erwarteten Ergebnis verglichen.

(set! liste '(("1" . "101")("10" . "00")("011" . "11"))) (equal? (pcp '()) '(1 3 2 3))

ausführen

Ein weiteres Beispiel:

(set! todo-list '()) (set! liste '(("01" . "0")("110010" . "0")("1" . "1111")("11" . "01"))) (equal? (pcp '()) '(1 3 2 4 4 3))

ausführen

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.

;(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))

ausführen