-fejlesztés alatt: 2006-09-17 -
Alapötlet
A feladat tehát az, hogy a rendőr-áthelyezések közül találjuk meg az egyik legkisebb költségűt. Ha mindet meg szeretnénk vizsgálni az túlságosan sok lehetőség lenne, és nem lenne elég gyors a programunk. Ilyenkor meg lehet próbálkozni egy olyan ötlettel ami lecsökkenti a vizsgálandó lehetőségek számát, pl. azon az alapon, hogy megfogalmaz egy állítást az optimális megoldás szerkezetéről. Így már csak az olyan szerkezetű megoldások halmazán kellene optimumot keresnünk, amik jó állítás esetén sokkal kevesebben vannak.
Az alapötletet Bergmann Gábortól kaptam...
...mely a következő: bizonyítható, hogy létezik olyan optimális (azaz minimális áthelyezési költségű) megoldás, melyben az egy rendőrörsről áthelyezett rendőrök egymás utáni szomszédos városokba fognak kerülni, ráadásul az így kialakuló blokkok azonos sorrendben lesznek, mint az eredeti városok. Pl.:
A négyzetek a városokat szimbolizálják, a színek és a számok a rendőröket jelzik. A felső sor a feladat, az alsó sor egy a feltételeknek megfelelő lehetséges (de éppen nem optimális) áthelyezés
Tehát nem azt állítjuk, hogy minden optimális megoldás feltétlenül így fog kinézni, hanem csak azt, hogy léteznie kell legalább egy így kinéző optimális megoldásnak. Ez elég, így ugyanis csak az ilyen formájú megoldások halmazán kell optimumot keresnünk, ami drasztikusan lecsökkenti a lehetőségek számát. Ráadásul majd a dinamikus programozás elvét is alkalmazni fogjuk tudni.
Bizonyítás (átugorható)
A bizonyítást alapja a következő: veszünk egy tetszlőges rendőr-elrendezést és olyan transzformációkkal, amik nem növelik az összköltséget, olyanná alakítjuk, hogy megfeleljen a feltételeknek: (Ne feledjük, hogy nem azt kell bizonyítani, hogy minden optimális megoldás megfelel a feltételeknek, csak azt, hogy létezik olyan is.)
Első lépésben csak azt bizonyítjuk, hogy az áthelyezett rendőrök sorrenje meg kell, hogy egyezzen az rendőrök eredeti sorrendjével, tehát kiküszöbölhetőek az ilyen felállások:
A módszer nagyon egyszerű, cseréljük fel a helytelen sorrendben kihejezett rendőröket. Így mindkét rendőr áthelyezési költsége ugyanannyival változott, csak akkor lenne baj, ha mindkettő növekedne. Azaz ha mindkét rendőr távolodna a kiindulási városától.
Tehát az össz-felhasznált áthelyezési költség növekedni biztosan nem fog ezzel a cserével. Gondoljuk végig, hogy az egyik kültségváltozás azért lesz biztosan csökkenés, mert nem lehetséges az, hogy a cserével mindkét rendőr egyszerre távolodjon a saját kiindulási városától.
Ezzel beláttuk tehát, hogy található egy olyan optimális megoldás is, melyben a rendőrök elhelyezése ehhez hasonló:
Intuitívan innen már látható, hogy a lenti rendőrök összetologatása még mindig nem növelheti tovább a költségeket. (Egy versenyen ha kevés az idő akkor az ilyen megérzéseket már esetleg el lehet fogadni.) Ezért a bizonyítást a lelkes olvasóra bízzuk...
Megvalósítás
Programunk csak az előző pont legelején kifejtett feltételeknek megfelelő megoldások halmazán fog keresni. A keresés a dinamikus programozás gondolata miatt lesz gyors, de először nézzük az egyszerűbb változatot:
Rekurzív back-track
Az algoritmus sorban veszi azokat a városokat, melyekben van rendőr. Minden ilyen városhoz egy akkora folytonos rendőr-blokk fog tartozni, ahány rendőr van benne. Ezt megpróbáljuk minden lehetséges helyen elhelyezni az autópályán. Minden lehetséges elhelyezésre vesszük a következő város rendőr-blokkját, és azt is megpróbáljuk ugyanígy elhelyezni, de már csak az előző blokktól jobbra elhelyezkedő részben, mert bizonyítottuk, hogy fennáll a sorrendiség. És így tovább, rekurzívan végignézünk minden lehetséges elhelyezést, feljegyezzük a legkisebb áthelyezési költségűt, és az lesz az optimális megoldás.
folyt. köv
Megoldások
