/* 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
*/