Probabilistische Algorithmen SS10

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2010-05-30T16:42:20+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Einleitung
2 Pseudozufallszahlen
3 Monte-Carlo-Algorithmen
4 Las-Vegas-Algorithmen
5 Ant Colony Optimization

Autoren:

Mateusz Zwierz (simazwie@stud.hs-zigr.de)
Hans Markwart (sihamark@stud.hs-zigr.de)

Einleitung

Pseudozufallszahlen

(define random-maker
 (let* ((multiplier 48271)
        (modulus 2147483647)
        (apply-congruence
         (lambda (current-seed)
           (let ((candidate (modulo (* current-seed multiplier) modulus)))
             (if (zero? candidate)
                 modulus
                 candidate))))
        (coerce
         (lambda (proposed-seed)
           (if (integer? proposed-seed)
               (- modulus (modulo proposed-seed modulus))
               19860617))))  ;; an arbitrarily chosen birthday
 (lambda (initial-seed)
   (let ((seed (coerce initial-seed)))
     (lambda args
       (cond ((null? args)
              (set! seed (apply-congruence seed))
              (/ (- modulus seed) modulus))
             ((null? (cdr args))
              (let* ((proposed-top
                      (ceiling (abs (car args))))
                     (exact-top
                      (if (inexact? proposed-top)
                          (inexact->exact proposed-top)
                          proposed-top))
                     (top
                      (if (zero? exact-top)
                          1
                          exact-top)))
                (set! seed (apply-congruence seed))
                (inexact->exact (floor (* top (/ seed modulus))))))
             ((eq? (cadr args) 'reset)
              (set! seed (coerce (car args))))
             (else
              (display "random: unrecognized message")
              (newline))))))))

(define random
  (let ((seed (time-nanosecond (current-time))))
;    (display seed)
    (random-maker seed)))

(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)   ; stellt current-time usw. bereit

(define random (random-maker (time-nanosecond (current-time))))

(define a 
  (lambda (t el ls)
    (cond
         ((<= t 0) 0)
         ((=(car ls)el) (car ls))
         (else
          (a (- t 1) el (cdr ls))))))



(define search
  (lambda (ns t el ls)
  (cond
    ((= (a  (random t) el ls) 0) 'false)
    ((= (a (random t) el ls) el) 'true)
    (else( search (- ns 1) (random t) el ls)))))

(define ls '(1 2 3 6 6 6))

<eval id="4c02956bc5556"> (search 2 6 1 ls) </eval>

Probabilistische Algorithmen SS10

Inhaltsverzeichnis

Einleitung

Pseudozufallszahlen

Monte-Carlo-Algorithmen

Las-Vegas-Algorithmen

Ant Colony Optimization

Suche