Declaratieve Talen/Oplossing Dijkstra Alternatief (Haskell): verschil tussen versies

Uit Wina Examenwiki
Naar navigatie springen Naar zoeken springen
Nieuwe pagina: ====Mogelijke oplossing==== alleen het kortste pad wordt niet terug gegeven, hiervoor zou je bij uw afbeelding moeten bijhouden van welke knoop de waarde afkomstig is, zodat je deze ...
 
 
Regel 1: Regel 1:
====Mogelijke oplossing====
====Alternatieve oplossing (geeft pad en afstand terug) ====
 
alleen het kortste pad wordt niet terug gegeven, hiervoor zou je bij uw afbeelding moeten bijhouden van welke knoop de waarde afkomstig is, zodat je deze op het einde achteruit kan doorlopen enzo het kortste pad kan contrueren.


<pre>
<pre>
import List
import List


data Afstand = Waarde Int | Oneindig | Null
data Afstand = Afst Int | Inf deriving Show
deriving (Eq, Show)
type Pad = [String]


instance Eq Afstand where
(Afst x) == (Afst y) = x == y
Inf == _ = False
_ == Inf = False
instance Ord Afstand where
instance Ord Afstand where
Oneindig <= Oneindig = True
(Afst x) <= (Afst y) = x <= y
Oneindig <= Waarde a = False
Inf <= _ = False
_ <= Oneindig = True
_ <= Inf = True
Waarde a <= Waarde b = (a <= b)
Null <= _ = False
_ <= Null = False
Oneindig >= _ = True
------------------------------------------------------------------------
Waarde a >= Oneindig = False
Waarde a >= Waarde b = (a >= b)
Null >= _ = False
_ >= Null = False
Oneindig < _ = False
dijkstra :: String -> String -> (Afstand, String)
Waarde a < Oneindig = True
dijkstra s e =  
Waarde a < Waarde b = (a < b)
let
Null < _ = False
allknopen = knopen
_ < Null = False
init = (Afst 0, s, s) : [(Inf, kn, "") | kn <- allknopen, kn /= s]
tabel = dijkstra2 e allknopen init
Oneindig > Oneindig = False
--
Oneindig > _ = True
distance = getdistance e tabel
Waarde a > Oneindig = False
path = findpath s e tabel
Waarde a > Waarde b = (a > b)
in
Null > _ = False
(distance, path)
_ > Null = False
------------------------------------------------------------------------
--- Dijkstra algoritme: stel tabel op (Afstand, Punt, KortsteAfstandPunt)


boog :: String -> String -> Afstand
dijkstra2 :: String -> [String] -> [(Afstand, String, String)] -> [(Afstand, String, String)]
boog x y
dijkstra2 endknoop remknopen tabel =
| boog2 x y == Null = boog2 y x
| True = boog2 x y
 
boog2 :: String -> String -> Afstand
------------------------------------
boog2 "a" "b" = Waarde 10
boog2 "b" "e" = Waarde 8
boog2 "e" "f" = Oneindig
boog2 "f" "c" = Waarde 7
boog2 "c" "a" = Waarde 5
boog2 "c" "d" = Waarde 3
boog2 "d" "e" = Waarde 9
boog2 x y = Null
 
knopen :: [String]
------------------
knopen = ["a", "b", "c", "d", "e", "f"]
 
dijkstra :: String -> String -> (Afstand, Pad)
----------------------------------------------
dijkstra beginknoop eindknoop =  
let
let
-- zet T gelijk aan V
klknoop@(_, k, _) = zoek_kleinste remknopen tabel
t = knopen
newremknopen = delete k remknopen
-- Definieer afbeelding L op V door L(a) = 0 L(x) = Oneindig
newtable = updatetabel newremknopen klknoop tabel
afbeelding = [(beginknoop, Waarde 0)] ++ [ (x, Oneindig)  | x <- t, x /= beginknoop]
in
dijkstra2 beginknoop eindknoop t afbeelding
dijkstra2 :: String -> String -> [String] -> [(String, Afstand)] -> (Afstand, Pad)
----------------------------------------------------------------------------------------------
dijkstra2 bk ek t a =
let
-- Kies een v element van t met de kleinste L(v)
kleinste@(ks, ka) = zoek_kleinste t a
-- zet t gelijk aan t zonder v
newt = delete ks t
-- herberekn voor alle knopen y in t die verbonden zijn met knoop v, zet L(y) = min(L(y), L(v) + w(v,y))
newa = herbereken ks ka a t
in
in
-- indien z geen element meer is van t dan stopt het algoritme
if (k == endknoop)
if (not (elem ek newt))
then
then (ka , knopen\\t)
newtable
else dijkstra2 bk ek newt newa
else
dijkstra2 endknoop newremknopen newtable
herbereken :: String -> Afstand -> [(String, Afstand)] -> [String] -> [(String, Afstand)]
----------------------------------------------------------------------------
updatetabel :: [String] -> (Afstand, String, String) -> [(Afstand, String, String)] -> [(Afstand, String, String)]
herbereken v lv [] t = []
updatetabel _ _ [] = []
herbereken v lv ((s,a):as) t =
updatetabel remknopen klknoop@(dmin, kmin, _) (currknoop@(dcurr, kcurr, _) : xs) =
if ((elem s t) && ((boog v  s) /= Null))
if (elem kcurr remknopen)
then  
then
let  
let
newa = min (plusafstand lv (boog v s)) a
newcurrknoop = getnewdist klknoop currknoop
in
in
(s, newa):herbereken v lv as t
newcurrknoop : updatetabel remknopen klknoop xs
else (s,a):herbereken v lv as t
else
currknoop : updatetabel remknopen klknoop xs
plusafstand :: Afstand -> Afstand -> Afstand
getnewdist :: (Afstand, String, String) -> (Afstand, String, String) -> (Afstand, String, String)
--------------------------------------------
getnewdist (dmin, kmin, kminorig) orig@(dcurr, kcurr, kcurrorig) =
plusafstand (Waarde a) (Waarde b) =  
let
let
newa = a+b
dnew = plusafstand dmin (boog kmin kcurr)
--dnew = min dcurr drol
in
in
Waarde newa
if dcurr < dnew
plusafstand (Waarde a) Oneindig = Oneindig
then
plusafstand Oneindig (Waarde a) = Oneindig
orig --(dcurr, kcurr, kcurrorig)
plusafstand _ _ = Null
else
(dnew, kcurr, kmin)
zoek_kleinste :: [String] -> [(String, Afstand)] -> (String, Afstand)
 
---------------------------------------------------------------------
plusafstand :: Afstand -> Afstand -> Afstand
zoek_kleinste t [(s, a)] =  
plusafstand Inf _ = Inf
if (elem s t)
plusafstand _ Inf = Inf
then (s,a)
plusafstand (Afst x) (Afst y) = Afst (x + y)
else ("geen knoop", Oneindig)
 
zoek_kleinste t ((s, a):xs) =
zoek_kleinste :: [String] -> [(Afstand, String, String)] -> (Afstand, String, String)
zoek_kleinste remknopen [curr@(_, k, _)] =
if (elem k remknopen)
then
curr
else
(Inf, "Error", "")
zoek_kleinste remknopen (newcandid@(d0, k0, _) : xs) =  
let
let
kleinste@(ks, ka) = zoek_kleinste t xs
smallest@(d1, k1, _) = zoek_kleinste remknopen xs
in
in
if(a <= ka && (elem s t))
if (d0 < d1 && (elem k0 remknopen))
then (s,a)
then
else kleinste
newcandid
else
smallest
 
------------------------------------------------------------------------
--- Pad bepalen
 
findpath :: String -> String -> [(Afstand, String, String)] -> String
findpath s e table | s == e = s
| otherwise =
let
nextkey = getnext table e
in
(findpath s nextkey table) ++ e
 
getnext :: [(Afstand, String, String)] -> String -> String
getnext ((_, key0, nextkey) : xs) key1 | key0 == key1 = nextkey
| otherwise = getnext xs key1
 
------------------------------------------------------------------------
--- Afstand opzoeken in tabel
getdistance :: String -> [(Afstand, String, String)] -> Afstand
getdistance key1 ((dist, key0, _) : xs) | key0 == key1 = dist
| otherwise = getdistance key1 xs
 
------------------------------------------------------------------------
-- Geimproviseerde gegevens
 
boog :: String -> String -> Afstand
boog s e | dist s e < Inf = dist s e
| otherwise = dist e s
 
dist :: String -> String -> Afstand
dist "a" "b" = Afst 1
dist "a" "c" = Afst 2
dist "a" "d" = Afst 10
dist "b" "c" = Afst 5
dist "c" "d" = Afst 1
dist _ _ = Inf
 
knopen :: [String]
knopen = ["a", "b", "c", "d"]
</pre>
</pre>

Huidige versie van 13 jan 2009 18:16

Alternatieve oplossing (geeft pad en afstand terug)

import List

data Afstand = Afst Int | Inf deriving Show

instance Eq Afstand where
	(Afst x) == (Afst y) = x == y
	Inf == _ = False
	_ == Inf = False
	
instance Ord Afstand where
	(Afst x) <= (Afst y) = x <= y
	Inf <= _ = False
	_ <= Inf = True
	
------------------------------------------------------------------------
	
dijkstra :: String -> String -> (Afstand, String)
dijkstra s e = 
	let
		allknopen = knopen
		init = (Afst 0, s, s) : [(Inf, kn, "") | kn <- allknopen, kn /= s]
		tabel = dijkstra2 e allknopen init
		--
		distance = getdistance e tabel
		path = findpath s e tabel
	in	
		(distance, path)
		
------------------------------------------------------------------------
--- Dijkstra algoritme: stel tabel op (Afstand, Punt, KortsteAfstandPunt)

dijkstra2 :: String -> [String] -> [(Afstand, String, String)] -> [(Afstand, String, String)]
dijkstra2 endknoop remknopen tabel =
	let
		klknoop@(_, k, _) = zoek_kleinste remknopen tabel
		newremknopen = delete k remknopen
		newtable = updatetabel newremknopen klknoop tabel
	in
		if (k == endknoop)
		then
			newtable
		else
			dijkstra2 endknoop newremknopen newtable
		
updatetabel :: [String] -> (Afstand, String, String) -> [(Afstand, String, String)] -> [(Afstand, String, String)]
updatetabel _ _ [] = []
updatetabel remknopen klknoop@(dmin, kmin, _) (currknoop@(dcurr, kcurr, _) : xs) =
	if (elem kcurr remknopen)
	then
		let
			newcurrknoop = getnewdist klknoop currknoop
		in
			newcurrknoop : updatetabel remknopen klknoop xs
	else
		currknoop : updatetabel remknopen klknoop xs
	
getnewdist :: (Afstand, String, String) -> (Afstand, String, String) -> (Afstand, String, String)
getnewdist (dmin, kmin, kminorig) orig@(dcurr, kcurr, kcurrorig) =
	let
		dnew = plusafstand dmin (boog kmin kcurr)
		--dnew = min dcurr drol
	in
		if dcurr < dnew
		then
			orig --(dcurr, kcurr, kcurrorig)
		else
			(dnew, kcurr, kmin)

plusafstand :: Afstand -> Afstand -> Afstand
plusafstand Inf _ = Inf
plusafstand _ Inf = Inf
plusafstand (Afst x) (Afst y) = Afst (x + y)

zoek_kleinste :: [String] -> [(Afstand, String, String)] -> (Afstand, String, String)
zoek_kleinste remknopen [curr@(_, k, _)] =
	if (elem k remknopen)
	then
		curr
	else
		(Inf, "Error", "")
zoek_kleinste remknopen (newcandid@(d0, k0, _) : xs) = 
	let
		smallest@(d1, k1, _) = zoek_kleinste remknopen xs
	in
		if (d0 < d1 && (elem k0 remknopen))
		then
			newcandid
		else
			smallest

------------------------------------------------------------------------
--- Pad bepalen

findpath :: String -> String -> [(Afstand, String, String)] -> String
findpath s e table 	| s == e = s
					| otherwise = 
						let
							nextkey = getnext table e
						in
							(findpath s nextkey table) ++ e
						

getnext :: [(Afstand, String, String)] -> String -> String
getnext ((_, key0, nextkey) : xs) key1	| key0 == key1 = nextkey
										| otherwise = getnext xs key1

------------------------------------------------------------------------
--- Afstand opzoeken in tabel
getdistance :: String -> [(Afstand, String, String)] -> Afstand
getdistance key1 ((dist, key0, _) : xs)	| key0 == key1 = dist
										| otherwise = getdistance key1 xs
		

------------------------------------------------------------------------
-- Geimproviseerde gegevens

boog :: String -> String -> Afstand
boog s e	| dist s e < Inf	= dist s e
			| otherwise			= dist e s

dist :: String -> String -> Afstand
dist "a" "b" = Afst 1
dist "a" "c" = Afst 2
dist "a" "d" = Afst 10
dist "b" "c" = Afst 5
dist "c" "d" = Afst 1
dist _ _ = Inf

knopen :: [String]
knopen = ["a", "b", "c", "d"]
Overgenomen van "http://examens.wina.be/index.php?title=Declaratieve_Talen/Oplossing_Dijkstra_Alternatief_(Haskell)&oldid=9934"