Repunpakkaus
Kehitä 2-approksimaatioalgoritmi seuraavaan ongelmaan:
Sinulle annetaan repun maksimipaino sekä esinettä, joista :nnellä on paino ja arvo . Valitse joukko esineitä, jotka maksimoivat arvojen summan niin ettei niiden yhteispaino ylitä repun maksimipainoa.
Solmupeite
-
Toteuta lineaarinen ohjelma (painottomaan) solmupeiteongelmaan Pythonin MIP-paketilla.
-
Ohjelma voi tuottaa ratkaisun, jossa osan muuttujista arvo ei ole kokonaisluku. Solmupeitteessä solmut joko sisältyvät peitteeseen (1) tai eivät sisälly (0). Tarkastele mitä käy, jos pyöristät ratkaisun, eli valitset solmupeitteeseen kaikki solmut, joiden arvo on vähintään :
a) Vakuuta itsellesi, että ratkaisu tuottaa solmupeitteen.
b) Kuinka hyvän approksimaation se tuottaa? (Osoita ensin, että lineaariohjelma tuottaa alaraja ja pyöristys ylärajan)
Kauppamatkustajan ongelma
Kehitä 2-approksimaatioalgoritmi seuraavaan ongelmaan:
Sinulle annetaan kaupungin koordinaatit . Etsi lyhin polku, joka käy kaikissa kaupungeissa, kun kahden kaupungin etäisyys määritellään niiden euklidinen etäisyytenä, eli .