JavaScript útkeresés

3. A mélységi kereső algoritmus

A mélységi kereső algoritmus széleskörben használt olyan nehéz feladatok megoldásainak keresésére, mint az útvonalkereső algoritmusok. A legtöbb kifejlett algoritmus alapját ez adja. A lényege, hogy a keresést elindítjuk egy irányban, amit addig követünk, amíg zsákutcába nem jutunk, vagy megoldáshoz. Ezen kívül viszont az összes lehetőséget elmentjük, amerre még folytathattuk volna a keresést egy döntésnél. Ha megakadunk egy ágon, akkor az ahhoz legközelebbi döntés egy másik irányában próbálkozunk.

Bemenet: A böngésző munkaterületén kialakított, pontokat (amelyek városokat jelölnek) tartalmazó játéktér, amelyen a pontok között különböző súlyú élek mennek (súlyozott gráf). A példában az élek színe jelöli a súly, a zöld élek a rövidek, a pirosak a hosszúak.

Kimenet: A start (piros) és end (kék) városok közötti útvonal legrövidebb útvonal, vagyis ahol a használt élek összsúlya a legkevesebb.

Változók: A pontok és élek adatai, tömbökben tárolva.

Algoritmus: Nyilvántartunk egy listát, ahol az elkezdett, de még be nem fejezett útvonalakat tároljuk. Kezdetben csak egy félkész útvonalat tartalmaz, ami egy pontból áll, a start-ból. Amíg a lista ki nem ürül, addig mindig kiválasztunk belőle egy félkész útvonalat, amit meghosszabítunk. A meghosszabítás azt jelenti, hogy kiválasztjuk az összes lehetőséget (élet), amerre az útvonalat az utolsó csúcsból folytatni tudjuk, és még nem jártunk a végpontban. Az összes új, ilyen módon generált félkész útvonalat a listába helyezzük. Amennyiben egy útvonalon eljutunk a célba, úgy egy befejezett útvonalat kapunk. A befejezett útvonalak közül elegendő csak a legrövidebbet eltárolni, hiszen erre lesz szükségünk, mint megoldás. A mélységi keresés úgy fog megvalósulni ezzel az algoritmussal, hogy mindig azt az útvonalat választjuk ki a listából, amit legutóbb tettünk bele. Ez legegyszerűbben úgy valósítható meg, ha mindig a lista végéről választjuk ki az útvonalakat, és a lista végére is tesszük az újakat.

Eseménykezelés: Az onclick esemény bekövetkezésekor végrehajtandó metódusokat a hitTest() függvényből hívjuk meg.

Az alábbiakban rendszerezzük a megoldáshoz szükséges ismereteket. A platformfüggetlen megoldás elkészítéséhez gyakorlatilag egy böngésző programra, és esetleg egy egyszerűbb editorra van szükség. A lecke mintaprogramja a böngészőben kipróbálható és módosítható. Indátásához kattintsatok a forráskód alatti "Próbáld ki! »" gombra.

1	Az algoritmus jellemzői

Az algoritmus véges számú, végrehajtható műveletek sorozatának az elnevezése. Fontos szabály még az is, hogy mindig van bemenete és legalább egy kimenete. A számítógép által értelmezhető nyelven megírt algoritmus pedig a program. Azokat a típusalgoritmusokat, amelyek egy feladat egzakt megoldását adják programozási tételeknek nevezzük. Ilyen például a sorozatszámítás, minimim-maximum választás, keresés, rendezés algoritmusa. Az algoritmusokat nem forrásnyelvi kódban szokták megadni, hanem leíróeszközök segítségével (pl. folyamatábrával, struktogrammal, Jackson ábrával vagy pszeudó kóddal) írják le, amit aztán kódolni lehet egy adott környezetben.

Hasznos leírások:

Adonyi Róbert: Adatstruktúrák és algoritmusok
Heckl István: Adatstruktúrák és algoritmusok példatár

« Előző | Lap eleje

2	Hogyan alakítsuk ki a belső adatszerkezetet?

Az algoritmus által használt értékeket változókban tároljuk. A programnyelvek egyszerű és összetett változókkal dolgoznak. A programtervezés során az adattípusok meghatározása mellet, ügyelnünk kell a belső adatszerkezet optimális kialakítása is. Egy ügyesen tervezett adatszerkezet rengeteg munkát megspórolhat a kódolásnál.

Egy város adatait és objektumban tároljuk. Az útvonal megkereséséhez fontos információ eltárolni, hogy a város a keresés kiinduló, vagy végpontja. Ezen kívül az eredmény megjelenítése szempontjából hasznos eltárolni, hogy a megtalált legrövidebb úton található-e. Az éleknek nem ekll külön objektom, jelenleg csak egy számot tartalmaznak, ami az él súlya. A városokat és éleket egy-egy tömbben tároljuk.

// ==== Itt tároljuk egy város adatait
	function City(id, x, y)
	{
		this.Id=id;
		this.X=x;
		this.Y=y;
		this.Start=false;
		this.End=false;
		this.Road=false;
	}
	var Game = {
		Canvas: null,
		CityCount: 10,
		CityRad: 10,
		Cities: [],
		StartCity: null,
		EndCity: null,
		Roads: [],
		Timer: null,

		Init: function (id) {
			this.Canvas = Canvas2D;
			this.Canvas.Init(id);
// ==== Készítsünk 10 várost a példához
			this.Cities[0]=new City(0,50,50);
			this.Cities[1]=new City(1,100,500);
			this.Cities[2]=new City(2,150,250);
			this.Cities[3]=new City(3,200,550);
			this.Cities[4]=new City(4,350,350);
			this.Cities[5]=new City(5,450,150);
			this.Cities[6]=new City(6,500,200);
			this.Cities[7]=new City(7,700,100);
			this.Cities[8]=new City(8,700,400);
			this.Cities[9]=new City(9,750,550);
// ==== Kezdetben az első a start, és az utolsó az end			
			this.StartCity=this.Cities[0];
			this.StartCity.Start=true;
			this.EndCity=this.Cities[9];
			this.EndCity.End=true;
			
			for (var i=0; i<this.CityCount; i++)
			{
				this.Roads[i]=new Array(this.CityCount);
				for (var j=0; j<this.CityCount; j++)
					this.Roads[i][j]=null;
			}
			
// ==== Rajzoljunk be éleket
			this.Roads[0][1]=this.Roads[1][0]=8;
			this.Roads[2][3]=this.Roads[3][2]=1;
			this.Roads[4][5]=this.Roads[5][4]=4;

A program futtatása közben további úgynevezett segédváltozókat is használunk, amelyekkel bizonyos vezérlőszerkezetek működést tudjuk irányítani. Ugyancsak gondoskodnunk kell a kimenő adatok tárolását biztosító adatszerkezetekről is. Ez utóbbiak lehetnek egy másik programmodul, vagy objektum bemenő adatai.

« Előző | Lap eleje

3	Hogyan működik a mélységi keresés?

A játéktéren a városokat jelölő pontok közül a piros jelöli az út kezdetét, a kék pedig a végét. A zöld pontok a legrövidebb út által érintett egyéb városok. A solver metódus végzi el az útvonal megkeresését a pontok, élek, valamint a start és end csúcsok alapján, majd állítja be, hogy mely csúcsok szerepelnek az útvonalon.

A keresés során nyilvántartunk egy várólistát, ahol olyan útvonalakat tárolunk, amelyek még nem jutottak el az end csúcshoz. A listának kezdetben egy útvonalat kell tartalmaznia. Ezen az útvonalon egy város szerepel, a start. A keresés addig tart, amíg ennek a listának van eleme.

Minden iterációban ki kell választani a lista utolsó elemét, ami egy félkész út, és megvizsgálni, mit tudunk vele kezdeni. A félkész út utolsó pontjáról megkeressük az összes szomszédot, ami még nem szerepel az útban. Egy szomszéd hozzáfűzése az úthoz egy új, hosszabb utat eredményez.

Amennyiben a kiválasztott szomszéd az end, úgy találtunk egy tényleges utat a start és end között. Ha ez a legrövidebb út, amit eddig találtunk, akkor el kell tárolni, egyébként nem érdekes.
Ha a szomszéd nem az end, akkor ez még mindig csak egy félkész út. Ekkor ezt a lista végéhez hozzá kell fűzni.

A fenti algoritmust ismételve a lista egy idő után üres lesz, ekkor végzett a keresés. A megtalált legrövidebb út a megoldás. Azt, hogy a keresés ténylegesen mélységi keresésként működjon, az biztosítja, hogy mindig a lista végéhez adunk hozzá, és onnan veszünk el.

« Előző | Lap eleje

4	Érdekel a mesterséges intelligencia?

"A mesterséges intelligencia kutatások célja olyan rendszerek (számítógépes programok, robotok) létrehozása, amelyek intelligens módon képesek feladatokat megoldani. Az utóbbi években egy új szemléletű, viselkedésalapú megközelítés van terjedőben, amely ezt a feladatot úgy fogalmazza meg, hogy kutatások, fejlesztések célja, hogy a feladatmegoldást olyan szereplőkkel, ágensekkel végeztesse el, amelyek az intelligens viselkedés bizonyos vonásaival rendelkeznek."

"Egy intelligens rendszer a problémamegoldás során megszerzett ismeretei alapján oldja meg az adott feladatot és megadja ennek eredményét. Egy ilyen viszonylag független, önálló egységet ágensnek tekintünk. Az ágens eredete a latin ago, agere szó, melynek elsődleges jelentése mozgásba hoz, elintéz, cselekszik. A szó alapjelentése szerint ágens lehet mindaz, ami bizonyos fokú önállósággal bír, valamilyen környezet veszi körül, továbbá ezt a környezetet érzékeli és szükség esetén környezetébe beavatkozik.

Ebben az értelemben ágensnek tekinthető egy ember, aki érzékszervei (pl. fül, szem, orr) segítségével érzékeli környezetét és különböző testrészei (pl. száj, kéz, láb) segítségével beavatkozik. Ágens lehet egy robot is, amely kamerái, szenzorai segítségével érzékel és motorokkal vezérelt beavatkozói (pl. robot karok) segítségével beavatkozik. Ágens lehet továbbá egy szoftver is, amelynél input és output adatok (kódolt bitsorozatok) formájában történik az érzékelés és a beavatkozás." ^[2]

Így tudod kipörgetni a Rubik-kockát 5 másodperc alatt.

Hasznos leírások:

Piglerné Lakner Rozália - Starkné Werner Ágnes: Ágens-technológia

« Előző | Lap eleje

5	Próbáld ki a megoldást!

A leckében tárgyaltak összefoglalásaként tekintsük át és próbáljuk ki az eredeti feladat megoldását. Az elkészült kód most már több mint 250 soros lett, ezért az áttekinthetőség biztosításának érdekében kommentek előzik meg a fontosabb tevékenységek utasításait. Figyeljük meg az elkészült metódusok felépítését, és fedezzük fel azok hívásának sajátosságait, a paraméterátadást, illetve a visszaadott értékek kezelését.

<!DOCTYPE html>
<html lang="hu">
<head>
 <title>Depth first search</title>
 <meta charset="UTF-8">
 <meta name="author" content="fj">
 
	<script>
 
// ==== Kirajzoláshoz kellő funkciók
	var Canvas2D = {
		Id: "",
		Context: null,
		Canvas: null,
		Width: 0,
		Height: 0,

		Init: function (id) {
			this.Id = id;
			this.Context = document.getElementById(id).getContext('2d');
			this.Canvas = this.Context.canvas;
			this.Width = this.Canvas.width;
			this.Height = this.Canvas.height;
		},

		DrawCircle: function (x, y, r, color) {
			if (color === 'undefined')
				color = 'black';
			Canvas2D.Context.strokeStyle = color;
			var path=new Path2D();
			path.arc(x, y, r, 0, 2 * Math.PI, false);
			Canvas2D.Context.stroke(path);
		},

		DrawDot: function (x, y, r, color) {
			if (color === 'undefined')
				color = 'black';
			Canvas2D.Context.fillStyle = color;
			var path=new Path2D();
			path.arc(x, y, r, 0, 2 * Math.PI, false);
			Canvas2D.Context.fill(path);
		},
		
		DrawLine: function (x1, y1, x2, y2, color)
		{
			Canvas2D.Context.strokeStyle = color;
			var path=new Path2D();
		  path.moveTo(x1,y1);
		  path.lineTo(x2,y2);
		  Canvas2D.Context.stroke(path);
		},

		Clear: function()
		{
			this.Context.clearRect(0, 0, this.Width, this.Height);
		}
	}
	
// ==== Itt tároljuk egy város adatait
	function City(id, x, y)
	{
		this.Id=id;
		this.X=x;
		this.Y=y;
		this.Start=false;
		this.End=false;
		this.Road=false;
	}
	
	var Game = {
		Canvas: null,
		CityCount: 10,
		CityRad: 10,
		Cities: [],
		StartCity: null,
		EndCity: null,
		Roads: [],
		Timer: null,

		Init: function (id) {
			this.Canvas = Canvas2D;
			this.Canvas.Init(id);
// ==== Készítsünk 10 várost a példához
			this.Cities[0]=new City(0,50,50);
			this.Cities[1]=new City(1,100,500);
			this.Cities[2]=new City(2,150,250);
			this.Cities[3]=new City(3,200,550);
			this.Cities[4]=new City(4,350,350);
			this.Cities[5]=new City(5,450,150);
			this.Cities[6]=new City(6,500,200);
			this.Cities[7]=new City(7,700,100);
			this.Cities[8]=new City(8,700,400);
			this.Cities[9]=new City(9,750,550);
// ==== Kezdetben az első a start, és az utolsó az end			
			this.StartCity=this.Cities[0];
			this.StartCity.Start=true;
			this.EndCity=this.Cities[9];
			this.EndCity.End=true;
			
			for (var i=0; i<this.CityCount; i++)
			{
				this.Roads[i]=new Array(this.CityCount);
				for (var j=0; j<this.CityCount; j++)
					this.Roads[i][j]=null;
			}
			
// ==== Rajzoljunk be éleket
			this.Roads[0][1]=this.Roads[1][0]=8;
			this.Roads[2][3]=this.Roads[3][2]=1;
			this.Roads[4][5]=this.Roads[5][4]=4;
			this.Roads[6][7]=this.Roads[7][6]=7;
			this.Roads[8][9]=this.Roads[9][8]=2;
			this.Roads[5][7]=this.Roads[7][5]=3;
			this.Roads[0][2]=this.Roads[2][0]=4;
			this.Roads[3][9]=this.Roads[9][3]=8;
			this.Roads[1][3]=this.Roads[3][1]=2;
			this.Roads[3][4]=this.Roads[4][3]=5;
			this.Roads[4][6]=this.Roads[6][4]=6;
			this.Roads[4][8]=this.Roads[8][4]=3;
			this.Roads[6][8]=this.Roads[8][6]=2;
			this.Roads[0][5]=this.Roads[5][0]=4;

			this.Timer = setInterval(this.Update, 50);
		},
// ==== Kirajzolás
		Draw: function () {
			Game.Canvas.Clear();
			
			for (var i=0; i<Game.CityCount-1; i++)
			{
				for (var j=i+1; j<Game.CityCount; j++)
				{
					if (Game.Roads[i][j])
					{
						var val=Game.Roads[i][j]-1;
						Game.Canvas.DrawLine(Game.Cities[i].X, Game.Cities[i].Y, Game.Cities[j].X, Game.Cities[j].Y, "rgb("+Math.floor(255*val/7)+","+Math.floor(255*(7-val)/7)+",0)");
					}
				}
			}
			
			for (var i=0; i<Game.CityCount; i++)
			{
				var color='black'
				if (Game.Cities[i].Start) color='red';
				if (Game.Cities[i].End) color='blue';
				if (Game.Cities[i].Road) color='green';
				Game.Canvas.DrawDot(Game.Cities[i].X, Game.Cities[i].Y, Game.CityRad, color);
			}

		},

		Update: function () {
			Game.Draw();
		}
	}
// ==== Itt érzékeljük, ha rákattintunk egy pontra
	function hitTest(e)
	{
		var object = e.target;
		var rectObject = object.getBoundingClientRect();
		var x=e.clientX - rectObject.left;
		var y=e.clientY - rectObject.top;
		
		
		for (var i=0; i<Game.CityCount; i++)
		{
			if ( (x-Game.Cities[i].X)*(x-Game.Cities[i].X)+(y-Game.Cities[i].Y)*(y-Game.Cities[i].Y) <= Game.CityRad*Game.CityRad )
			{
				Game.StartCity.Start=false;
				Game.EndCity.End=false;
				
				Game.StartCity=Game.EndCity;
				Game.EndCity=Game.Cities[i];
				
				Game.StartCity.Start=true;
				Game.EndCity.End=true;
				solver();
			}
		}
	}
// ==== Mélységi keresés
  function solver(){
		for (var i=0; i<Game.CityCount; i++)
		{
			Game.Cities[i].Road=false;
		}
// ==== Üres lista, majd készítünk egy félkész utat csak a start ponttal, és beletesszük
		var pathes = [];
		var singlePath=[Game.StartCity.Id];
		pathes.push(singlePath);
		var minDist=null;
		var minPath=null;
// ==== Addig dolgozunk, amíg a lista ki nem ürül
		while (pathes.length>0)
		{
// ==== A legutolsót szedjük ki
			var currentPath=pathes.pop();
			var lastCityId=currentPath[currentPath.length-1];
// ==== Meg kell nézni minden szomszédot, ahol az adott út még nem járt
			for (var i=0; i<Game.CityCount; i++)
			{
				if (Game.Roads[lastCityId][i] && currentPath.indexOf(i)==-1)
				{
					var newPath=currentPath.slice();
					newPath.push(i);
// ==== Ha elértük az end pontot, akkor találtunk egy utat, meg kell vizsgálni, hátha ez az addigi legrövidebb
					if (Game.Cities[i].End)
					{
						var dist=0;
						for (var j=0; j<newPath.length-1; j++)
						{
							dist+=Game.Roads[newPath[j]][newPath[j+1]];
						}
// ==== Ha ez a legrövidebb, akkor el kell menteni
						if (minDist===null || minDist>dist)
						{
							minDist=dist;
							minPath=newPath;
// ==== Az algoritmus ellenőrzéséhez lehet információkat kiíratni, ezt a böngészőben lehet elérni
							console.log("new dist: "+dist);
						}
					}
					else
					{
// ==== A legvégéhez adjuk hozzá
						pathes.push(newPath);
					}
				}
			}
		}
		if (minPath)
		{
			for (var i=0; i<minPath.length; i++)
			{
				var j=minPath[i];
				if (!Game.Cities[j].Start && !Game.Cities[j].End) Game.Cities[j].Road=true;
			}
		}
	}	


	</script>
	
</head>
<body>

	<section>
		<h1>Útkeresés mélységi bejárással</h1>
		
		
	<canvas id="game" width="800" height="600" style="border:1px solid #d3d3d3;" onclick="hitTest(event)">
	Your browser does not support the HTML5 canvas tag.</canvas>
	
	<script>
	Game.Init("game");
	solver();
	</script>

</body>
</html>

« Előző | Lap eleje

6	Oldd meg a feladatokat!

Kedves Bakonyi Bitfaragó Jelöltek!

Elérkeztünk az erőgyűjtés szakaszának a végéhez. Az itt szerzett ismereteket fogjátok majd alkalmazni az összemérés fordulójában. A következő erőpróbáig azonban még meg kellene oldani néhány izgalmas feladatot.

A példaként kirakott megoldás sajnos túlzottan egyszerűre sikerült, így használhatósága korlátozott. A feladat, hogy egy használhatóbb, több fukcióval rendelkező változatot elkészítsetek. A kódoláshoz bátran használjátok fel a most bemutatott programot is.

Beküldhető feladatok:

Készítsünk egy programot, amely városok közötti útvonalak tervezését szolgálja
- Készítsétek el a térképet, városokkal, és az azokat közvetlenül összekötő utakkal. Minden út egy egyenes vonal, amik egymást nem keresztezhetik. Az él súlya nem felel meg az út hosszának a térképen, hiszen a terep is módosíthatja az utazási időt, nem csak a távolság.
- Legyen lehetőség a kezdő és a végcél város kiválasztására.
- A program keresse meg a legrövidebb utat a két város között.
- A megjelenítés legyen szép, vagyis az utakon való utazási idők egyértelműen legyenek kivehetőek, és a legrövidebb út megjelenítésekor az utakat is emelje ki a program, ne csak a városokat.
- A városoknak legyen egy mérete (pl. terület, vagy lakosok száma). A térképen a nagyobb városok tűnjenek is nagyobbnak.
- A legrövidebb út megkeresése során legyen lehetőség kiválasztani egy köztes várost, amit az útvonalnak érintenie kell. Ekkor a köztes város előtti és utáni útvonalnak lehet közös része.
- A legrövidebb útvonal megkeresése után jelenjen meg az útvonal összhossza is.
1000 0000|₂ pont
Bővítsétek ki a programot, hogy különböző közlekedési eszközökre is lehessen tervezni. Minden útvonal tartalmazza, hogy lehet-e kerékpárral, személygépjárművel, vagy autóbusszal közlekedni a két város között, illetve az utazási időket minden lehetőséghez. Egy megkötés van: ha két város között van autóbusz járat, akkor személygépjárművel is van lehetőség közlekedni a két város között. A felhasználó tudja kiválasztani a közlekedés módját. Ilyenkor a program csak a megadott közlekedési lehetőségeken keresse az útvonalat. Előfordulhat, hogy két város között egyáltalán nincs útvonal a megadott feltételekkel (főleg kerékpár esetén), ekkor ezt jelezni kell. Az alapártelmezett közlekedési forma a személygépjármű legyen.
1000 0000|₂ pont

Lazításként oldjátok meg, majd töltsétek fel az alábbi gondolatébresztő feladatokat is. Lehet, hogy éppen az itt szerzett bitpoint-ok vezetnek el benneteket egyenesen a döntőig.

Beküldhető feladatok:

Az (x₁,y₁), (x₂,y₂),…,(x_n,y_n) valós értékpárok egy síkbeli, n csúcspontú konvex sokszög csúcspontjainak az óramutató járásával ellenkező irányú körüljárási sorrendben megadott koordinátái.
- Számítsátok ki a sokszög kerületét!
- Határozzátok meg a sokszög területét!
  Útmutató: Feltételezzük, hogy a sokszog az origot körbefogja. Az origót összekötve a csúcsokkal háromszögeket kapunk. Egy háromszög területét – ha az oldalakat a, b, c jelöli – a már megismert Heron képlettel számolhatjuk ki: T=Math.sqrt(s*(s-a)*(s-b)*(s-c)), ahol s=0,5*(a+b+c).
10 0000|₂ pont
Számítsátok ki egy szám négyzetgyökét Newton módszerrel. A beolvasott szám legyen A. X₁=A/2, X_n+1=(X_n+A/X_n)/2 ha n>=1. A számítást addig folytassátok, amíg |X_n+1-X_n|<0,0001. Az eredményt négy tizedes jeggyel jelenítsétek meg!
1 0000|₂ pont

« Előző | Lap eleje

3. A mélységi kereső algoritmus

Az algoritmus jellemzői

Hasznos leírások:

Hogyan alakítsuk ki a belső adatszerkezetet?

Hogyan működik a mélységi keresés?

Érdekel a mesterséges intelligencia?

Hasznos leírások:

Próbáld ki a megoldást!

Oldd meg a feladatokat!

Kedves Bakonyi Bitfaragó Jelöltek!

Beküldhető feladatok:

Beküldhető feladatok:

Hivatkozások, felhasznált források