Prenos/port/porting september 7, 2010

Zadnji mesec sem imel kar nekaj opravka s prenosi programov iz ene platforme na drugo (npr. računalnik -> hladilnik). Pri tem se pojavljata dve problematiki:
1. Drugo (razvojno) okolje
2. Druga (slabša) strojna oprema

Zdaj pa par primerov.

Romunski programi za prijavo odlagališč preko mobilnikov
Romuni so v okviru svoje analogije Estonske čistilne akcije razvili par omenjenih programov. Ker telefoni tečejo na zelo pestri osnovni programski in strojni opremi, ni bil dovolj en, ampak so jih naredili kar štiri! Enega za Android, enega za winmobile, enega za Symbian in ostale javance ter enega za robido. Vsi so odprtokodni programi, zato sem hotel preveriti, če bi bili uporabni tudi pri nas.
Ajajaj, kakšne komplikacije! Prvo sem preizkusil različico za Symbian, ker imam slučajno blizu en kompatibilen telefon. Že pri namestitvi je bilo par zapletov, na koncu pa zadeve sploh nisem mogel zagnati, navkljub podpori razvijalca. Njemu seveda vse dela, je pa res, da na točno takem telefonu še ni bilo testov. Winmobile sem takoj odpisal, za Blackberry pa naj bi obstajal dober emulator, a se je izkazalo, da teče le na oknih. Za razliko ima Android zelo prenosen emulator (preko qemu), ki je takoj delal. Vsaj nekaj, bi pa za vzpostavitev razvijalskega okolja potreboval še en kup drugega dela.

Wormux
Tukaj se dogajajo stvari iz drugega zornega kota. Nekdo se je javil za stvaritev prenosa na Maemo (novejše nokie in drugi) in takoj začel z delom. Ker so telefoni švoh, wormux pa požrešen, je šlo večino dela v optimizacijo in izklop raznih bonbončkov. Komunikacija teče dobro, popravki letijo levo in desno in napredek je očiten. Sinergija in skupni know-how delata čudeže.

GemRB
Tu je spet drugače. Že dolgo različni ljudje izdelujejo prenose, ampak se ob težavah redko obračajo na nas. Večina jih je zaradi razvojnega okolja in potrebnih knjižnic, vseeno bi pa lahko dobili več feedback-a, ker sami velike večine teh ekzotov nimamo. Pri dostih napravah so težave tudi z velikostjo zaslona in vnosom, saj ali nimajo ničesar analognega tipkovnici in miški ali pa so te zelo okrnjene (telefoni).
Ekstremen primer je tu ročna konzola Dingoo, kjer je na voljo le kopica gumbov, zaslon je pa manjši kot pri nekaterih telefonih. Da bi se slika sploh prilegala na zaslon, je avtor spremenil izrisovanje, da vedno zmanjša sliko na polovico. Zato tele niso predogledne slike, ampak originali, igranje pa očitna muka! Čisto nasprotje prenosu na ipad, ki ima velik zaslon občutljiv na dotik.
Ampak to ni še dno. Zadnjič je na kanal prišel nekdo, ki je hotel gemrb prenesti na Dreamcast! Ja, le 16M sistemskega pomilnika in praktično nič prostora na disku. Nočna mora, če pomislimo, da se ponavadi prišpara na enem, tako da se uporabi več drugega.

Od zadnjega sporočila je bila izdana nova različica z nekaj manjšo porabo pomnilnika in novim lahkotnim ter okrnjenim vtičnikom za zvok. Odlično za prenosnike. Škoda, da ni med njimi nobenega resnejšega razvijalca, ker bi z optimizacijo izrisovanja (SDL) ali pa novim vtičnikom (prek OpenGL (ES)) lahko dosegli več kot občutne pohitritve. Izrisovanje je ozko grlo na najhitrejših računalnikih, kaj šele na podhranjenih aparatkih. Pa pogon sploh ni tri-dimenzionalen!

Iskanje potencialnih lokacij divjih odlagališč malo drugače februar 12, 2010

Tudi če vas spoznavanje Slovenije iz ptičje perspektive, vohunjenje ali iskanje krogov v žitu ne zanima, je iskanje in popis divjih odlagališč morda za vas. Na vse skupaj lahko gledate kot na umetniško platformo (za t.i. pixel art).

Akcija poteka odlično in v ta namen sem ustvaril naslednjo mozoljasto umetnino.
Prvo sem rezerviral vse potebne kvadrante:

Začel barvanje bistva:

Rezultat (sloj potencialnih lokacij je izključen):

Na voljo so torej omejene dimenzije in le štiri barve, pri čemer modre ne moremo izbrati, ampak se moramo zanašati na obstoječe obarvane kvadrante. Ustvarjalni izziv, a pohitite, platna je vedno manj!

Problem trgovskega potnika – travelling salesman problem februar 8, 2010

V okviru projekta Očistimo Slovenijo v enem dnevu! smo razmišljali tudi o minimizaciji poti terenskih popisovalcev odlagališč. Tako bi bilo delo za njih (in za okolje) ceneje in hitreje. Priti morajo do vseh znanih (potencialnih) lokacij in jih opisati, zato nas zanima v kakšnem vrstnem redu naj jih obiščejo, da bo pot čim krajša? To je problem trgovskega potnika. Zaradi praktične vrednosti in težavnosti je to eden izmed najbolj preučevanih optimizacijskih problemov. Pri manjšem številu točk se da v sprejemljivem času izračunati natančno rešitev, povsod drugod pa pridejo v poštev le približki hevrstičnih metod.

Seveda se nisem takoj zakadil v implementacijo ene od teh metod, ampak sem raje preveril obstoječe prostoprogramske rešitve. Med drugim sem našel petnajst let stari tsp_solve (patch, da se spet prevede), ki je zbirka mnogih algoritmov za reševanje tega problema. Na žalost pa ne podpira vnosa točk preko njihovih koordinat GPS, zato sem iskal naprej. Vse potrebno ima Concorde, ki lahko situacijo tudi nariše.

Vzel sem vse potencialne lokacije divjih odlagališč v Škofljici, saj je bila to prva v celoti pregledana občina. Concorde je izračunal optimalno pot (točk je bilo le 69), potem sem jo pa preveril še enkrat preko wine, da sem dobil tudi sliko – TSP Škofljica. Hitro je postalo jasno, da je nekaj narobe – popisovalec bi moral dvakrat na drugi konec občine! Ista težava je razvidna tudi na hevristični rešitvi za del Ljubljane.

A ta pot je celokupno gledano res najkrajša, le problem je bil slabo definiran. Trgovski potnik lahko namreč obišče vsako točko le enkrat! Toliko matematikov se ukvarja z njim, pa ni nihče pomislil na to?! Precej nepraktično, je pa zato problem lažje rešljiv. Že na pamet lahko pod novimi predpostavkami takoj vidno izboljšamo pot – krajša pot v Škofljici (primerjajte s prejšnjo sliko).

V končni fazi smo idejo zato opustili in tuhtanje prepustili cestnim aparatom GPS. Njihova metoda najbližjih sosedov dostikrat ni optimalna, a bo dala dovolj dober približek. Tako tudi ne bomo nepotrebno obremenjevali Geopedie z računanjem razdalj po cestah in s samo optimizacijo. Računanje preko ravninskih koordinat bi dalo slabe rezultate, saj ne upošteva ovir (vode, železnice, …) in višinskih razlik.

Mogoče sem bom kdaj lotil praktičnega reševanja našega problema, ki ga ob tej priliki krstim za problem pametnega trgovskega potnika.