/* pts_mihazi.java -- A* algoritmus implementáció * * This is a text-based JDK1.1 application. * The language of the program and the source is Hungarian. * See EOF for revision history. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * */ import java.util.Hashtable; /* Graf */ import java.util.Vector; /* Graf */ import java.util.Enumeration; /* Graf */ public class pts_mihazi { /** Olyan Object-ekből álló adatstruktúra, amelynek mindkét végére hozzá * lehet fűzni és mindkét végéről lehet törölni. Veremként így használatos: * jobbHozzaad(o), jobbTorol(). Sorként: jobbHozzaad(o), balTorol(). * Imp: összemérni egy duplán láncolt listával * Imp: kevesebb ures,bal,jobb randa trükk */ static public class SorVerem { protected int MIN_MERET=16; /** l.length >= MIN_MERET */ protected Object[] t; /** true iff a sor üres. Ekkor persze bal==0 és jobb==t.length-1 */ protected boolean ures; /** a bal oldali, tartalmazott elem indexe. Nem feltétlenül kisebb-egyenlő * a jobb-nál */ protected int bal; protected int jobb; /** @return hány eleme van (this)-nek */ protected int getHossz() { return ures ? 0 : bal<=jobb ? 1+jobb-bal : 1+t.length+jobb-bal; } /** @param delta 0 vagy 1 */ protected void atmeretez(int delta) { int ujmeret=t.length; int n=getHossz()+delta; if (ujmeret/4>=n) ujmeret=n*2; else if (ujmeret<n) ujmeret=n*2; if (ujmeret<MIN_MERET) ujmeret=MIN_MERET; // System.out.println("# "+t.length+" ->"+ujmeret+" "+n); n-=delta; if (ujmeret!=t.length) { Object[] uj_t=new Object[ujmeret]; if (ures) { if (bal!=0) throw new RuntimeException("! bal=0"); if (jobb!=t.length-1) throw new RuntimeException("! jobb==t.length-1"); } else if (bal<=jobb) { // System.out.println("% "+bal+" "+(1+jobb-bal)+" "+t.length+" "+uj_t.length); System.arraycopy(t, bal, uj_t, 0, 1+jobb-bal); bal=0; jobb=n-1; } else { System.arraycopy(t, bal, uj_t, 0, t.length-bal); System.arraycopy(t, 0, uj_t, t.length-bal, jobb+1); bal=0; jobb=n-1; } /* Imp: t-t kinull-ozni */ t=uj_t; } } /** @return null, ha üres, egyébként bal oldalt töröl 1-et és azt adja */ public Object balTorol() { if (ures) return null; Object torolt=t[bal]; if (bal++==jobb) { /* kiürült */ bal=0; jobb=t.length-1; ures=true; } else { if (bal==t.length) bal=0; } atmeretez(0); /* Imp: csak ha muszáj */ return torolt; } /** @return null, ha üres, egyébként jobb oldalt töröl 1-et és azt adja */ public Object jobbTorol() { if (ures) return null; Object torolt=t[jobb]; if (bal==jobb--) { /* kiürült */ bal=0; jobb=t.length-1; ures=true; } else { if (jobb==-1) jobb=t.length-1; } atmeretez(0); /* Imp: csak ha muszáj */ return torolt; } public void jobbHozzaad(Object uj) { atmeretez(1); /* Imp: csak ha muszáj */ ures=false; if (++jobb==t.length) jobb=0; // if (jobb==bal) throw new RuntimeException("! jobb!=bal"); t[jobb]=uj; } public void balHozzaad(Object uj) { atmeretez(1); ures=false; bal=(bal==0)?t.length-1:bal-1; // if (jobb==bal) throw new RuntimeException("! jobb!=bal"); t[bal]=uj; } public SorVerem() { t=new Object[MIN_MERET]; bal=0; jobb=t.length-1; ures=true; } public static class Teszt { public static void teszt() { /* // minding a kiíró sor után mutatja a várt eredményt */ SorVerem sv=new SorVerem(); for (int i=0;i<40;i++) sv.jobbHozzaad(new Integer(i)); System.out.println(sv.getHossz()); //40// Integer j; while ((j=(Integer)sv.balTorol())!=null) System.out.print(j+" "); System.out.println(""); //0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39// System.out.println(sv.getHossz()); //0// for (int i=20;i<40;i++) sv.jobbHozzaad(new Integer(i)); for (int i=19;i>=0;i--) sv.balHozzaad(new Integer(i)); while ((j=(Integer)sv.balTorol())!=null) System.out.print(j+" "); System.out.println(""); //0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39// System.out.println(sv.getHossz()); //0// for (int i=0;i<40;i++) sv.balHozzaad(new Integer(i)); while ((j=(Integer)sv.balTorol())!=null) { System.out.print(j+" "); if ((j=(Integer)sv.jobbTorol())==null) break; System.out.print(j+" "); } System.out.println(""); /* vvv Dat: melleseleg +1-gyel épp ez a Fregatt nyomtatási sorrend */ //39 0 38 1 37 2 36 3 35 4 34 5 33 6 32 7 31 8 30 9 29 10 28 11 27 12 26 13 25 14 24 15 23 16 22 17 21 18 20 19// } } } /** Comparable-hez hasonló, de az JDK 1.1-ben nem működik */ interface Hasonlito { /** -1, ha a kisebb b-nél, 1, ha a nagyobb, 0 különben */ int hasonlit(Object a, Object b); } /** Kupac-ból (és egyéb adatszerkezetekből) való, tömeges törlésre * használt függvény. */ interface Torlo { boolean toroljem_e(Object kit, Object adat); } /** Általános célú, összehasonlítható objektumokat tartalmazó (bináris) * kupac adatszerkezet, a fa gyökerében a legkisebb elem áll. Algel könyv * 2.2.5-től annyiban tér el, hogy 0-tól számozza az elemeket, és t-ben * n-nél több helyet is fenntartunk a későbbi beszúrások számára. */ static public class Kupac { protected int MIN_MERET=16; /** t.length nem mindig kettőhatvány */ protected Object[] t; /** t első n elemét használjuk csak, a többi null */ protected int n; protected Hasonlito h; protected void atmeretez(int delta) { int ujmeret=t.length; int h=n+delta; if (ujmeret/4>=h) ujmeret=h*2; else if (ujmeret<h) ujmeret=h*2; if (ujmeret<MIN_MERET) ujmeret=MIN_MERET; if (ujmeret!=t.length) { Object[] uj_t=new Object[ujmeret]; // if (ujmeret<n) throw new IllegalStateException(); if (t.length<n) throw new IllegalStateException(); System.arraycopy(t, 0, uj_t, 0, n); /* Imp: t-t kinull-ozni */ t=uj_t; } } /** @return hány elem van a kupacban */ protected int getHossz() { return n; } /** Igazából leszivarog()-nak kéne hívni, de tartjuk magunkat az * Algel könyv, 2.2.5 elnevezéséhez. */ protected void felszivarog(int idx) { /* Az előző algoritmus rossz volt, mert n-t nem figyelte */ int bal, jobb, min; Object ez; while (true) { bal=idx*2+1; jobb=idx*2+2; ez=t[idx]; min=(bal<n && h.hasonlit(t[bal],ez)<0) ? bal : idx; if (jobb<n && h.hasonlit(t[jobb],t[min])<0) min=jobb; if (min==idx) break; t[idx]=t[min]; t[min]=ez; idx=min; } } protected void gyokerfele(int idx) { Object tmp; int apja_idx; while (idx!=0 && h.hasonlit(tmp=t[idx], t[apja_idx=(idx-1)>>1])<0) { t[idx]=t[apja_idx]; t[apja_idx]=tmp; idx=apja_idx; } } /** null vagy a minimális elem */ public Object getLegkisebb() { return t[0]; } /** @return üres kupac esetén null, különben pedig törli és visszaadja az * egyik legkisebb elemet. */ public Object mintor() { if (n==0) return null; Object legkisebb=t[0]; if (--n==0) { t[0]=null; return legkisebb; } /* gyorsítás */ t[0]=t[n]; t[n]=null; /* drop reference */ if (t.length>MIN_MERET && t.length/4>=n) atmeretez(0); felszivarog(0); return legkisebb; } public void beszur(Object ujelem) { if (t.length==n) atmeretez(1); t[n]=ujelem; gyokerfele(n++); } /** Ez egy picit használhatatlan, hiszen a hívónak ismernie kell az elem * pozícióját, amit sehol sem kötöttünk az ő orrára. * @return régi érték */ public Object set(int idx, Object uj) { if (idx<0 || idx>=n) throw new ArrayIndexOutOfBoundsException(); Object regi=t[idx]; t[idx]=uj; int cmp=h.hasonlit(uj, regi); if (cmp<0) gyokerfele(idx); /* fogyaszt */ else if (cmp>0) felszivarog(idx); /* növel */ return regi; } /** Növekvő sorrendben adja vissza a kupac elemeit és egyúttal kiüríti * a kupacot. Ez egy kupacrendezés: (new Kupac(h, tomb)).novtor(). */ public Object[] novtor() { /* Azért nem a mintor()-t hívjuk, hogy megússzuk az atmeretez()-t */ int oldn=n; Object[] tomb=new Object[n]; for (int i=0;i<oldn;i++) { tomb[i]=t[0]; t[0]=t[--n]; t[n]=null; /* drop reference */ felszivarog(0); } // for (int i=oldn;i>=0;i--) t[n]=null; /* ref felejtés */ n=0; atmeretez(0); return tomb; } /** Törli a kupacból az összes, Torlo által kijelölt elemet. * @param adat továbbadja Torlo#toroljem_e-nek */ public void torol(Torlo torlo, Object adat) { for (int i=0;i<n;) { if (torlo.toroljem_e(t[i], adat)) { t[i]=t[--n]; t[n]=null; /* drop reference */ felszivarog(0); } else i++; } atmeretez(0); } /** Csak a kupacot másolja, a tartalmát referenciálisan. */ public Kupac masol() { return new Kupac(h, t, n); } /** Üres kupacot épít. */ public Kupac(Hasonlito h) { this.h=h; t=new Object[MIN_MERET]; n=0; } /** kuapcépítés(): a megadott elemekből kupacot épít. * Imp: java.util.Enumenrable */ public Kupac(Hasonlito h, Object elemek[], int elemhossz) { this.h=h; t=new Object[Math.max(MIN_MERET,n=elemhossz)]; System.arraycopy(elemek, 0, t, 0, n); for (int i=n-1;i>=0;i--) felszivarog(i); } public Kupac(Hasonlito h, Object elemek[]) { this(h,elemek,elemek.length); } /** Not thread-safe. */ public static class Teszt { public static class EgeszHasonlito implements Hasonlito { /** Sajnos nem lehet static-ként, mert az Osztály java-ban nem * elsőrendű típus. (Osztályok nem öröklődhetnek például.) */ public int hasonlit(Object a, Object b) { int aa=((Integer)a).intValue(); int bb=((Integer)b).intValue(); return aa<bb ? -1 : aa>bb ? 1 : 0; } } public static void teszt() { /* // minding a kiíró sor után mutatja a várt eredményt */ Kupac k=new Kupac(new EgeszHasonlito()); for (int i=0;i<40;i++) k.beszur(new Integer(i)); System.out.println(k.getHossz()); //40// Integer j; while ((j=(Integer)k.mintor())!=null) System.out.print(j+" "); System.out.println(""); //0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39// System.out.println(k.getHossz()); //0// for (int i=20;i<40;i++) k.beszur(new Integer(i)); for (int i=19;i>=0;i--) k.beszur(new Integer(i)); // k.beszur(new Integer(4)); k.beszur(new Integer(4)); k.beszur(new Integer(4)); while ((j=(Integer)k.mintor())!=null) System.out.print(j+" "); System.out.println(""); //0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39// System.out.println(k.getHossz()); //0// for (int i=1;i<6;i++) k.beszur(new Integer(i)); // k.mintor(); k.beszur(new Integer(4)); while ((j=(Integer)k.mintor())!=null) System.out.print(j+" "); System.out.println(""); while ((j=(Integer)k.mintor())!=null) { System.out.print(j+"("+k.getHossz()+")"+" "); int i=j.intValue(); if (i!=1 && i%2==1) k.beszur(new Integer(3*i+1)); if (i%2==0) k.beszur(new Integer(i/2)); } System.out.println(""); //1(4) 2(3) 1(3) 3(2) 4(2) 2(2) 1(2) 5(1) 10(1) 5(1) 16(1) 8(1) 4(1) 2(1) 1(1) 16(0) 8(0) 4(0) 2(0) 1(0)// } } } /* --- Általános-Keresés implementációja, MI könyv 3.4 alapján --- */ /** Az állapottér egy állapota. Ezt kell problémafüggően kell * felüldefiniálni, ebbe van besuvasztva a probléma legtöbb komponense: * (operátorok: kifejt(), cél-teszt: celTeszt(), út-költség-függvény: * kifejt()). Ami hiányzik, az a kiinduló-állapot. Ezt külön meg kell majd * adni altalanosKereses()-nek. * <P>Hagyomány, hogy a leszármazottak konstruktorai a kezdőállapotot * adják vissza. */ static public abstract class Allapot { /** @return -1, 0, 1 */ public int ahasonlit(Allapot masik) { return 0; } /** !! Minimális csomóponti f érték, amit valaha is elértünk ebben az * állapotban. */ protected double minf=Double.MAX_VALUE; /** @return true iff ténylegesen csökkentettük */ public boolean minfCsokkent(double ertek) { // System.out.println("mcs="+this); if (ertek<minf) { minf=ertek; return true; } else return false; // minf=Math.min(minf, ertek); } public double getMinf() { return minf; } /** Az innen valamely célállapotig vezető legrövidebb út alulról * becsült költségét számolja ki. Nem célállapotra pozitív, célállapotra * nulla. Fontos, * hogy a tényleges útköltségnél ne legyen nagyobb (ez az ún. megengedett * hash függvény). A monotonitásnak (háromszög-egyenlőtlenségnek) nem kell * teljesülnie. * Ha a keresés nem informált, akkor nem kell felüldefiniálni ezt a * metódust, ami így nullát ad vissza végállapotra, 1-et nem végállapotra. */ public double calcH() { return celTeszt() ? 0.0d : 1.0d; } /** Ez valósítja meg az operátorokat és a célfüggvényt. Kifejti (this)-t, * mint újdonsült szülőállapotot. Megengedhető, hogy a visszaadott tömbben * null-ok szerepeljenek (ekkor arrafelé nincs csomópont). Többszöri * meghívásnál lehet ugyanazt a tömbref-et visszaadni. * @param cs (this)-t tároló csomópont */ abstract public Csomopont[] kifejt(Csomopont cs); /** @return true iff (this) végállapot */ abstract public boolean celTeszt(); } /** A keresési tér egy csomópontja. Ez nem egy okos osztály, nem is szabad * felüldefiniálni. */ static public final class Csomopont { protected Allapot allapot; /** null, ha ő a kiinduló állapot _és_ kiinduló csomópont is egyben */ protected Csomopont szulo; /** Problema#kifejt állítja be tetszőleges, implementációfüggő értékre. * Azt jellemzi, hogy ő mely operator-ral jött létre szulo-bol. * szulo==null esetén értéke -1, egyébként tetszőleges (akár -1 is lehet) */ protected int operator; /** A kezdőállapotból idáig vezető út tényleges költsége. */ protected double g; /** Az innen valamely célállapotig vezető legrövidebb út alulról * becsült költsége. Nem célállapotra pozitív, célállapotra nulla. Fontos, * hogy a tényleges útköltségnél ne legyen nagyobb (ez az ún. megengedett * hash függvény). A monotonitásnak (háromszög-egyenlőtlenségnek) nem kell * teljesülnie. */ protected double h; /** min(szulo.f, g+h) */ protected double f; public double getF() { return f; } public double getG() { return g; } public double getH() { return h; } public Allapot getAllapot() { return allapot; } public Csomopont getSzulo() { return szulo; } /** Visszaad egy tömböt, amely a keresési fában a kezdőcsúcs és (this) * közötti keresési csúcsokat tartalmazza a kifejtés sorrendjében. Az utat a * Csomopont#szulo mutatókat követve térképezi fel. * @return a lista nulladik csúcsa a kezdőállapot, az utolsó csúcsa pedig * (this).allapot. A köztes csúcsok a kifejtés sorrendjében állnak. * @see Csomopont#szulo * Imp: operátorokat is felgöngyölíteni */ public Allapot[] allapotFelgongyolit() { int n=0; for (Csomopont cs=this; cs!=null; cs=cs.szulo) n++; Allapot[] t=new Allapot[n]; Csomopont cs=this; while (cs!=null) { t[--n]=cs.getAllapot(); cs=cs.szulo; } return t; } /** STDERR-re */ public static void megoldasKiir(Csomopont talaltCel) { if (talaltCel!=null) { Allapot[] t=talaltCel.allapotFelgongyolit(); System.err.println("A megoldás hossza "+t.length+", költsége "+talaltCel.g); for (int i=0;i<t.length;i++) System.err.println(t[i]); } else System.err.println("Nincs megoldás."); } /** @return true iff a gyökértől (this)-ig ki szerepel */ boolean szerepel(Csomopont ki) { for (Csomopont cs=this; cs!=null; cs=cs.szulo) if (cs.allapot==ki.allapot) return true; return false; } /** @return true iff a gyökértől (this)-ig (this) >= 2-szer szerepel */ boolean ismetlodik() { return szulo!=null && szulo.szerepel(this); } public Csomopont(Allapot allapot, Csomopont szulo, int operator, double utkoltseg) { this.h=allapot.calcH(); /* NullPointerException-t dobjuk korán */ this.allapot=allapot; if ((this.szulo=szulo)==null) { this.operator=-1; this.g=0; this.f=this.h; } else { this.operator=operator; this.g=szulo.g+utkoltseg; this.f=Math.max(szulo.f, this.g+this.h); } } public String toString() { return "((Csomopont f="+f+" g="+g+" h="+h+" op="+operator+ " áll="+allapot+"))"; } public String toStringKifejtjuk() { return allapot+","+(int)f; } public String toStringKifejtetlen() { return allapot+":"+(int)f; } } /** A keresés során még kifejtetlen csomópontok listája. Egyben a keresési * stratégiát is reprezentálja (a sorbaállító függvénybe rejtve). */ interface KeresesiStrategia { /** @return null, ha üres, különben törli és visszaadja az első elemet */ Csomopont elsoTorol(); void sorbaAllit(Csomopont cs); /** Módosítja, felülvizsgálja a kifejtést. Például null-áz néhány ágat, ha * úgy észleli, hogy azt már valahol máshol kifejtettük. Legtöbbször csak * visszaadja a paramétert változatlanul. */ Csomopont[] felulvizsgal(Csomopont[] lista); String toStringKifejtetlen(); } /** MI könyv, 3.4 alapján * @param csomopontok kezdetben üres, az algoritmus munketerületként használja * @return (Csak akkor garantált, hogy visszatér (lefut), ha a keresési * stratégia teljes. Csak akkor garantált, hogy az eredmény optimális, ha * a keresési stratégia optimális.) null, ha a keresés sikertelen; egyébként * az egyik megtalált cél-csúcsot adja vissza. Ebből a keresési út * rekonstruálható Csomopont#allapotFelgongyolit() segítségével. * @see Csomopont#allapotFelgongyolit() segítségével */ static Csomopont altalanosKereses(Allapot kiinduloAllapot, KeresesiStrategia csomopontok) { kiinduloAllapot.minfCsokkent(0); csomopontok.sorbaAllit(new Csomopont(kiinduloAllapot, null, -1, 0.0d)); Csomopont kit; while ((kit=csomopontok.elsoTorol())!=null) { // System.out.print("kifejt="); System.out.println(kit); System.out.print(kit.toStringKifejtjuk()); if (kit.getAllapot().celTeszt()) { System.out.println(";"); return kit; } System.out.println(":"); Csomopont[] kifejtes=csomopontok.felulvizsgal(kit.getAllapot().kifejt(kit)); // problema.kifejt(kit); for (int i=0;i<kifejtes.length;i++) if (kifejtes[i]!=null) { // vvv Dat: nem működik Kirako8-ra, mert mindenkit újragenerálunk // (sose lesz kifejtve==true) // vvv Dat: .kifejtve tesztje elrontja az optimalitást! Csak akkor // lenne szabad letiltani a kifejtést, ha a régebben kifejtett // csomópont kisebb f (vagy g) értékű. // vvv ?? szabad .kifejtve?? // if (true) { // if (!kifejtes[i].getAllapot().kifejtve) { // if (!kifejtes[i].ismetlodik()) { // -- KeresesiStrategia része lett csomopontok.sorbaAllit(kifejtes[i]); // kifejtes[i].getAllapot().kifejtve=true; // !! } System.out.print(csomopontok.toStringKifejtetlen()+";\n\n"); } return null; /* sikertelen keresés */ } /* --- néhány keresési stratégia --- */ /** sorbaAllit() a sor végére teszi az új elemet */ static public class SzelessegiKereses implements KeresesiStrategia { SorVerem sv=new SorVerem(); public Csomopont elsoTorol() { return (Csomopont)sv.balTorol(); } public void sorbaAllit(Csomopont cs) { System.out.println(cs); sv.jobbHozzaad(cs); } public Csomopont[] felulvizsgal(Csomopont[] lista) { return lista; } public String toStringKifejtetlen() { return "???"; } } /** sorbaAllit() g szerint növekvően helyez el, elsoTorol a legkisebbet * g-jűt veszi ki. */ static public class EgyenletesKoltseguKereses implements KeresesiStrategia, Hasonlito { public int hasonlit(Object a, Object b) { double aa=((Csomopont)a).getG(); double bb=((Csomopont)b).getG(); return aa<bb ? -1 : aa>bb ? 1 : 0; } protected Kupac kupac; public EgyenletesKoltseguKereses() { kupac=new Kupac(this); } public Csomopont elsoTorol() { return (Csomopont)kupac.mintor(); } public void sorbaAllit(Csomopont cs) { kupac.beszur(cs); } public Csomopont[] felulvizsgal(Csomopont[] lista) { return lista; } public String toStringKifejtetlen() { return "???"; } } /** sorbaAllit() a sor elejére teszi az új elemet */ static public class MelysegiKereses extends SorVerem implements KeresesiStrategia { public Csomopont elsoTorol() { return (Csomopont)balTorol(); } public void sorbaAllit(Csomopont cs) { balHozzaad(cs); } public Csomopont[] felulvizsgal(Csomopont[] lista) { return lista; } public String toStringKifejtetlen() { return "???"; } } /* Kimarad: mélységkorlátozott keresés */ /* Kimarad: iteratívan mélyülő keresés */ /* Kimarad: kétirányú keresés */ /* Kimarad: kényszerkielégítéses keresés */ /* Kimarad: legjobbat-először keresés (ez technikailag azonos a mohó kereséssel) */ /** sorbaAllit() Csomopont#getH() növekvő sorrendjében rendez, * elsoTorol() a legkisebbet adja vissza. */ static public class MohoKereses implements KeresesiStrategia, Hasonlito { public int hasonlit(Object a, Object b) { double aa=((Csomopont)a).getH(); double bb=((Csomopont)b).getH(); return aa<bb ? -1 : aa>bb ? 1 : 0; } protected Kupac kupac; public MohoKereses() { kupac=new Kupac(this); } public Csomopont elsoTorol() { return (Csomopont)kupac.mintor(); } public void sorbaAllit(Csomopont cs) { kupac.beszur(cs); } public Csomopont[] felulvizsgal(Csomopont[] lista) { return lista; } public String toStringKifejtetlen() { return "???"; } } /** sorbaAllit() Csomopont#getF() növekvő sorrendjében rendez, * elsoTorol() a legkisebbet adja vissza. * Imp: ne legyen crossref, refc tudjon működni */ static public class ACsillagKereses implements KeresesiStrategia, Hasonlito { public int hasonlit(Object a, Object b) { Csomopont acs=(Csomopont)a, bcs=(Csomopont)b; double aa=acs.getF(); double bb=bcs.getF(); return aa<bb ? -1 : aa>bb ? 1 : acs.getAllapot().ahasonlit(bcs.getAllapot()); } protected Kupac kupac; public ACsillagKereses() { kupac=new Kupac(this); } public Csomopont elsoTorol() { return (Csomopont)kupac.mintor(); } public void sorbaAllit(Csomopont cs) { // ?? milyen sorrendben kell kiírni // System.out.print("sorbaAllit="); System.out.println(cs); kupac.beszur(cs); } public Csomopont[] felulvizsgal(Csomopont[] lista) { return lista; } public String toStringKifejtetlen() { Object[] rendezett=kupac.masol().novtor(); StringBuffer sb=new StringBuffer(); for (int i=0;i<rendezett.length;i++) { if (i!=0) sb.append(","); sb.append(((Csomopont)rendezett[i]).toStringKifejtetlen()); } return sb.toString(); } } /** sorbaAllit() Csomopont#getF() növekvő sorrendjében rendez, * elsoTorol() a legkisebbet adja vissza, elkerüli a gyökér felé vezető * csomópontismétlődést. * Imp: ne legyen crossref, refc tudjon működni */ static public class ACsillagGyokerKereses extends ACsillagKereses { public Csomopont[] felulvizsgal(Csomopont[] lista) { for (int i=lista.length-1;i>=0;i--) { if (lista[i]!=null && lista[i].ismetlodik()) lista[i]=null; } return lista; } } /** sorbaAllit() Csomopont#getF() növekvő sorrendjében rendez, * elsoTorol() a legkisebbet adja vissza, elkerüli az összes ismétlődést. * Tadeusz így kérte: az open listából töröljük azokat a (kifejtetlen) * csúcsokat, melyek valamely őse (esetleg saját maguk) az épp kifejtett * csúcs egy magasabb f-jű értékét hordozzák */ static public class ACsillagTorloKereses extends ACsillagKereses implements Torlo { /** Torlo implementációja: töröljük, ha jobb helyen már láttuk. Pontosan * akkor kéri csomopont törlését, ha ősei közt (őt magát is beleértve) van * olyan csomópont, melynek állapota megegyezi allapot-tal és f() értéke * nagyobb allapot.getMinf()-nél. */ public boolean toroljem_e(Object csomopont_, Object allapot_) { Allapot allapot=(Allapot)allapot_; for (Csomopont cs=(Csomopont)csomopont_;cs!=null;cs=cs.getSzulo()) { if (cs.getAllapot()==allapot && allapot.getMinf()<cs.getF()) return true; } return false; } public Csomopont[] felulvizsgal(Csomopont[] lista) { Allapot allapot; for (int i=lista.length-1;i>=0;i--) { if (lista[i]==null) continue; allapot=lista[i].getAllapot(); if (allapot.minfCsokkent(lista[i].getF())) { kupac.torol(this, allapot); } else { lista[i]=null; /* Ugyanezt az állapotot már jobb helyen láttuk. */ } } return lista; } } /* --- néhány konkrét probléma */ /** MI könyv 4.2 eleje */ public static class Kirako8 extends Allapot { /* Imp: H1 lapka-célhely távolság összege */ /* Imp: H2 háztömbtávolság-összeg */ public static final int BAL_OP=0, JOBB_OP=1, FEL_OP=2, LE_OP=3; /** 9 elemű tömb, balról jobbra. 0: üres, 1--8: elemek */ protected byte[] t; /** az üres mező indexe */ protected int u; static protected Csomopont folyt[]=new Csomopont[4]; /** Kiinduló állapot. */ public Kirako8() { t=new byte[] { 5, 4, 0, 6, 1, 8, 7, 3, 2 }; u=2; } /** Új állapotot hoz létre: az üres helyet elozo.cs-vel megcseréli */ protected Kirako8(Kirako8 elozo, int cs) { if (elozo.t[elozo.u]!=0) throw new RuntimeException(); t=new byte[9]; System.arraycopy(elozo.t, 0, t, 0, 9); t[elozo.u]=t[cs]; t[u=cs]=0; } public Csomopont[] kifejt(Csomopont szulo) { folyt[BAL_OP]=(u%3==0) ? null: new Csomopont(new Kirako8(this, u-1), szulo, BAL_OP, 1); folyt[JOBB_OP]=(u%3==2) ? null: new Csomopont(new Kirako8(this, u+1), szulo, JOBB_OP, 1); folyt[FEL_OP]=(u<3) ? null: new Csomopont(new Kirako8(this, u-3), szulo, FEL_OP, 1); folyt[LE_OP]=(u>=6) ? null: new Csomopont(new Kirako8(this, u+3), szulo, LE_OP, 1); return folyt; } public boolean celTeszt() { // return t[0]==1 && t[1]==2 && t[2]==3 // && t[3]==8 && t[4]==0 && t[5]==4 // && t[6]==7 && t[7]==6 && t[8]==5; return t[0]==6 && t[1]==5 && t[2]==4 && t[3]==7 && t[4]==1 && t[5]==0 && t[6]==3 && t[7]==2 && t[8]==8; // return t[0]==5 && t[1]==0 && t[2]==4 // && t[3]==6 && t[4]==5 && t[5]==8 // && t[6]==7 && t[7]==3 && t[8]==2; } /** ki hova szeretne kerülni */ static final int cel[]={ 4, 0, 1, 2, 5, 8, 7, 6, 3 }; public double calcHx() { /* Háztömb-heurisztika */ int a, b, r=0; if (true) return 0; for (int i=0;i<9;i++) { a=cel[b=t[i]]; r+=Math.abs((a-b)%3)+Math.abs(a/3-b/3); } return r; } public String toString() { return "\n["+t[0]+" "+t[1]+" "+t[2]+"\n"+ " "+t[3]+" "+t[4]+" "+t[5]+"\n"+ " "+t[6]+" "+t[7]+" "+t[8]+"]"; } } /* Keresési probléma: városok */ public static class Graf { public static class Csucs extends Allapot { protected String nev; /** földrajzi szélesség és magasság */ protected double szelesseg, hosszusag; protected int i; /** A célcsúcstól mért légvonalbeli távolsága, setCelCsucs számolja ki */ protected double h; protected Vector el=new Vector(); protected Vector elsuly=new Vector(); public double calcH() { return h; } public boolean celTeszt() { return h==0.0d; } public Csomopont[] kifejt(Csomopont szulo) { Csomopont[] folyt=new Csomopont[el.size()]; for (int i=el.size()-1;i>=0;i--) { folyt[i]=new Csomopont((Csucs)el.elementAt(i), szulo, 0, ((Double)elsuly.elementAt(i)).doubleValue()); } return folyt; } public String toString() { return nev; } /** Csak úgy, simán nem hozható létre. */ protected Csucs() {} public int ahasonlit(Allapot masik) { // return nev < ((Csucs)masik).nev ? -1 : // (nev == ((Csucs)masik).nev ? 0 : 1); return nev.compareTo(((Csucs)masik).nev); } } protected Hashtable h2i=new Hashtable(); protected int n=0; /* csúcsok száma */ protected Csucs cel; public void ujCsucs(String nev, double szelesseg, double hosszusag) { /* Dat: uses String#equals */ if (h2i.containsKey(nev)) throw new IllegalArgumentException(); Csucs cs=new Csucs(); cs.nev=nev; cs.szelesseg=szelesseg; cs.hosszusag=hosszusag; cs.i=n++; h2i.put(nev, cs); } /** Nem ellenőrzi a többszörös éleket. */ public void elBehuz (String honnan, String hova, double tavolsag) { Csucs honnan_=(Csucs)h2i.get(honnan), hova_=(Csucs)h2i.get(hova); if (honnan_==null) throw new IllegalArgumentException(); if (hova_==null) throw new IllegalArgumentException(); Double tavolsag_=new Double(tavolsag); honnan_.el.addElement(hova_); honnan_.elsuly.addElement(tavolsag_); hova_.el.addElement(honnan_); hova_.elsuly.addElement(tavolsag_); } public Csucs getCsucs(String nev) { Csucs cs=(Csucs)h2i.get(nev); if (cs==null) throw new IllegalArgumentException(); return cs; } /** Csak ujCsucs() és elBehuz() hívások után */ public void setCelCsucs(String cel_n) { cel=getCsucs(cel_n); for (Enumeration en=h2i.elements();en.hasMoreElements();) { Csucs cs=(Csucs)en.nextElement(); // ?? double dx=(cel.szelesseg-cs.szelesseg)*100; double dy=(cel.hosszusag-cs.hosszusag)*45; cs.h=(double)Math.round(Math.sqrt(dx*dx+dy*dy)); } } } /* --- az Application main függvénye --- */ public static void main(String args[]) { final String nev="Szabó Péter"; final String neptun_kod="MVBYN6"; final String start_varos="Smolensk"; final String cel_varos="Astrakhan"; final String evszak="Ősz"; // System.out.println(-7%5); // -2 // SorVerem.Teszt.teszt(); // Kupac.Teszt.teszt(); // Csomopont.megoldasKiir(altalanosKereses(new Kirako8(), new ACsillagKereses())); System.out.println(nev); System.out.println(neptun_kod); System.out.println(start_varos); System.out.println(cel_varos); // tél =1 , tavasz = 2, nyár =3 , ősz = 4 System.out.println(evszak=="Tél"?1:evszak=="Tavasz"?2:evszak=="Nyár"?3:4); System.out.println(""); Graf og=evszak=="Tél"?(Graf)new TeliGraf():(Graf)new OsziGraf(); // Imp: más évszakok gráfjai og.setCelCsucs(cel_varos); // System.exit(args.length); /* 0 alapból */ KeresesiStrategia strategia= (args.length==1) ? new ACsillagKereses() : /* buta */ (args.length==2) ? new ACsillagGyokerKereses() : /* tűrhető */ (KeresesiStrategia)new ACsillagTorloKereses(); /* okos, kötelező */ Csomopont.megoldasKiir(altalanosKereses(og.getCsucs(start_varos), strategia)); /* A megoldás hossza 8, költsége 1907.0 Smolensk Moscow Ryazan Lipetsk Tambov Borisoglebsk Volgograd Astrakhan */ } /* Keresési probléma: Oroszország városai, ősszel */ static class OsziGraf extends Graf { public OsziGraf() { /* Őszi adatok */ ujCsucs("Archangelsk", 64.567, 40.533); ujCsucs("Astrakhan", 46.349, 48.049); ujCsucs("Belgorod", 50.613, 36.587); ujCsucs("Borisoglebsk", 51.369, 42.091); ujCsucs("Brest", 52.1, 23.7); ujCsucs("Chelyabinsk", 55.167, 61.4); ujCsucs("Dnipropetrovsk", 48.45, 34.983); ujCsucs("Donetsk", 48, 37.8); ujCsucs("Elista", 46.308, 44.256); ujCsucs("Gomel", 52.433, 31); ujCsucs("Groznyy", 43.307, 45.701); ujCsucs("Kaliningrad", 54.71, 20.5); ujCsucs("Kharkov", 50, 36.25); ujCsucs("Kiev", 50.433, 30.517); ujCsucs("Kirov", 58.597, 49.658); ujCsucs("Kirovograd", 48.504, 32.263); ujCsucs("Krasnodar", 45.033, 38.977); ujCsucs("Kropotkin", 45.435, 40.579); ujCsucs("Kursk", 51.73, 36.194); ujCsucs("Lipetsk", 52.619, 39.569); ujCsucs("Lugansk", 48.567, 39.333); ujCsucs("Minsk", 53.9, 27.583); ujCsucs("Moscow", 55.75, 37.583); ujCsucs("Murmansk", 68.967, 33.083); ujCsucs("Naberezhnyye Chelny", 55.7, 52.317); ujCsucs("Nalchik", 43.498, 43.619); ujCsucs("Nizhni Novgorod", 56.333, 44); ujCsucs("Novgorod", 58.517, 31.283); ujCsucs("Orenburg", 51.783, 55.05); ujCsucs("Pensa", 53.196, 45); ujCsucs("Perm", 58, 56.25); ujCsucs("Petrozavodsk", 61.817, 34.333); ujCsucs("Poltava", 49.583, 34.567); ujCsucs("Riga", 56.95, 24.1); ujCsucs("Rostov-na-Donu", 47.236, 39.714); ujCsucs("Ryazan", 54.62, 39.74); ujCsucs("Saint Petersburg", 59.894, 30.264); ujCsucs("Samara", 53.2, 50.15); ujCsucs("Saransk", 54.183, 45.183); ujCsucs("Saratov", 51.567, 46.033); ujCsucs("Segezha", 63.733, 34.317); ujCsucs("Smolensk", 54.782, 32.04); ujCsucs("Stavropol", 45.037, 41.97); ujCsucs("Tallin", 59.434, 24.728); ujCsucs("Tambov", 52.732, 41.434); ujCsucs("Tver", 56.867, 35.917); ujCsucs("Vilnius", 54.683, 25.317); ujCsucs("Vitebsk", 55, 29.5); ujCsucs("Volgograd", 48.805, 44.586); ujCsucs("Vologda", 59.217, 39.9); ujCsucs("Voronezh", 51.666, 39.17); ujCsucs("Yekaterinburg", 56.85, 60.6); elBehuz("Archangelsk" , "Petrozavodsk" , 1015); elBehuz("Archangelsk" , "Vologda" , 795); elBehuz("Astrakhan" , "Groznyy" , 734); elBehuz("Belgorod" , "Kharkov" , 80); elBehuz("Borisoglebsk" , "Volgograd" , 367); elBehuz("Brest" , "Minsk" , 340); elBehuz("Chelyabinsk" , "Orenburg" , 785); elBehuz("Chelyabinsk" , "Yekaterinburg" , 200); elBehuz("Dnipropetrovsk" , "Donetsk" , 270); elBehuz("Donetsk" , "Lugansk" , 160); elBehuz("Donetsk" , "Rostov-na-Donu" , 205); elBehuz("Elista" , "Astrakhan" , 353); elBehuz("Elista" , "Stavropol" , 302); elBehuz("Gomel" , "Kiev" , 255); elBehuz("Gomel" , "Brest" , 599); elBehuz("Gomel" , "Minsk" , 290); elBehuz("Kharkov" , "Poltava" , 140); elBehuz("Kharkov" , "Dnipropetrovsk" , 225); elBehuz("Kharkov" , "Donetsk" , 329); elBehuz("Kharkov" , "Lugansk" , 335); elBehuz("Kiev" , "Poltava" , 372); elBehuz("Kiev" , "Kirovograd" , 315); elBehuz("Kirov" , "Perm" , 648); elBehuz("Kirovograd" , "Dnipropetrovsk" , 290); elBehuz("Kropotkin" , "Krasnodar" , 135); elBehuz("Kursk" , "Voronezh" , 228); elBehuz("Kursk" , "Belgorod" , 150); elBehuz("Kursk" , "Kiev" , 545); elBehuz("Kursk" , "Gomel" , 555); elBehuz("Lipetsk" , "Tambov" , 135); elBehuz("Lipetsk" , "Voronezh" , 130); elBehuz("Lugansk" , "Rostov-na-Donu" , 259); elBehuz("Moscow" , "Tver" , 188); elBehuz("Moscow" , "Nizhni Novgorod" , 425); elBehuz("Moscow" , "Ryazan" , 195); elBehuz("Moscow" , "Kursk" , 599); elBehuz("Moscow" , "Gomel" , 655); elBehuz("Moscow" , "Smolensk" , 395); elBehuz("Murmansk" , "Segezha" , 675); elBehuz("Naberezhnyye Chelny" , "Chelyabinsk" , 868); elBehuz("Naberezhnyye Chelny" , "Perm" , 510); elBehuz("Nalchik" , "Stavropol" , 495); elBehuz("Nalchik" , "Groznyy" , 205); elBehuz("Nizhni Novgorod" , "Ryazan" , 430); elBehuz("Nizhni Novgorod" , "Saransk" , 318); elBehuz("Nizhni Novgorod" , "Samara" , 780); elBehuz("Nizhni Novgorod" , "Naberezhnyye Chelny" , 625); elBehuz("Nizhni Novgorod" , "Kirov" , 670); elBehuz("Novgorod" , "Riga" , 520); elBehuz("Novgorod" , "Tver" , 404); elBehuz("Pensa" , "Tambov" , 280); elBehuz("Pensa" , "Saratov" , 220); elBehuz("Perm" , "Yekaterinburg" , 335); elBehuz("Petrozavodsk" , "Saint Petersburg" , 450); elBehuz("Petrozavodsk" , "Novgorod" , 572); elBehuz("Poltava" , "Kirovograd" , 240); elBehuz("Poltava" , "Dnipropetrovsk" , 180); elBehuz("Riga" , "Vitebsk" , 515); elBehuz("Riga" , "Vilnius" , 285); elBehuz("Riga" , "Kaliningrad" , 417); elBehuz("Rostov-na-Donu" , "Kropotkin" , 220); elBehuz("Rostov-na-Donu" , "Krasnodar" , 299); elBehuz("Ryazan" , "Lipetsk" , 260); elBehuz("Saint Petersburg" , "Tallin" , 370); elBehuz("Saint Petersburg" , "Novgorod" , 180); elBehuz("Samara" , "Pensa" , 477); elBehuz("Samara" , "Naberezhnyye Chelny" , 585); elBehuz("Samara" , "Chelyabinsk" , 870); elBehuz("Samara" , "Orenburg" , 435); elBehuz("Samara" , "Saratov" , 500); elBehuz("Saransk" , "Pensa" , 150); elBehuz("Saratov" , "Borisoglebsk" , 290); elBehuz("Saratov" , "Volgograd" , 390); elBehuz("Segezha" , "Archangelsk" , 945); elBehuz("Segezha" , "Petrozavodsk" , 299); elBehuz("Smolensk" , "Vitebsk" , 149); elBehuz("Tallin" , "Riga" , 362); elBehuz("Tambov" , "Borisoglebsk" , 160); elBehuz("Vilnius" , "Kaliningrad" , 325); elBehuz("Vilnius" , "Minsk" , 185); elBehuz("Vilnius" , "Brest" , 415); elBehuz("Vitebsk" , "Minsk" , 275); elBehuz("Volgograd" , "Lugansk" , 470); elBehuz("Volgograd" , "Rostov-na-Donu" , 490); elBehuz("Volgograd" , "Elista" , 305); elBehuz("Volgograd" , "Astrakhan" , 395); elBehuz("Vologda" , "Saint Petersburg" , 675); elBehuz("Vologda" , "Novgorod" , 886); elBehuz("Vologda" , "Moscow" , 445); elBehuz("Voronezh" , "Tambov" , 252); elBehuz("Voronezh" , "Borisoglebsk" , 245); elBehuz("Voronezh" , "Belgorod" , 265); } } static class TeliGraf extends Graf { public TeliGraf() { /* Téli adatok */ ujCsucs("Archangelsk", 64.567, 40.533); ujCsucs("Astrakhan", 46.349, 48.049); ujCsucs("Belgorod", 50.613, 36.587); ujCsucs("Borisoglebsk", 51.369, 42.091); ujCsucs("Brest", 52.1, 23.7); ujCsucs("Chelyabinsk", 55.167, 61.4); ujCsucs("Dnipropetrovsk", 48.45, 34.983); ujCsucs("Donetsk", 48, 37.8); ujCsucs("Elista", 46.308, 44.256); ujCsucs("Gomel", 52.433, 31); ujCsucs("Groznyy", 43.307, 45.701); ujCsucs("Kaliningrad", 54.71, 20.5); ujCsucs("Kharkov", 50, 36.25); ujCsucs("Kiev", 50.433, 30.517); ujCsucs("Kirov", 58.597, 49.658); ujCsucs("Kirovograd", 48.504, 32.263); ujCsucs("Krasnodar", 45.033, 38.977); ujCsucs("Kropotkin", 45.435, 40.579); ujCsucs("Kursk", 51.73, 36.194); ujCsucs("Lipetsk", 52.619, 39.569); ujCsucs("Lugansk", 48.567, 39.333); ujCsucs("Minsk", 53.9, 27.583); ujCsucs("Moscow", 55.75, 37.583); ujCsucs("Murmansk", 68.967, 33.083); ujCsucs("Naberezhnyye Chelny", 55.7, 52.317); ujCsucs("Nalchik", 43.498, 43.619); ujCsucs("Nizhni Novgorod", 56.333, 44); ujCsucs("Novgorod", 58.517, 31.283); ujCsucs("Orenburg", 51.783, 55.05); ujCsucs("Pensa", 53.196, 45); ujCsucs("Perm", 58, 56.25); ujCsucs("Petrozavodsk", 61.817, 34.333); ujCsucs("Poltava", 49.583, 34.567); ujCsucs("Riga", 56.95, 24.1); ujCsucs("Rostov-na-Donu", 47.236, 39.714); ujCsucs("Ryazan", 54.62, 39.74); ujCsucs("Saint Petersburg", 59.894, 30.264); ujCsucs("Samara", 53.2, 50.15); ujCsucs("Saransk", 54.183, 45.183); ujCsucs("Saratov", 51.567, 46.033); ujCsucs("Segezha", 63.733, 34.317); ujCsucs("Smolensk", 54.782, 32.04); ujCsucs("Stavropol", 45.037, 41.97); ujCsucs("Tallin", 59.434, 24.728); ujCsucs("Tambov", 52.732, 41.434); ujCsucs("Tver", 56.867, 35.917); ujCsucs("Vilnius", 54.683, 25.317); ujCsucs("Vitebsk", 55, 29.5); ujCsucs("Volgograd", 48.805, 44.586); ujCsucs("Vologda", 59.217, 39.9); ujCsucs("Voronezh", 51.666, 39.17); ujCsucs("Yekaterinburg", 56.85, 60.6); elBehuz("Archangelsk","Petrozavodsk", 1015); elBehuz("Archangelsk","Vologda", 795); elBehuz("Astrakhan","Groznyy", 650); elBehuz("Belgorod","Kharkov", 80); elBehuz("Borisoglebsk","Volgograd", 350); elBehuz("Brest","Minsk", 391); elBehuz("Chelyabinsk","Orenburg", 871); elBehuz("Chelyabinsk","Yekaterinburg", 200); elBehuz("Dnipropetrovsk","Donetsk", 270); elBehuz("Donetsk","Lugansk", 160); elBehuz("Donetsk","Rostov-na-Donu", 205); elBehuz("Elista","Astrakhan", 305); elBehuz("Elista","Stavropol", 275); elBehuz("Gomel","Kiev", 255); elBehuz("Gomel","Brest", 535); elBehuz("Gomel","Minsk", 307); elBehuz("Kharkov","Poltava", 154); elBehuz("Kharkov","Dnipropetrovsk", 240); elBehuz("Kharkov","Donetsk", 305); elBehuz("Kharkov","Lugansk", 335); elBehuz("Kiev","Poltava", 330); elBehuz("Kiev","Kirovograd", 315); elBehuz("Kirov","Perm", 545); elBehuz("Kirovograd","Dnipropetrovsk", 290); elBehuz("Kropotkin","Krasnodar", 135); elBehuz("Kursk","Voronezh", 210); elBehuz("Kursk","Belgorod", 150); elBehuz("Kursk","Kiev", 505); elBehuz("Kursk","Gomel", 555); elBehuz("Lipetsk","Tambov", 149); elBehuz("Lipetsk","Voronezh", 130); elBehuz("Lugansk","Rostov-na-Donu", 240); elBehuz("Moscow","Tver", 170); elBehuz("Moscow","Nizhni Novgorod", 425); elBehuz("Moscow","Ryazan", 232); elBehuz("Moscow","Kursk", 545); elBehuz("Moscow","Gomel", 655); elBehuz("Moscow","Smolensk", 395); elBehuz("Murmansk","Segezha", 675); elBehuz("Naberezhnyye Chelny","Chelyabinsk", 730); elBehuz("Naberezhnyye Chelny","Perm", 510); elBehuz("Nalchik","Stavropol", 495); elBehuz("Nalchik","Groznyy", 205); elBehuz("Nizhni Novgorod","Ryazan", 430); elBehuz("Nizhni Novgorod","Saransk", 295); elBehuz("Nizhni Novgorod","Samara", 881); elBehuz("Nizhni Novgorod","Naberezhnyye Chelny", 625); elBehuz("Nizhni Novgorod","Kirov", 670); elBehuz("Novgorod","Riga", 572); elBehuz("Novgorod","Tver", 355); elBehuz("Pensa","Tambov", 296); elBehuz("Pensa","Saratov", 231); elBehuz("Perm","Yekaterinburg", 361); elBehuz("Petrozavodsk","Saint Petersburg", 450); elBehuz("Petrozavodsk","Novgorod", 520); elBehuz("Poltava","Kirovograd", 240); elBehuz("Poltava","Dnipropetrovsk", 192); elBehuz("Riga","Vitebsk", 515); elBehuz("Riga","Vilnius", 285); elBehuz("Riga","Kaliningrad", 390); elBehuz("Rostov-na-Donu","Kropotkin", 246); elBehuz("Rostov-na-Donu","Krasnodar", 275); elBehuz("Ryazan","Lipetsk", 283); elBehuz("Saint Petersburg","Tallin", 436); elBehuz("Saint Petersburg","Novgorod", 180); elBehuz("Samara","Pensa", 430); elBehuz("Samara","Naberezhnyye Chelny", 585); elBehuz("Samara","Chelyabinsk", 991); elBehuz("Samara","Orenburg", 435); elBehuz("Samara","Saratov", 500); elBehuz("Saransk","Pensa", 150); elBehuz("Saratov","Borisoglebsk", 316); elBehuz("Saratov","Volgograd", 460); elBehuz("Segezha","Archangelsk", 1058); elBehuz("Segezha","Petrozavodsk", 260); elBehuz("Smolensk","Vitebsk", 130); elBehuz("Tallin","Riga", 305); elBehuz("Tambov","Borisoglebsk", 160); elBehuz("Vilnius","Kaliningrad", 360); elBehuz("Vilnius","Minsk", 212); elBehuz("Vilnius","Brest", 493); elBehuz("Vitebsk","Minsk", 275); elBehuz("Volgograd","Lugansk", 470); elBehuz("Volgograd","Rostov-na-Donu", 490); elBehuz("Volgograd","Elista", 305); elBehuz("Volgograd","Astrakhan", 470); elBehuz("Vologda","Saint Petersburg", 722); elBehuz("Vologda","Novgorod", 745); elBehuz("Vologda","Moscow", 476); elBehuz("Voronezh","Tambov", 240); elBehuz("Voronezh","Borisoglebsk", 225); elBehuz("Voronezh","Belgorod", 265); } } } /* Revision history (CHANGES, ChangeLog): * * v0.1 Mon Nov 5 21:13:41 CET 2001 * pre-szkeleton verzió. Lefordul, de nem próbáltam futtatni. LIFO és FIFO * implementáció hiányzik, keresési stratégiák nincsenek implementálva. * * v0.2 Tue Nov 6 22:01:06 CET 2001 * városok etc. * * v0.3 Thu Nov 8 23:09:47 CET 2001 -- Fri Nov 9 00:34:29 CET 2001 * ACsillagGyoker, ACsillagTorloKereses, STDOUT Tadeusz akarata szerint * * v0.4 Mon Dec 3 13:00:23 CET 2001 * Allapot#ahasonlit, évszak máshogy kiír */