Faculty of Informatics Vienna University of Technology Institute of Computer Aided Automation PRIP Home PRIP Home
Personal tools
You are here: Home Teaching Informatikpraktika Traveling Salesperson Problem mittels Pyramiden

Traveling Salesperson Problem mittels Pyramiden

Status des Praktikums: vergeben
Betreuer: Yll Haxhimusa

Problemstellung

Aufgabe das TSP Problems ist das Finden des kuerzesten Pfades (minimale Laenge) durch alle Knoten eines gegebenen gewichteten Graphen. Das Problem ist als NP-vollstaendig bekannt. In letzer Zeit wurden Pyramidenalgorithmen benutzt um mentale Problemloesungsmechanismen zu modellieren. Solche Mechanismen koennten an der visuellen Loesung des TSP beteiligt, sowie an der Loesung anderer visueller Probleme [1,2]. Menschen scheinen die Cluster von Knoten zusammenzufassen, das Problem auf einem vereinfachten Graphen zu loesen und den gesuchten Pfad durch Verfeinerung "top-down" zu suchen. Es ist klar, dass das Resultat nur eine Approximation darstellt, in vielen Faellen aber eine sehr gute, deren Pfadlaenge nahe der optimalen Loesung liegt. Die den mentalen Processen entsprechenden Algorithmen haben eine niedrige Rechenkomplexitaet (i.e. linear). Pyramidmodelle koennten die erste glaubhafte Erklaerungen von Phenomenen des menschlichen Denken erlauben ('directedness of thought and reasoning'). Pyramidenalgorithmen werden auch als adaequate Modelle fuer die Gestaltregeln in der Wahrnehmung (perceptual organization) gesehen, wie z.B die Nachbarschaft, die gute Fortsetzung etc. Objekte der visuellen Wahrnehmung erscheinen dem Menschen in einer grossen Bandbreite an Groessen, mit vielen Details, wenn das Objekt nahe ist und mit sehr wenig Details in der Entfernung, wo der visuelle Kontext fuer die Erkennung wichtig ist. Pyramiden unterstuetzen zwei grundsaetzlich gegensaetzliche Verarbeitungsweisen, die den den Uebergang von hoher und niedriger Aufloesung bewaeltigen: bottom-up (fine to coarse) sowie top-down (coarse to fine). Der top-down Ansatz ist oft entscheidend fuer die effiziente Loesung des Segmentierungsproblems.

Literatur

  1. Z. Pizlo and Z. Li. Pyramid algorithms as models of human cognition. Proc. of SPIE IST Electronic Imaging, Computational Imaging, 5016, 1-12, 2003.
  2. Z. Pizlo and Z. Li. Graph Pyramids as models of human problem solving. Proc. of SPIE IST Electronic Imaging, Computational Imaging, 5299, 205-215, 2004.
  3. W.G. Kropatsch. Building Irregular Pyramids by Dual Graph Contraction. IEE-Proc. Vision, Image and Signal Processing, V.142,366-374, 1995.
    Also as technical report.

Zielsetzung

Irregulaere Graphenpyramiden [3] als Modelle fuer die 'human problem solving'.

Gliederung

  • Einarbeitung.
  • C/C++ Implementation mit bereits bestehende Software Z. Li and Z.Pizlo (C) der Purdue University und Software von PRIP, mit aktivem Gedankenaustausch mit den Forschungsaktivitaeten an der Purdue University.
  • Performance Test.

Sonstiges

Fuer dieses Praktikum besteht auch die Moeglichkeit eine Diplomarbeit anzuschliessen.