Gráf és a bash

UNIX kezdő

Üdvözletem kedves fórumlakók, kihívást keresők!
Lenne itt egy feladatom, amihez segítséget szeretnék kérni. A feladat a következő:

Keszitsen olyan bash programot amely beolvas egy text file-bol egy grafot
es ebben megtalalja a leghosszabb utat ket a programunknak megadott csucs kozott.
A text file minden egyes sora egy graf elet irjon le pl: "1-3", "4-2" stb.

Ehez annyit tennék hozzá hogy megvan az alap program azon változata mely a legrövidebb utat keresi ki.
De ezt még ki kellene bővíteni annyival, hogy ne mi adjuk meg a kezdő és a végpontot,
hanem a program bejárja az összes lehetséges utat az összes csúcsból kiindulva.
Valamint ellenőrizni kell hogy ne legyen benne kör.

Itt a graf.txt tartalma:
1-2
2-3
2-4
3-5
4-6
4-7

Ehez az elkészített program részletekben:

Ez a része felel a legrövidebb kiválasztásáért(ha minden igaz):

cnt=1;
sor=`cat $1 | wc -l`;
sor=`expr $sor + 1`;
min=`cat $1 | head -n 1 | tail -n 1 | wc -L`
minstr=`cat $1 | head -n 1 | tail -n 1`
while [ $sor != $cnt ]
do
if [ $min -gt `cat $1 | head -n $cnt | tail -n 1 | wc -L` ]
then
min=`cat $1 | head -n $cnt | tail -n 1 | wc -L`;
minstr=`cat $1 | head -n $cnt | tail -n 1`;
fi
cnt=`expr $cnt + 1`;
done
echo $minstr;

Előre is köszönöm Minden kedves segítő egyénnek hogy fogalkozik a problémámmal!

  • 1689 megtekintés

( nosy | 2008. 10. 27., h – 20:27 )

udv,
csak 1 kerdes:
hogy lesz legrovidebb ut keresobol leghosszabb ut kereso?

Talán, ha irányítom a gráfot, akkor lehet, hogy közelebb jutok a megoldáshoz:

irányított gráf esetén persze több legrövidebb út is lehetséges. (mármint több "a" és "b" között).
mivel egy általános gráfról van szó, ezért ez tartalmazhat kört is. az irányítás csak extra.
biztos, hogy van olyan a->b legrövidebb út, ami egy kör kerületi szakasza.
akkor veszem a b->a irányított utat, ami tuti hogy hosszabb, mint az a->b, mivel több csúcsát is tartalmazza a gráfnak
biztos, hogy marad ki lehetséges él, amivel még bővíthető ez a maximális út, ezért a visszirányú körből kimaradt csúcsokkal próbálom bővíteni a már létező b->a->b kört, aminek a végén az a->b élet elhagyva egy körmentes leghosszabb út az eredmény.

vagy nagyon nyakatekert és logikátlan?

/mazursky 

Love your job but never love your company!
Because you never know when your company stops loving you!

Bocs, de ennek nem sok értelme van amit leírtál. Vagy nagyon félreértesz valamit, vagy jól gondolkozol, csak nem tudod jól leírni.
Először is mit jelent nálad, hogy irányítod a gráfot? A gráfot irányított gráfnak veszed, minden él helyett egy oda és egy vissza éllel? Vagy valahogy önkényesen kiválasztasz minden élnek egy irányt? Az elsőnek lehet értelme, sok algoritmus van, amit irányított gráfokra találtak ki, és egyszerűen lehet általános gráfból ilyen módon irányított gráfot csinálni. Viszont az érvelésedet nem tudtam ezzel összeegyeztetni. A második lehetőségnek pedig természetesen semmi értelme.

"irányított gráf esetén persze több legrövidebb út is lehetséges. (mármint több "a" és "b" között)."
Ezzel sem tudok mit kezdeni, persze hogy több legrövidebb út lehet, de ez nem csak az irányított gráfokra igaz. Ha már van két párhuzamos él(azaz 2 olyan él, amiknek a két végpontja megegyezik), akkor az már egyből 2 különböző út lehetséges, úgy, hogy az érintett pontok megegyeznek. A zárójeles megjegyzést sem értem. Egy út két pont között húzódik, hogy lehetne már több pont között. Vagy több "a" és "b" pont között páronként? Csak az meg nem tudom, hogy hogy jön ide.

"biztos, hogy van olyan a->b legrövidebb út, ami egy kör kerületi szakasza."
Már mitől lenne biztos? Ha tényleg úgy értetted, hogy minden él helyett van egy oda, meg vissza él, akkor tényleg biztos, viszont ezzel még nem nyersz semmit, ugyan az a feladat ezt a kört megtalálni, mint az a->b utat az eredetiben. Ha viszont nem úgy értetted, akkor pl egy fában nincs kör, mivel a fa a definíció szerint a körmentes gráf. Igaz, hogy ilyenkor összvissz 1 út van két pont között, viszont azt akkor is meg kell találni, tehát nem kereshetsz köröket.

A továbbiakat ezek után már ezek hiányában nem is lehet értelmezni.

Léci legközelebb pontosabban fogalmazz, mert ezt így sok féle képpen lehet érteni. Attól, hogy te megérted az alapján, amit leírsz, más nem biztos, hogy ugyanúgy értelmezi, ha nem fogalmazol elég precízen. (bocs, még valami, hogy lehet bővíteni egy maximális utat?)

Csak hogy a kérdésre is válaszoljak:
Két pont közötti legrövidebb út megkereséséhez egység súlyú élekkel elég egy sima szélességi keresés.
Minden két pont közötti legrövidebb út megkeresésére találták ki a Floyd algoritmust ( http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm ).
Ha két pont között keresed a leghosszabb utat, az már nem ilyen egyszerű, sajnos az utazó ügynök problémára visszavezethető, szal NP-teljes. Egyébként én egy mélységi kereséssel indulnék el, kicsit a problémára szabva.

( gergob | 2008. 10. 27., h – 20:57 )

Lehet, hogy rosszul kozelitem meg, de szerintem ha a while-ban levo if-nek nem -gt han -le kapcsolot adsz akkor a leghosszabb utat kapod...
Csak kosza gondolat, ha nem akkor bocsanat a felrevezetesert.

( stra | 2008. 10. 27., h – 21:08 )

Nosy felvetésén túl:
- próbáld meg először algoritmizálni, és utána megírni a bash scriptet
- a fenti kód sejtésem szerint a legrövidebb (legkevesebb karakterből álló) sorok közül az elsőt választja ki. Valószínűleg nem ezt keressük.
- ez véleményed szerint mely csúcsok között vizsgálná az utat?
- rengeteg feleslegesen túlbonyolított megoldás van benne. Párosával a példák: 

sor=`cat $1 | wc -l`;
sor=`wc -l $x`

sor=`expr $sor + 1`;
sor=$(($sor + 1))

minstr=`cat $1 | head -n 1 | tail -n 1`
minstr=`head -n 1 $1`

if [ $min -gt `cat $1 | head -n $cnt | tail -n 1 | wc -L` ]
if [ $min -gt `head -n $cnt $1 | tail -n 1 | wc -L` ]

min=`cat $1 | head -n $cnt | tail -n 1 | wc -L`;
min=`head -n $cnt $1 | tail -n 1 | wc -L`

minstr=`cat $1 | head -n $cnt | tail -n 1`;
minstr=`head -n $cnt $1 | tail -n 1`

cnt=`expr $cnt + 1`;
cnt=$(($cnt + 1))

A head -n 1 | tail -n 1 kiváltható lenne egy readdel.

( sibidiba | 2008. 10. 27., h – 21:09 )

csak nem megint eljött a progkör beadandók ideje?