MestInt gyakorlat visszalépéses keresés N királynő probléma Probléma leírása Az n királynő probléma, azt a kérdést veti fel, hányféleképpen lehet lerakni n darab királynőt egy n×n-es táblán úgy, hogy a sakk szabályai szerint ne üssék egymást. Forráskód using using using using using
System; System.Collections.Generic; System.Linq; System.Text; System.Threading.Tasks;
namespace Nkirálynő { class Program { public class NKirálynő { private int[] oszlopok; private int N; int megoldásokSzáma; public NKirálynő(int királynőkSzáma) { N = királynőkSzáma; oszlopok = new int[királynőkSzáma]; } private void KirálynőPozíció(int sor) { if (jónakTűnő(sor)) { if (sor == N - 1) { //Eredmény kiíratása for (int i = 0; i < N; i++) { Console.WriteLine(i + 1 + ".sor " + "
" + (oszlopok[i]+1) + ".
oszlop"); } Console.WriteLine("------------------------------"); megoldásokSzáma++; Console.WriteLine(); } else for (int j = 0; j < N; j++) { oszlopok[sor + 1] = j; KirálynőPozíció (sor + 1); } } } private bool jónakTűnő(int index) { int k = 0; bool jelölő = true; while (k < index && jelölő ) { if ((oszlopok[index] == oszlopok[k]) || (Math.Abs(oszlopok[index] - oszlopok[k]) == index - k)) jelölő = false; k++; } return jelölő; } public void királynőkElhelyezése()
1
{ // Az összes lehetséges eset feldolgozása for (int i = 0; i < N; i++) { oszlopok[0] = i; KirálynőPozíció(0); } Console.WriteLine("Megoldási lehetőségek száma: " + megoldásokSzáma); } } static void Main(string[] args) { int N = 8; NKirálynő királynők; királynők = new NKirálynő(N); Console.WriteLine(N +" kiránynő elhelyezése egy (" + N + " x " + N + ")-es sakktáblán" ); Console.WriteLine("A királynők elhelyezése: "); királynők.királynőkElhelyezése(); Console.ReadLine(); } } }
Feladat Módosítsa az előző feladatot úgy, hogy az előző n-királynő problémához hasonlóan, most úgynevezett „szuperkirálynőket” kell a táblára rakni. A szuperkirálynő léphet úgy, mint egy klasszikus sakkbeli királynő (vízszintes, függőleges, átlós), és tud ugrani, mint a huszár.
2
Hamilton kör Probléma leírása Definíció: Egy G gráfban Hamilton-körnek nevezünk egy kört, ha a gráf összes pontját tartalmazza. Egy utat Hamilton-útnak nevezünk, ha a gráf összes pontját tartalmazza. Felmerülő kérdések Adott egy G gráf. Hogyan dönthető el, hogy G-ben van-e Hamilton-kör? Ha van benne, hogyan található meg egy? Ha nincs, akkor mi akadályozza meg? https://www.cs.sunysb.edu/~skiena/combinatorica/animations/ham.html Egy útvonal nem Hamilton kör, -
ha az összes N csúcson át vezető út után nem kerülünk vissza a kezdeti csúcsba, ha bármely (0 < i < N) csúcsból nem vezet él útVonal[i-1] -ből útVonal[i] – be, ha az útvonal kört tartalmaz. Egyik él sem szerepelhet az útvonalban kétszer kivéve az elsőt és az utolsót.
Reprezentáció - szomszédsági mátrix Legyen G=(V,E) véges gráf, és n a csúcsok száma. Ekkor a gráfot egy n x n –es mátrixban ábrázoljuk, ahol az oszlopokat és a sorokat rendre a csúcsokkal indexeljük. Egy mezőben akkor van 1-es, ha a hozzá tartozó oszlop által meghatározott csúcs szomszédja a sor által meghatározott csúcsnak. Azaz 0, ℎ𝑎 (𝑖, 𝑗) ∉ 𝐸 𝐴[𝑖, 𝑗] = { 1, ℎ𝑎 (𝑖, 𝑗) ∈ 𝐸 pl.
Irányítatlan gráf esetén: 0 1 1 0 (0
1 0 1 1 1
1 1 0 1 0
0 1 1 0 1
Irányított gráf esetén:
0 1 0 1 0)
0 0 0 0 (0
3
1 0 0 0 0
1 1 0 0 0
0 1 1 0 1
0 1 0 0 0)
Forráskód using using using using using
System; System.Collections.Generic; System.Linq; System.Text; System.Threading.Tasks;
namespace HamiltonKör { class Program { public class HamiltonBacktrack { private int[][] M; private int[] útVonal; private int N;
//a szomszédsági mátrix reprezentálásához //útvonal //csúcsok száma
public HamiltonBacktrack(int[][] G) { M = G; N = M.Length; útVonal = new int[N + 1]; } private void hamilton(int index) { if (jónakTűnő(index)) { if (index == N -1) { //Eredmény kiíratása útVonal[index+1] = útVonal[0]; //kezdeti csúcs hozzáadása a végéhez Console.WriteLine("Megoldás:"); for (int i = 0; i <= N; i++) Console.WriteLine(" " + útVonal[i]); Console.WriteLine("" ); } else for (int j = 0; j < N; j++) { //Az összes csúcs kipróbálása, mint lehetséges következő csúcs útVonal[index+1] = j; hamilton(index+1); } } } private bool jónakTűnő(int index) { if (index == 0) return true; if (index == N - 1 && M[útVonal[index]][útVonal[0]] == 0) return false; if (index > 0 && M[útVonal[index - 1]][útVonal[index]] == 0) return false; int j = 0; while (j < index && útVonal[index] != útVonal[j]) j++; return (j == index); } public void hamiltonÚtVonal(int startCsúcs) { útVonal[0] = startCsúcs; hamilton(0); } } static void Main(string[] args) { int[][] Matrix = new int[4][]; Matrix[0] = new int[] { 0, 1, 0, 1}; Matrix[1] = new int[] { 1, 0, 1, 0}; Matrix[2] = new int[] { 0, 1, 0, 1}; Matrix[3] = new int[] { 1, 0, 1, 0}; Console.WriteLine("Hamilton kör"); Console.WriteLine("------------"); HamiltonBacktrack gráf; gráf = new HamiltonBacktrack(Matrix);
4
gráf.hamiltonÚtVonal(0); Console.ReadLine(); } } }
5
0-1 Hátizsák probléma Probléma leírása Adott egy K kapacitású hátizsák (a turista egy bizonyos tömegnél nem tud többet elvinni), N darab tárgy, amelyek tömege m1, m2,...mN, értéke (hasznossága) pedig e1, e2,…en. Szeretnénk a legtöbb értéket bepakolni a hátizsákba, anélkül, hogy túllépnénk a hátizsák kapacitását. Ha az összes tárgy nem fér a hátizsákba akkor a turista kénytelen szelektálni és a válogatást úgy végzi, hogy a súlykorlátozás betartása mellett a magával vitt tárgyak összértéke (összhasznossága) minél nagyobb legyen. A válogatást tárgyanként egy vagy értéket felvehető döntési változóval írhatjuk le. Legyen a döntési változó a , amelynek értéke legyen , ha a -edik tárgyat a turista beteszi a hátizsákjába, ill. értéke legyen , ha a -edik tárgyat nem teszi be a hátizsákjába. A
mutatja a hátizsákba behelyezett tárgyak összsúlyát, a
pedig a hátizsákba behelyezett tárgyak összértékét. Így a fenti probléma matematikai megfogalmazása a következő: Adott a és a
szám, amelyek pozitív egészek és
vektor
.
-------------------------------------------------------------------------------------K a hátizsák kapacitása értékSűrűség = ei/mi A tárgyakat ennek megfelelően csökkenő sorrendbe kell rendezni teljesMéret= aktMéret + ∑𝑘−1 𝑗=𝑖+1 𝑚𝑖 maxLehetségesÉrték = aktÉrték + ∑𝑘−1 𝑗=𝑖+1 𝑒𝑖 + (K – teljesMéret * (ek/mk) Tesztadatok: K = 16 n = 4 i
ei
1 2 3 4
45 30 45 10
Ft Ft Ft Ft
6
mi
ei/mi
3 5 9 5
15 Ft 6 Ft 5 Ft 2 Ft
Kezdetben: teljesMéret = 0 + s1 + s2 = 0 + 3 + 5 = 8 maxLehetségesÉrték = 0 + v1 + v2 + (K – teljesMéret) * (e3/m3) = 0 + 45Ft + 30Ft + (16-8) * (5Ft) = 75Ft + 40Ft = 115Ft Következő szint?
Forráskód using using using using using
System; System.Collections.Generic; System.Linq; System.Text; System.Threading.Tasks;
namespace ConsoleApplication5 { class Program { public class HátizsákBacktrack { private double maxÉrték; // A hátizsákba pakolható tárgyak maximális értéke... private double Kapacitás; //Hátizsák kapacitása... private double[] méretek; //Tárgyak méretei (növekvő sorendben kell megadni az értékeket) private double[] értékek; //Tárgyak értékei... private LinkedList
bepakoltTárgyakListája; //A belepakolt tárgyak listája... private int tárgyakSzáma; //Tárgyak száma... public HátizsákBacktrack(double kapacitás, double[] méret, double[] érték, int tárgyakSz) { maxÉrték = 0.0; Kapacitás = kapacitás; méretek = méret; értékek = érték; tárgyakSzáma = tárgyakSz; bepakoltTárgyakListája = null; } private void hátizsák(int index, double aktMéret, double aktÉrték, LinkedList aktLista) { if (aktMéret <= Kapacitás && aktÉrték > maxÉrték) { maxÉrték = aktÉrték; LinkedList bepakoltTárgyakListája = new LinkedList(aktLista); } if (jónakTűnő(index, aktMéret, aktÉrték)) { LinkedList balLista = new LinkedList(aktLista); LinkedListNode csúcs = new LinkedListNode(index + 1); bepakoltTárgyakListája = balLista; balLista.AddLast(csúcs); hátizsák(index + 1, aktMéret + méretek[index+1], aktÉrték + értékek[index+1], balLista); LinkedList jobbLista = new LinkedList(aktLista); hátizsák(index + 1, aktMéret, aktÉrték, jobbLista); } } private bool jónakTűnő(int tárgy, double méret, double érték) { double maxLehetségesÉrték = érték; double teljesMéret = méret; int k = tárgy + 1;
7
Console.Write((tárgy + 1) +". lépés " + " " + méret + " " + érték + " ; " ); Console.WriteLine(""); if (méret > Kapacitás) return false; while (k < tárgyakSzáma && teljesMéret + méretek[k] <= Kapacitás) { maxLehetségesÉrték += értékek[k]; teljesMéret += méretek[k]; k++; } if (k < tárgyakSzáma) maxLehetségesÉrték += (Kapacitás - teljesMéret) * (értékek[k] / méretek[k]); return maxLehetségesÉrték > maxÉrték; } public void megoldásKeresése() { LinkedList aktLista = new LinkedList(); hátizsák(0, 0.0, 0.0, aktLista); Console.WriteLine(" "); Console.WriteLine("Belepakolt elemek:"); for (int i = 0; i < bepakoltTárgyakListája.Count(); i++) { Console.WriteLine(" " + bepakoltTárgyakListája.ElementAt(i) + ". tárgy "); } Console.WriteLine("A hátizsákba pakolható tárgyak értéke $" + maxÉrték); } static void Main(string[] args) { double[] Méretek = new double[4]; double[] Értékek = new double[4]; Méretek[0] = 3; Méretek[1] = 5; Méretek[2] = 5; Méretek[3] = 9; Értékek[0] = 45; Értékek[1] = 30; Értékek[2] = 10; Értékek[3] = 45; int Kapacitás = 16; int tágyakSzáma = Értékek.Length; HátizsákBacktrack hátiZsák; hátiZsák = new HátizsákBacktrack(Kapacitás,Méretek,Értékek,tágyakSzáma); Console.WriteLine("Próbálkozások: "); Console.WriteLine("--------------------------------------"); hátiZsák.megoldásKeresése(); Console.ReadLine(); } } } }
Feladat:
8
