"Általános" algoritmusok

Üdv!

gsimon megoldása lehet, hogy nem lesz jó, mert max 500 pont lehet a gráfban, és ha a te módszeredet követjük, akkor 25000x25000-es gráfot kellene tárolni, ami nem fér bele a 64MB-ba.. Vagy esetleg kapcsolati lánccal ábrázoljuk a gráfot?

Petya

[quote:b50fc79256="kl223"]hm. igaz, megpróbálom azzal.
Fero: nem rossz. Bár ahogy nézem, ez lényegében a "sok kivonás"-os módszer azzal a finomítással, hogy itt az osztó folyamatosan nő. (gondolom ezzel is csökkentve a műveletszámot.)
Már ha jól értelmezem a kódot... ;)

thx a válaszokat.

kl223

Pontosan. Bar ez a finomitas egy problemaosztalyt csokkent rajta ;). O(2^n) -> O(n^a), ha jol sejtem a=2, bar nincs erom levezetni.

Egy kollégám javasolt egy egyszerűbb módszert:

Egyszerűen megfordítjuk az összes élet (vagyis transzponáljuk a szomszédsági mátrixot), és így keresünk két utat egy adott pontba. Tehát mindkét pontból indítunk egy szélességi keresést, és ha mindkettő megtalálja a megadott célpontot, akkor megnézzük, hogy a két útban van-e közös pont. Ha nincs, akkor kész vagyunk, de ha van... na akkor nem tudom mit kellene csinálni...

Szerinted ez így jó lehet? És mit csináljunk, ha van a két útban közös pont?

Petya

[quote:ee3d74b9b1="kl223"]Azt szeretném kérdezni, hogy ismer-e vki a neten alapvető (pl. kereső, _útkereső_, rendező, egyéb) algoritmusokat leírva?

Gondolom továbbra is ezzel kívánsz foglalkozni, így előnyösebb venni egy könyvet, pl. Új algoritmusok címűt (Cormen,. Leiserson., Rivest, Stein szerzőkkel).

jahm, az uj Cormen konyv ("Uj algoritmusok") elegge reszletes a temaban, de a regi valtozatat is erdemes forgatni. Az etlen gaz az ara, kb. 10 rugo, vagy kicsit kevesebb. En megvettem, de biztos megvan ebookban is.

[quote:a56b2dbcf4="_Petya_"]...akkor megnézzük, hogy a két útban van-e közös pont. Ha nincs, akkor kész vagyunk, de ha van... na akkor nem tudom mit kellene csinálni...
Szerinted ez így jó lehet? És mit csináljunk, ha van a két útban közös pont?

Hát igen, ezen az úton én is eddig jutottam. Ha van egy közös pont, akkor onnantól a két út a célpontig együtt fut (mert a minimális út tetszőleges szakasza minimális), azaz valami Y-szerű elrendezést kapunk, ahol a két szár végén a kiinduló pontok vannak, a közepén az összefutási pont, az alján meg a cél. Törpöltem valami olyasmin, hogy feloldandó a problémát, az egyik utat "el kéne terelni" az Y száráról még az összefutási pont előtt, de ez egyenértékű lenne azzal, hogy a másik utat minimálisra választjuk, majd kiszedjük a gráfból, és a maradékon keressük a másik utat, de ennek helytelen voltát azt hiszem már ellenpéldával beláttuk.
A gond ott van, hogy a két útkeresés egymást erősen befolyásolja, függenek egymás eredményeitől, így nem lehet őket szétválasztani. Legalábbis én nem látok rá módot.

Az eredeti 500 pontos gráfban 40k él van, azaz elég ritkán vannak az élek (mármint az 500!-hoz képest), az átlagos ki-fok 40k/500=80, tehát a 250000 pontúban a ki-fok kb. 6400 lenne, azaz (ha el nem néztem, akkor) valami vacak 16 millió él lenne, mindegyikre kiindulási- és végpont plusz költség, négy byte-ban ez nem férne el még él-listás tárolással sem. Esetleg azzal lehetne operálni, hogy a G'-t amúgy is algoritmikusan generáltuk, így a tényleges generálás nélkül is meg tudjuk mondani, hogy mely pontjából mely pontjába milyen költséggel megy az él. Legfeljebb nem tömb-elemként kapjuk mint g_vesszo[i][j], hanem függvényként mint g_vesszo(m1,m2, n1,n2), így aztán abszolute nem is kell tárolni. Mondjuk a függvény-kiértékelés meg cpu-időt eszik, de ez két tömbelem-olvasás meg jó esetben egy összeadás, úgyhogy lehet, hogy ki lehet bírni. Valami ilyenre gondoltam:
[code:1:ae0bec9ccd]
int g_vesszo(int m1, int m2, int n1, int n2)
{
if ((g[m1][n1] <= 0) || /* nincs el m1-bol n1-be */
(g[m2][n2] <= 0)) return -1; /* nincs el m2-bol n2-be */
return g[m1][n1] + g[m2][n2];
}
[/code:1:ae0bec9ccd]
Azt meg, hogy egy G'-beli MN pontból hová megy él, szintén pusztán G ismeretében sorolhatjuk:
[code:1:ae0bec9ccd]
/* ... */
/* m es n az aktualis G'-beli pontot alkoto ket G-beli pont indexe */
for (i = 0; i < G_PONT_SZAM; i++)
for (j = 0; j < G_PONT_SZAM; j++)
{
if (((i != m) || (j != n)) &&
(i != j) &&
((m == i) || (g[m][i] > 0)) &&
((n == j) || (g[n][j] > 0))) megnezni(i, j);
}
/* ... */
[/code:1:ae0bec9ccd]

Nos, van valakinek ötlete?

Petya

Van valami Pollackos Mesterséges Inteligencia jegyzetem html-ben. Köszönet érte Achs tanárnőnek :)
Nem túl magasröpptű, átfogó leiras, szívesen elküldöm...
Ha jól emlekszem keresőalgoritmusok, gráfkeresés stb-ről van benne szó.

az "ien", "iet", "iesmit" szavakat hanyadik osztalyban (es foleg milyen idegen nyelvi oran) tanultatok?

Vagy tudod mit?
Itt megtalalod:
ftp://witch.pmmf.hu:2001/Szamitastechnika_Tanszek/achs/mestint/mijegyzet/cimlap.htm
Nezz bele, aztan majd eldontod :-)

Udv!

bocs, azt hittem komoly. a linuxforum nem tudom micsoda.

[quote:a6e7208e37="kl223"]Hali!

Minden olyan algoritmus érdekelne, ami mondjuk egy sztechversenyen előferdülhet (gimnázium).

kösz!
kl223

Ezt szerintem pont jó lesz:
http://www.panem.hu/a_konyv.php?konyv=170&PHPSESSID=0226d0ac6dcb287771d31a893edee0b6

kl223:
ha tenyleg erdekel a tema es eleg mazo
vagy vedd ki a konyvtarbol Knuth:
A szamitogepprogramozas muveszete II-t.
udv, ncs

Ajánlani tudom a "Bibliát"! :-) Donald E Knuth: The Art of Computer Programming

[quote:4632f744a2="nosy"]kl223:
ha tenyleg erdekel a tema es eleg mazo
vagy vedd ki a konyvtarbol Knuth:
A szamitogepprogramozas muveszete II-t.
udv, ncs

Esetleg tudnám még javasolni az "Algoritmusok" ill. "Szgépes Alg." könyveket, magyar szerzők (túlnyomórészt ELTE ill. BME). Talán most tart a 3. átdolgozott kiadásnál.

Éppen egy ilyen témájú honlapon dolgozom a volt tanárommal. Kicsit lightosabb mint az említett könyvek,
a címe: http://bdgprog.no-ip.org

Gábor

Ott vann fentebb. Használd a bc-t. Első lépésben konvertáld a 256-os alapú számodat valami egyszerű eszközzel 16-osba (ez azért nem hiszem, hogy túl nehéz lenne), majd az eredményt add oda a bc-nek (hint: obase=X ibase=Y kimeneti számrendszer X, bemeneti számrendszer Y)

[quote:de6382adb1="kl223"]Hi!

Egy apró problémám lenne: írok egy kisebb toolt bármekkora, bármilyen számrendszerbeli számok kezelésére.
Szükségem lenne egy gyors algoritmusra a maradékos osztáshoz!
...
kl223

En egy hasonlo problemat igy oldottam meg:
folyamatosan duplazom az osztot amig kisebb, mint az osztando, kivonom, majd mehet az egesz az uj szammal elorol.
[code:1:de6382adb1]
while (o <= x) {
z = o;
do
y = z;
while ((z = y + y) < x);
x -= y;
}
[/code:1:de6382adb1]
ez altalaban eleg gyors, gondolom a bc-vel nem veszi fel a versenyt, de legalabb "tiszta", es eleg keves muveletet hasznal. Ha van gyors osztas, akkor az elso iteracio utan indulhatsz visszafele is.

Köszönöm a segítséget!

Szerinted azt hogy érdemes lekódolni, hogy a G' gráf pontjai két gráfontnak felelnek meg? Mert én 1...500 számokkal jelölöm a pontokat, és így ha az első pont sorszámát megszorzom 500-al, és hozzáadom a második számot, akkor ez jónak tűnik, csak az lenne a kérdésem, hogy van ennél hatékonyabb módszer?

Petya

Na, találtam egy algoritmust, amihez nem kell a pontpárok halmazát képezni, bár picit összetettebb lesz. Akit nem érdekel, attól előre is bocs.
Szóval, az utak megfordítása jó ötlet, legyen tehát a feladat az, hogy a B és C pontból kell diszjunkt utakon eljutni A-ba minimális összköltséggel.

Először keressük meg a minimális B-A és C-A utakat. Ha ezek csak A-ban találkoznak, akkor kész vagyunk :). Ha nem, akkor az első közös pontjukat nevezzük Q1-nek:
[code:1:906b1f3e12]
B--...---Q1---...---C
|
Q2
|

...
|
A
[/code:1:906b1f3e12]
(Kiegészítés: Q1-től A-ig ugyanazon Q2, Q3, ..., Qn=A pontokon futnak az utak, mert Q1-be mindkettő elért, onnan pedig ennél rövidebb út A-ba nincs, ha ui. lenne, akkor egyik út sem lenne minimális)

Lemma: A keresett két út közül pontosan az egyik el fog menni Q1-be.
Biz.: A keresett két út közül ugyanis ha az egyik nem érintené a Q1..Qn-1 pontok egyikét sem, akkor a másik nyugodtan mehetne a Q1..Qn-1 vonalon (ami minimális), így az érintené Q1-et. Tehát az legalább az egyik út érinti valamelyik Qj-t. Viszont ebbe a Qj-be a legrövidebb út a Q1..Qj-1 pontokon át vezet (mert Q1..A minimális), ha tehát a Q pontok közül először Qj-t érinti, azt azért teszi, mert valamely Qi: i<j pontot a másik út már lefoglalt. Ezt iterálva azt kapjuk, hogy a Q pontok 'teteje' (lehet, hogy csak a Q1) az egyik úthoz tartozik, azaz az egyik keresett út érinti Q1-et. Mindkettő a diszjunktság miatt nem érintheti, tehát csak pontosan az egyik fogja.

Legyen most ez a C-ből induló út: tehát a végeredményben C-ből A-ba menő út érinti Q1-et, és teszi ezt az eredeti minimális C-Q1-A út C-Q1 részén, mert minimális út minden része minimális. Ekkor már csak a B-A és Q1-A diszjunkt és minimális összköltségű utakat kell megkeresni.
Ehhez vegyük ki szépen a gráfból a fenti C-Q1 utat, mert arra már nem lesz szükség, valamint az összes Q1-be befutó élt, mert Q1-be a másik úttal amúgy sem szabad eljutni.
Innen ismerős az ábra: egész precízen ugyanaz, mint a kiindulási helyzet, csak most B és C helyett B és Q1-ből kell A-ba diszjunkt utakat találni. Csak éppen a Q1 "közelebb van", mint a C, és ráadásul a Q1-A minimális utat sem kell keresni, mert tudjuk, hogy ez a Q1-Q2-Qn-1-A út lesz.
Ha ebben a maradék gráfban előről kezdjük a nótát, akkor a B-A legrövidebb út valamely Q2..Qn=A pontban érinti a fenti utat, stb., csak épp a közös szakasz hossza szigorúan monoton csökken, azaz legfeljebb n lépésben elfogy, azaz az algoritmus garantáltan célt ér.

A költségigényét számolja ki valaki nálam szorgalmasabb :), a durva lépés az egészben az, hogy az elején (B,C-Q1-A) vajon a B-Q1 vagy a C-Q1 fog megmaradni, mert ha ez a kettes szorzó minden rekurzív lépésben megmarad, akkor a lépésidő közel exponenciális lesz. Ha ezt valahogy frappánsan el lehetne dönteni, egész szép lenne a helyzet...

Ötlet, valaki? Csak olvassák matematikusok is a hup-ot :) !

[quote:cc7a6a1586="_Petya_"]Mert én 1...500 számokkal jelölöm a pontokat, és így ha az első pont sorszámát megszorzom 500-al, és hozzáadom a második számot, akkor ez jónak tűnik, csak az lenne a kérdésem, hogy van ennél hatékonyabb módszer?

Nem tudok róla. Technikailag hangyányit gyorsabb lenne, ha nem 500-zal szoroznád, hanem 9-cel shiftelnéd balra, de mivel valószínűleg nem assembly-ben írod, nemigen az az egy megspórolt óraciklus lesz a döntő :).

Bocs, hogy megint magam ala postolok, de jo lenne, ha valaki tudna segiteni...

Petya

http://oopweb.com/Algorithms/Documents/PLDS210/VolumeFrames.html

Irányítatlan a gráfod? Ha igen, akkor gyakorlatilag olyan minimális B-C utat keresel, ami átmegy az A ponton is.
Sajnos ez nem egyenértékű egy minimális B-A és A-C út keresésével, mert lehet, hogy a min. B-A út 'elhasznál' olyan pontot, amire az A-C útnak szüksége lenne, pl.:
[code:1:6611b21bbb]
10 100
B------A----+
|1 |1 |
+------Q----C
1
[/code:1:6611b21bbb]
Azaz BA=10, BQ=1, QA=1, AC=100, QC=1.
Ha veszed a minimális BA utat (BQA = 2), akkor a Q-t elhasználtad, így az AC útra csak a direkt AC=100 út marad, azaz az összeg 102.
Ha nem a minimális BA utat veszed, hanem a direkt BA=10 utat, akkor onnan az AC út lehet AQC=2, az összköltség pedig 12.
Ellenben a feladat (legalábbis nekem) erősen nem triviális.
A brute force (az összes BC út generálása, azokból az A-t tartalmazók közül a minimális megkeresése) lehetséges, de iszonyatos időigénye lenne.

Ha esetleg papíron is jó, nem csak neten, akkor:
Gács - Lovász: Algoritmusok (elsősorban a szokásos, kombinatorikai algoritmusok, + még egy kis algebra + bonyolultságelméleti alapműveltség)
Konkrét versenyfeladatok:
Hanák - Zsakó: Programozási versenyfeladatok tára '94
(nem tudom, hogy van-e újabb kiadás, ebben a Nemes Tihamér Verseny feladatai vannak).

A gráf irányított. A problémát, amit írtál én is is látom, csak megoldani nem sikerült még... lehet, hogy dinamikus programozással (táblázatkitöltés) kellene csinálni?

Petya

ha a Nemes Tihamérra készülsz, akkor én is a Cormen-Leierson-Rivest: Algoritmusok / Új algoritmusok könyvet ajánlom, ezekben minden megvan, ami kellhet;
a szélességi/mélységi keresést/bejárást érdemes vágni, néha egy kis Dijkstra-féle legrövidebb út algoritmus, meg valamelyik minimális feszítőfa algoritmus az, amivel már elég jól meg lehet oldani a feladatokat.

persze gyakorolni kell sokat, itt egy feladatgyűjtemény, amik a régebbi versenyeken voltak: [katt ide]
érdemes ezeket megnézni, a programozós fordulókban ezek vannak, a döntőn meg ezek közül a nehezebbek/ravaszabbak.
a filekezelés pedig könnyű, mert az inputok korrektek, legalább olyan szinten, ahogyan le van írva:)

üdv, és sok szerencsét;
G.

helo,
lehet hogy vmit felreertettem, de mit csinal az algo a
B D 1
B E 10
C E 1
C F 10
D E 1
E F 1
E A 10
F A 1
graffal? (a szamok a sulyok), ebben az optimalis utpar
BEA es CFA egyik tagja sem legrovidebb ut.
udv, ncs.

[quote:86d8e390e9="popacsek"]http://oopweb.com/Algorithms/Documents/PLDS210/VolumeFrames.html

Kicsit bővebben: http://oopweb.com/Algorithms/Files/Algorithms.html

[quote:f8db476603="nosy"]helo,
lehet hogy vmit felreertettem, de mit csinal az algo a
B D 1
B E 10
C E 1
C F 10
D E 1
E F 1
E A 10
F A 1
graffal? (a szamok a sulyok), ebben az optimalis utpar
BEA es CFA egyik tagja sem legrovidebb ut.
udv, ncs.

BEA = BE + EA = 10 + 10 = 20 szerintem nem minimális, ui.: BDEA = 1 + 1 + 10 = 12 rövidebb.

Nézzük az algoritmust: B-A min: BDEFA, C-A min: CEFA, legelső közös pont: E, tehát a megoldásban vagy a BDE vagy a CE benne lesz.

a., Tegyük fel, hogy CE lesz benne, ekkor vegyük ki a CE utat (ezúttal csak a CE élt), valamint az E-be befutó összes élt (DE, BE), és a maradékban keressük meg a B-A és E-A min. utakat. Meglepő módon B-A út nincs, ez a ló tehát nem nyert.

b., Tegyük fel, hogy a megoldásban a BDE lesz benne, vegyük hát ki a BDE utat (BD, DE élek), valamint az E-be befutó összes élt (BE, CE), és innen a feladatunk az E-A és C-A utak megkeresése. A gráf jelen helyzetben:
C F 10
E F 1
E A 10
F A 1
Erre megint az algoritmus: E-A min. út EFA, C-A min. út CFA, első közös pont az F, tehát a megoldásban vagy EF vagy CF benne lesz.

b1., Tegyük fel, hogy EF lesz benne: vegyük ki az EF utat (EF) ill. az F-be befutó összes élt (CF), majd a maradékon keressünk minimális C-A és F-A utat. Nincs C-A út, ez az ág tehát fuccs.

b2., Tegyük fel, hogy CF lesz benne a megoldásban, vegyük ki a CF utat (CF), valamint az összes F-be befutó élt (EF), és keressünk minimális E-A és F-A utat. A gráf jelenleg:
E A 10
F A 1

A min utak EA és FA csak A-ban találkoznak, tehát készen vagyunk, a megoldásban EA és FA benne lesznek.

Innen visszafelé összerakva az utakat:
EA és FA (a vége miatt), EA és CFA (b2 miatt), BDEA és CFA (b miatt).

Sziasztok!

Elolvasva az elöbbi kérdéseket már-már félve merem feltenni a kérdésem:
A feladatom a következő lenne, amihez a segítségeteket kérem:
Készítsen reguláris kifejezést és/vagy véges automatákat az alábbi nyelvek generálására/felismerésére. Ha mást nem mondunk az ábécé az {a,b} szimbólumok halmaza: olyan a {0,1} ábécé feletti w szavak, ahol a w által ábrázolt bináris szám osztható 3-mal

Ezt lehet csak reg.kif-el leírni?
Köszi!
Sz.

> Ezt lehet csak reg.kif-el leírni?

Nem értem kérdésedet, hiszen ismeretes, hogy az automatával felismerhető nyelvek osztálya, a reguláris nyelvek osztálya és a Chomsky 3 típusú nyelvek osztálya megegyezik. Tehát mindegy, hogy automatával vagy reg. kif-el írod le, mindkettő átalakítható a másikba, és a feladat bármelyiket elfogadja.

Tehát te a {0,1}^{*} feletti olyan w szót keresel, ahol w által ábrázolt szám osztható 3-mal. Szerintem próbálj meg automatát felrajzolni rá, én is gondolkodom rajta.

Petya

Szép feladat!
Automata: Három állapota lesz:
- M0 (mod 3 = 0)
- M1 (mod 3 = 1)
- M2 (mod 3 = 2)
Egy 0-s bit bejövetele 2-vel való szorzást jelent, egy 1-es bejövetele 2-vel való szorzás plusz egy-et, azaz az állapot-átmenetek:
(M0, 0) -> M0, mert 0*2 = 0
(M0, 1) -> M1, mert 0*2 + 1 = 1
(M1, 0) -> M2, mert 1*2 = 2
(M1, 1) -> M0, mert 1*2 + 1 = 3 = 0 (mod 3)
(M2, 0) -> M1, mert 2*2 = 4 = 1 (mod 3)
(M2, 1) -> M2, mert 2*2 + 1 = 5 = 2 (mod 3)
Kezdőállapot az M0, mert nulláról indulunk, elfogadó állapot szintén az M0, mert n mod 3 nulla kell, hogy legyen.

A regexp húzósabb, azon még törpölök egyet :).

A bc a te barátod.

Üdv!

Tudnátok segíteni?

A következő feladatot kaptam:

Egy gráfban kell utakat keresni, adott három szögpont, és keresni kell az egyikből a másikba, illetve az egyikből a harmadikba olyan utakat, hogy a két útnak csak az első pont legyen a közös pontja, és a két útt hosszának összege minimális legyen.

Nos, azt se tudom, hogy kedzjek hozzá. A gráfot valahogy letárolom egy tömbben, de hogyan tovább?

Petya

Oké, az automata alapján megvan a regexp is.

A kulcs-gondolat, hogy M0-ból hogyan juthatunk vissza M0-ba.
- egyrészt egy 0 hatására,
- másrészt ha jön egy 1-es, valami olyan, amitől M1-ből M1-be jutunk vissza, majd szintén egy 1-es.

M1-ből hogyan juthatunk vissza M1-be?
- egy 0, valami olyan, amivel M2-ből M2-be jutunk vissza, majd egy 0.

M2-ből hogyan juthatunk vissza M2-be?
- tetszőleges sok 1-es.

Ezek alapján az M2-ben maradás: '1*'
Az M1-ben maradás: '(0(1*)0)*', azaz '(01*0)*'
És végül az M0-ban maradás: '(0|1(01*0)*1)*'

Na ezt a regexp-et kerestük. Ki-escape-elve és teljes sorra vonatkoztatva ugyanez '^\(0\|1\(01*0\)*1\)*$', itt a teszt-script:
[code:1:c4a25d3e38]
#!/bin/bash

function binary0()
{
if [ "$1" != "0" ];
then
binary0 $(($1 / 2));
echo -n $(($1 % 2));
fi;
}

function binary()
{
if [ "$1" == "0" ];
then
echo -n "0";
else
echo $(binary0 $1);
fi;
}

for i in $(seq 40);
do
binary $i | grep "^\(0\|1\(01*0\)*1\)*$";
done;
[/code:1:c4a25d3e38]

[quote:221269823e="Panther"]A bc a te barátod.

A bc ennél a számnál: 2^345678 már egy picit gondolkodott, de egy 345 ezer bites szám sem okoz gondot, ez csak elég lesz...

helo,
- gsimon: igazad van! elneztem a peldat a grafos feladattal kapcsolatban.
- az automatas feladattal kapcsolatban: egy 'b' alapu rendszerben felirt szam pont
akkor oszthato b+1-gyel, ha a jegyeinek valtakozo elojelu osszege is oszthato vele.
bar nem tudom mi az az automata (csak mosogep szinten) de lehet hogy ez a
felismeresben segit...
udv, ncs

Na, azt hiszem, megvan.
Először is az eredeti G gráf alapján egy új G' gráfot kell építeni úgy, hogy a G' pontjai a G pontjaiból képzett párok legyenek, egy megkötéssel. A G-beli kiindulási pontot (ahonnan a két utat keresed) nevezzük A-nak, a két elérendő pontot V-nek és W-nek. A megkötés a következő:
- a G'-beli párokban lévő pontok nem lehetnek azonosak, kivéve egy esetet: AA
Tehát ha a G pontjai A, B, C és D voltak, akkor G' pontjai AA, AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC.
G' pontjai jelentsék azt, hogy az eredeti gráfban futtatott két út éppen hol tart.

Ezután állapítsuk meg G' éleit úgy, hogy a G'-beli XY pontból a szintén G'-beli PQ pontba megy él, ha G-ben X-ből megy él P-be és Y-ból megy él Q-ba, valamint ezen él költsége a G-beli X-P és Y-Q él költségének összege, magyarán szólva ha már a két út eljutott valamely költséggel A-ból X-be és Y-ba, akkor milyen költséggel juthat tovább P-be és Q-ba. Természetesen mivel az is lehetséges, hogy az egyik út marad X-ben és csak a másik megy tovább Q-ba, ezért P lehet egyenlő X-szel, és hasonlóan Q is lehet egyenlő Y-nal.
Egyelőre azzal ne foglalkozzunk, hogy esetleg ezek az utak menet közben érintenek közös pontokat is, az majd később kiesik.

Ezzel a feladatot majdnem visszavezettük arra, hogy a G'-ben kell egy AA-ból VW-be vagy WV-be menő utat találni. Itt ütközünk bele abba, hogy a két út használhat közös pontot (pl. AA-AC-BC-DC-VC-VD-VW, amikor D-t kétszer érintjük), ami nem engedhető meg.
Ezt azzal küszöbölhetjük ki, hogy a G'-beli minimális útkeresés közben nem azt tartjuk nyilván, hogy mely G'-beli pontot érintettünk már (és ezáltal még egyszer nem lépünk rá), hanem azt, hogy a felhasznált G'-beli pontok mely G-beli pontokat foglalják le (azaz pl. ha rálépünk a G'-beli MN pontra, akkor érintettnek jelöljük a G-beli M és N pontokat), és csak olyan G'-beli pontra engedélyezünk lépést, amely:
- valamely végpont (V vagy W), illetve
- egyik általa használt G-beli pont sincs érintettnek jelölve
Az első feltételre azért van szükség, hogy a kevesebb pontból álló G-beli út a végén "bevárhassa" a másik utat.
Ezzel garantáltan minimális költségű G'-beli utat kapunk, és mivel a G'-beli útköltség a két G-beli út árának az összege, a két út összköltsége is minimális lesz, valamint egyetlen pontot sem érintünk kétszer, ezért az utak diszjunktak is lesznek. Ezzel azt hiszem, kész is vagyunk :).

A lépésidő nagyságrendjére is próbáljunk egy becslést adni. Az eredeti G gráf álljon n pontból, melyek átlagos fokszáma legyen f. Ez alapján a G' gráf pontszáma 1+(n-1)*(n-1) (AA és a maradék n-1 ponthoz n-1 pontot rendelve, mert önmaga kiesik), azaz nagyságrendben n^2, az átlagos fokszáma pedig kb.
(f+1)(f+1) -1 (az MN pontból M felől lehet maradni + f ágon menni, N-ből úgyszintén, csak mindkettőben maradni nem lehet), azaz nagyságrendben f^2.
Ha jól emlékszem, a Dijstra-algoritmus lépésigénye az út pontjainak száma szorozva az átlagos fokszámmal, azaz nagyságrendben a pontok száma szorozva az átlagos fokszámmal (?), azaz itt n^2 * f^2. Hát ez brutális, de jobbat nem tudok.

Végig ugyan nem sakkoztam (valahol a harmadik és a negyedik sör között jött az ötlet tegnap :)...), tehát lehet, hogy elnéztem valamit, de kiindulásnak lehet, hogy jó lesz. Sok szerencsét :) !

Köszönöm a segítséget, ezt megpróbálom lekódolni. A feladat kiírása szerint az egészre van 3 másodperc, és lehet max 500 pont, és 40000 él...

Petya

gsimon for president! \o/ :lol:

[quote:c35d21df91="nosy"]bar nem tudom mi az az automata (csak mosogep szinten) de lehet hogy ez a
felismeresben segit...

Sajnos nem, mert aritmetikára lenne szükség, az összeg és társainak a fogalma meg túlmutat a lehetőségeken, de azért köszi!
Az automata gyakorlatilag egy olyan gondolati konstrukció, hogy vannak állapotok és közöttük menő nyilak, van egy aktuális állapot, amiben éppen vagyunk, és bizonyos feltételek hatására valamely innen menő nyíl mentén másik állapotba lépünk át.
A legegyszerűbb esetben (véges automata) ez a bizonyos feltétel csak a következő olvasott karaktertől függ, tehát olyan szabályaink vannak, hogy "ha az A állapotban x-et olvastunk, akkor átlépünk a B állapotba", "ha az A állapotban y-t olvastunk, akkor maradunk az A állapotban". Kb. mint a régi "Gazdálkodj okosan/Monopoly" játékban: ha a 42-es mezőn állsz, és a kockával 4-est dobsz, akkor menj a 100-as mezőre, különben a 43-asra :), csak itt nem a kockadobás a feltétel, hanem a bejövő karakter.
Természetesen ki kell jelölni egy kezdő állapotot, ami az egész cirkusz elején aktuálisnak tekinthető, és meg kell adni azon állapotokat, amelyeket "jónak" tekintünk, ami azt jelenti, hogy ha a teljes szöveg végigolvasása után a rendszer ezen állapotában tartózkodik, akkor az a szöveg "a célunknak megfelelő".
Maguk az állapotok valamilyen értelemben jellemzik azt a beolvasott karaktersorozatot, aminek hatására odajutottunk, a fenti példában ezek azok voltak, hogy "eddig a karakterig olvasva a 3-mal osztás maradéka 0, 1, vagy 2".

Természetesen nem minden feladat oldható meg véges automatával, tehát pl. egy sorozatról azt eldönteni, hogy olyan 'aa..abb..b" sorozat-e, amiben az a-k és b-k száma egyenlő, nem lehet, mert az állapotokban kéne valahogy tárolni, hogy eddig hány 'a' jött, ami viszont tetszőlegesen sok lehet, az állapotokból meg véges sok van. Az ilyesmikhez a véges automatát bővíteni kell egy veremmel, és onnantól az állapot-átmenetek nem csak a "ha ebben az állapotban ezt olvastuk, akkor ide megyünk" típusúak, hanem "ha ebben az állapotban ezt olvastuk és a verem tetején ez van, akkor ide megyünk, és ezt toljuk a verem tetejére", na ezt hívják veremautomatának.

Aztán persze érdekes téma, hogy mely feladatokhoz milyen automata kell, mi a kapcsolat a felismert nyelvek és az őket felismerő automata-osztályok között, van-e olyan feladat, amihez a veremautomata is kevés, van-e olyan feladat, amit nem lehet semmilyen automatával felismertetni, stb., hát valami ilyesmiről szól a "Formális nyelvek és automaták" c. tantárgy :).

Ha érdekel a téma, tudom javasolni Bach Iván tanár úr ugyanilyen című BME-s jegyzetét, szépen, korrektül, olvasmányos stílusban leírja az egészet az alapoktól egész a fordítóprogramok elvi alapjaiig. Ha jól tudom, a BME jegyzetbolt még mindig Petőfi híd budai hídfőjénél a V2 épület földszintjén van :).

gsimon!
Köszi!!!!
A következő HUP sörözésen én állom az első körödet! :)
Tényleg lesz valamikor ilyen?

csak 2..16 alapút.

hi,
legyen az egyik=F, a masik=C1 ill. a harmadik C2.
nincs mas dolgod mint 2 [DB]FS-t "csinalni" F-bol.
Az F->C1 bejaras elott letiltod (latogatotta teszed) C2-t,
a masik bejarasnal forditva jarsz el.
Nem mindig van ilyen tulajdonsagu ut paros.
udv, ncs.

[quote:3184913260="nosy"]hi,
legyen az egyik=F, a masik=C1 ill. a harmadik C2.
nincs mas dolgod mint 2 [DB]FS-t "csinalni" F-bol.
Az F->C1 bejaras elott letiltod (latogatotta teszed) C2-t,
a masik bejarasnal forditva jarsz el.
Nem mindig van ilyen tulajdonsagu ut paros.
udv, ncs.

Huh, ez nekem nem kicsit kínai, de megpróbálom megérteni. Tehát arra gondoltam, hogy a gráfot tömbben ábrázolom, és a tömb [i,j] eleme akkor 1-es, ha az i. és j. pont között van él, egyéb esetben 0. Az is lehet, hogy ez teljesen marhaság, hiszen az algoritmusom 64 mega memóriát használhat, és max 3 mp-is futhat. Szóval mi is az a 2 [DB]FS-t "csinalni" F-bol? A többi részből annyit értek, hogy valahogy le kell tárolni, hogy adott pont az adott bejárásban benne van, vagy nincs. Eddig jól értem?

Petya

ok,
maradjunk a BFS-nel. ez a szelessegi kereses roviditese.
tehat BFS-t inditasz F-bol "C1-be" ugy hogy C2-t tiltod,
majd forditva. azert van idezojelben az hogy C1-be, mert BFS-t
nem szoktak valahova, csak valahonnan inditani, de a kereses
leallithato ha megtalaltad a celt. a BFS-t sorral szoktak
implementalni, egy "segedsorral" az utvonal csucsai is
megjegyezhetok ill. visszafejthetok.
az osszes ilyen ut kell vagy csak 1 (ha van)?
mert ha az osszes akkor valami mast kell csinalni...
udv, ncs

JO NAGY HULYESEGET IRTAM, EZ NEM JO MEGOLDAS. BOCS.

[quote:7cbf265f70="Panther"]A bc a te barátod.

tagadok mindent :-) nem is ismerem

bc

Hi!

Ha kell, el tudok egy Algoritmusok konyvet (ez olyan 1-200 oldal), es egy C peldatar konyvet (ennek a 2. fele csak versenyfeladatokbol all) kuldeni.

Egyebkent versenyekre a dinamikus programozast celszeru atnezni.

A maradekos osztashoz egy otlet:Ha mondjuk 1000-nek a 3-mal vett maradekat akadod kiszamolni: veszed a 729-et. Ez 3^6. Levonod az 1000bol. Akkor 271-et kapsz, aminek a 3mal vett maradeka ugyanaz, mint az 1000-nek. A legnagyobb 3 hatvany, ami <=271 a 243=3^5. Utana 28at kapsz. Es igy tovabb.

By(t)e
TBS::Antiemes

Csak 1 ilyen út kell. Utánanázek a szélességi keresésnek a Cormen-féle könyvben. Köszönöm az eddigi segítségetl, lehet, hogy még kérdezek..

Petya

szerk: OK, akkor nem így csinálom, de a gráfban keresésnek azért akkor is utánanézek :)

hella,

http://www.konyvkereso.hu/netacgi/konyvker/index.pl?ln=M&fm=idxm.htm
ill.
http://aszt.inf.elte.hu/~hunlaci/book.pdf

de erdemes a weblapon korulnezni.

utobbi picit szaraz, az elso, kollega altal is ajanlott konyv nagyon jo, kimondottan elvezetes olvasmany... :)

a.

Üdv!

(szerk: jó ez a motor, kimoderálja a g r á f o s szót...)

Ha esetleg érdekel valakit a gráfos feladatra beadott megolásom, akkor leírom:

Tehát először keresünk két optimális utat a pontból(r) a másik kettőbe (a,b), külön-külön, egy módosított szélességi keresés algritmussal, ahol adott pontot ki lehet tiltani a keresésekből (mintha ott se lenne) . Itt még nem törődünk azzal, ha vannak közös pontok. Itt kiderül, hogy egyáltalán elérhetők-e a pontok. Ha nem, megállunk. Ha elérhető, akkor kigyűjtjük a közös pontokat. Ezután ezeket a pontokat kell "elosztani" a két út között. Tehát: megvan, hogy letiltott pontok nélkül, közös pontokkal nem törődve, el lehet jutni a-ba, és b-be, és ezen utak hossza is ismert. Most a közös pontok közül vesszük az elsőt, és letiltjuk az A és B keresésben is. Újra csinálunk két BFS-t, ennek eredménye lehet az alábbiak közül valamelyik:
1. Sem az a, sem a b pontba nem tudunk így eljutni => a letiltot pontra mindkét útnak szüksége van, így nincs két diszjunkt út.
2. Csak az a pontba tudtunk eljutni => B út kapja a pontot.
3. Csak a b pontba => A út kapja a pontot
4. Mindkettőbe el lehet jutni => megnézzük az úthosszak különbségét, az az út kapja a pontot, amelyik nagyobb kerülőre kényszerült.

pl. B út kapja a pontot: az a keresésben marad tiltva, B-ben engedélyezzük.

Röviden ennyi. A programom a 22 tesztesetből 19-re jól működött...

Petya