abonnement Unibet Coolblue Bitvavo
pi_33398343
Ik studeer Econometrie, afstudeerrichting Operations Research. Ben op dit moment bezig met mijn afstudeeronderzoek en heb daarvoor een drietal heuristieken ontwikkeld, reeds geimplementeerd in C++ en geevalueerd.

Het probleem is dat ik precies weet hoe deze in elkaar steken maar niet weet hoe ik dit correct in wiskundige notatie neer moet zetten (ten behoeve van mijn scriptie). Gezien het aantal theoretische wiskunde colleges dat ik gehad én gehaald heb is dat behoorlijk schandalig , maar ik vrees dat ik er zonder hulp kom niet uit kom.

Eén van de heuristieken is een modificatie op een andere heuristiek genaamd GKS, Greedy Karp-Steele Patching. GKS is een heuristiek voor het handelsreizigersprobleem (TSP) - het vinden van de kortste hamiltonian cycle die alle vertices van de graaf omvat (NP-hard). GKS lost eerst het assignment probleem (AP) op; het AP is het probleem van het vinden van een minimal bipartite matching (niet NP-hard). Beschouw je deze oplossing in de TSP-context, dan heb je een onbestemd aantal hamiltonian cycles; zie bijvoorbeeld onderstaand plaatje:



Deze individuele cycles kun je door hulp van een "patching operation" aan elkaar plakken: als je namelijk uit cycle 1 arc (p,q) en uit cycle 2 arc (r,s) verwijderd en vervolgens arcs (p,s) en (r,q) aan de oplossing toevoegd, worden cycle 1 en cycle 2 tot één gemaakt. GKS bekijkt iteratief alle mogelijke patching operations en voert steeds de goedkoopste uit, totdat alle cycles tot één verworden zijn.

Op dit moment heb ik het zó staan, en ja ik weet dat enkele dingen (wiskundige) onzin zijn Oh ja, er staat ook nog een typfoutje in stap 2 maar heb geen zin om het gif-je te veranderen


TeX versie: klik hier

CM is de kostenmatrix; CM(i,j) zijn de kosten voor het 'gaan' van vertex i naar vertex j. PC bevat de patchingcosts gerelateerd aan het verwijderen van twee arcs (p,q) en (r,s), en LPC(i,j) is een 'pointer' naar de index van PC (en dus twee arcs) die voor cycles i en j de goedkoopste patching operation oplevert. Bij stap 6 worden de kosten van alle mogelijke patching operations met betrekking de twee nieuwe arcs (p,s) en (r,q) berekend en opgeslagen.

Mijn implementatie is uitgebreider en vele malen efficienter dan hierboven staat, maar dat maakt het voor buitenstaanders alleen maar onbegrijpelijker en als dit eenmaal goed genoteerd is kan ik daaruit de rest wel afleiden.

Alvast bedankt! Suggesties met betrekking tot de leesbaarheid zijn uiteraard net zo hard welkom!
  Moderator zondag 25 december 2005 @ 18:59:19 #2
72712 crew  Rene
Dabadee dabadaa
pi_33398611
[Centraal] Bèta 'huiswerk en vragen topic'
Ik denk, ik help je eventjes een handje, die uitgebreide OP enzo
 | ❤ | Triquester... | ツ Met een accént aigu
abonnement Unibet Coolblue Bitvavo
Forum Opties
Forumhop:
Hop naar:
(afkorting, bv 'KLB')