Miten muurahainen löytää seuraavan asiakkaan?

Abstract

Tässä työssä tutustutaan graafiteorian Hamiltonin piiriongelmaan sekä kauppamatkustajan ongelmaan. Graafin piiri, joka sisältää graafin jokaisen solmun täsmälleen kerran, on Hamiltonin piiri. Mikäli graafista löytyy Hamiltonin piiri, on graafi Hamiltonin graafi. Hamiltonin piiriongelmaa tarkastellaan ensin teoreettisemmin, tutustuen tapoihin selvittää miten annetun graafin voi todeta Hamiltonin graafiksi. Samalla esitellään kaksi lausetta avuksi ongelmaan ja todistetaan ne.

Toiseksi tutustutaan kauppamatkustajan ongelmaan eli yritetään etsiä painoltaan pienintä mahdollista Hamiltonin piiriä painotetusta graafista. Kauppamatkustajan ongelma on kuuluisa esimerkki laskennallisesti erittäin haastavasta ongelmasta. Kauppamatkustajan ongelman parissa tarkastellaan mitä sen laskennallinen haastavuus tarkoittaa, esitellään sen ratkaisualgoritmien päätyypit ja tutustutaan tarkemmin yhteen muurahaisten innoittamaan reitinetsintäalgoritmiin.

Muurahaisoptimointialgoritmi on luonnossa esiintyvää muurahaisten käyttäytymistä mallintava parviälymenetelmien perheeseen kuuluva reitinetsintäalgoritmi. Muurahaisoptimointialgoritmin ei ole tarkoitus löytää kauppamatkustajan ongelmaan eksaktia ratkaisua, vaan sen tarkoitus on löytää ongelmaan nopeita ja tarpeeksi hyviä vastauksia. Työssä esitellään myös toimiva esimerkkitoteutus muurahaisoptimointialgoritmista.