Průchod bludištěm - Theseus

Algoritmy Bludiště Průchod bludištěm - Theseus

Vyřešit problém bludiště musel již v řecké mytologii Theseus, který se vydal do labyrintu zabít Minotaura. V tomto úkolu mu pomohla Ariadna, která se do Thésea zamilovala. Před vstupem do labyrintu mu dala klubko nití, které Théseus za sebou rozmotával. To by mu pomohlo se jistě z labyrintu vrátit (pokud by přežil souboj s Minotaurem), ale nezajistilo by mu to nalezení Minotaurova úkrytu v bludišti. K tomu potřeboval něco jako křídu, aby si mohl označit vchody (dveře) do místností v kterých již byl.

Algoritmus je prostý. Jít náhodně někam, kde jsem ještě nebyl. Zde postupuji sever, východ, jih a západ. Pokud jsem v místnosti, odkud vedou již jen mnou označené dveře (již jsem v nich byl), namotávám nit a vracím se tak dlouho, dokud neobjevím neoznačený vchod a do něho se vydám. Tento algoritmus mi zajistí nalezení Minotaura i to, že se případně vrátím. Natažená nit (seznam místností) je výsledek.

Výsledkem tedy není nejkratší cesta, ale jedna z možných. Pro nalezení nejkratší cesty musíme použít jiný algoritmus (vlnu).

V našem programu je nit realizována zásobníkem třídy Stack. Rozbalení nitě představuje metoda Push(místnost), kde parametrem je právě navštívená místnost, kterou vložíme do zásobníku. Namotávání nitě provedeme pomocí metody Pop(), pomocí níž mažeme poslední místnost ze zásobníku. Označení navštívených místností jsem provedl tak, že místnost označím hvězdičkou. Bludiště jsem vytvořil jako textový soubor blud.txt, obsahující 5x5 místností, kde každá místnost je řetězec pěti znaků, například: v↑→00 Tato místnost vyjadřuje, že je v ní vchod (písmeno v), a že z ní vedou vchody na sever (nahoru) a na východ (doprava). Místnost s Minotaurem vypadá takto: m00↓←.

Vchody jsou uspořádány: ↑→↓← Nula znamená žádný vchod. Místnosti jsou odděleny mezerou. Navštívenou místnost označím tak, že změním první nulu na hvězdičku.

Tady je celé bludiště:

00→↓0 00→↓← 00→↓← 00→0← 0000←
0↑→↓0 0↑0↓← 0↑000 00→↓← 0↑00←
0↑0↓0 0↑0↓0 000↓0 0↑→↓0 m00↓←
0↑→00 00→↓← 0↑→↓← 0↑00← 0↑0↓←
v↑→00 0↑00← 0↑→00 0↑00← 0↑000

Zde je základní kostra programu. Celý kód si můžete stáhnout jako soubor Bludiste.cs.

using System.IO;
using System.Collections;
using System.Drawing;
using System.Reflection;

class Bludiste
{
    private static string[,] bludiste = new string[5, 5];
    private static Stack nit = new Stack();
    private static bool existDvere;

    #region nacteni ze souboru
        private static void nactiBludiste(bool zeSouboru)
    {
        if (zeSouboru)
        {
            // Textový soubor můžeme umístit k exe souboru bin\Debug
            //string path = "blud.txt";

            // Zde je součástí Solution
            string path =                         Path.Combine(Directory.GetParent(System.IO.Directory.GetCurrentDirectory()).Parent.FullName, @"Data\blud.txt");

            try
            {
                using (StreamReader sr = new StreamReader(path))
                {
                    bool pokracovat = true;

                    for (int j = 0; j < 5; j++)
                    {
                        string radek = sr.ReadLine();
                        int cz = 0;
                        for (int i = 0; i < 5; i++)
                        {
                            while (pokracovat)
                            {
                                char znak = radek[cz];
                                bludiste[i, j] = bludiste[i, j] + znak;
                                if (znak == ' ') { pokracovat = false; cz--; }
                                cz = cz + 1;
                            }
                            cz = cz + 1;
                            pokracovat = true;
                            Console.Write(bludiste[i, j] + ' ');
                        }
                        Console.WriteLine();
                    }
                    Console.WriteLine();
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("Došlo k chybě: {0}", e.ToString());
                Console.ReadKey();
            }
        }
        else
        {
            Console.WriteLine();
            Console.WriteLine("Místnosti označené hvězdičkou byly navštíveny");
            Console.WriteLine();
            for (int j = 0; j < 5; j++)
            {
                for (int i = 0; i < 5; i++)
                {
                   Console.Write(bludiste[i, j] + ' ');
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }
    #endregion

    #region nalezení počátku
        private static Point najdiPocatek()
    {
        Point bunka = new Point() ;

        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                if (bludiste[i, j].Substring(0, 1) == "v")
                {
                   bunka.X = i;
                   bunka.Y = j;
                }
            }
        }
        return bunka;
    }
    #endregion

    #region Hledání cesty
        private static bool cestaNaSever(Point bunka)
    {
        bool moznost = false;
        int i = bunka.X;
        int j = bunka.Y;
        if (bludiste[i , j].Substring(1, 1) == "↑" && bludiste[i, j-1].Substring(0, 1) != "*"
            && bludiste[i, j-1].Substring(0, 1) != "v")
        {
            moznost = true;
        }
        return moznost;
    }

        //Podobně další směry

        private static void hledejCestu(Point vstupDoBludiste)
    {
        nit.Push(vstupDoBludiste);
        Point aktualniKomnata = vstupDoBludiste;
        int i;
        int j;
        bool nalezen = false;
        while (!nalezen)
        {
            //Console.WriteLine(aktualniKomnata);
            existDvere = false;
            aktualniKomnata = (Point)nit.Peek();
            if (cestaNaSever(aktualniKomnata))
            {
                existDvere = true;
                aktualniKomnata = (Point)nit.Peek();
                i = aktualniKomnata.X;
                j = aktualniKomnata.Y;
                j--;
                if (bludiste[i, j].Substring(0, 1) == "m") { nalezen = true; }
                else
                {
                    string obsahKomnaty = bludiste[i, j];
                    obsahKomnaty = obsahKomnaty.Remove(0, 1);
                    obsahKomnaty = obsahKomnaty.Insert(0, "*");
                    bludiste[i, j] = obsahKomnaty; //nahradí 0 znakem * - označení přítomnosti v komnatě
                }
                aktualniKomnata.X = i;
                aktualniKomnata.Y = j;
                nit.Push(aktualniKomnata);
                //Console.Write(aktualniKomnata + " ");
                continue;
            }

            if (cestaNaVychod(aktualniKomnata))
            {
                existDvere = true;
                aktualniKomnata = (Point)nit.Peek();
                i = aktualniKomnata.X;
                j = aktualniKomnata.Y;
                i++;
                if (bludiste[i, j].Substring(0, 1) == "m") { nalezen = true; }
                else
                {
                    string obsahKomnaty = bludiste[i, j];
                    obsahKomnaty = obsahKomnaty.Remove(0, 1);
                    obsahKomnaty = obsahKomnaty.Insert(0, "*");
                    bludiste[i, j] = obsahKomnaty; //nahradí 0 znakem * - označení přítomnosti v komnatě
                }


                aktualniKomnata.X = i;
                aktualniKomnata.Y = j;
                nit.Push(aktualniKomnata);
                //Console.Write(aktualniKomnata + " ");
                continue;
            }
                // Další směry jsou stejné

    #endregion

    #region vypisNit
    #endregion

    public static void Main()
    {
        nactiBludiste(true);
        Point vstupDoBludiste = najdiPocatek();
        hledejCestu(vstupDoBludiste);
        vypisNit(nit);
        nactiBludiste(false);
        Console.ReadKey();
    }
}

 

Stáhnout

Staženo 30x (11.85 kB)
Aplikace je včetně zdrojových kódů

 

  Aktivity (1)

Článek pro vás napsal Miloslav Šmíd
Avatar
Autor je učitelem matematiky, fyziky a programování na SSIŠ Dvůr Králové nad Labem.

Jak se ti líbí článek?
Celkem (1 hlasů) :
55555


 


Miniatura
Všechny články v sekci
Algoritmy pro bludiště

 

 

Komentáře

Avatar
Ondřej Langr (andysekcze):

Pouzivej kratsi zapis kupr. cz += 1; ;-)

Odpovědět  -5 22.7.2015 22:59
I have a charger. I have Note 7. Umh I haven't Note7.
Avatar
hanpari
Redaktor
Avatar
Odpovídá na Ondřej Langr (andysekcze)
hanpari:

Mínus za to, že komenuješ takovou ptákovinu. To ti opravdu stálo za to? Přijde mi, že jsi musel připomínkovat za každou cenu. A navíc, používáš PHP a nestydíš se za to :)

 
Odpovědět  +1 23.7.2015 9:45
Avatar
Odpovídá na hanpari
Ondřej Langr (andysekcze):

1.A webový aplikace mám dělat v čem ? C#/Java ? Proč bych to dělal? A v čem pak děláš ty? 2. Já to psal jen jako možnost jak to zkrátit ;-)

Odpovědět  -2 23.7.2015 10:05
I have a charger. I have Note 7. Umh I haven't Note7.
Avatar
Ondřej Langr (andysekcze):

Ale nehádejme se u určitě skvělé hry ;-)

Odpovědět  -2 23.7.2015 10:11
I have a charger. I have Note 7. Umh I haven't Note7.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Ondřej Langr (andysekcze)
David Čápka:

Když už, tak cz++. Ale jak již bylo řečeno, nechápu význam komentáře k algoritmu, kde řešíš 2 znaky v kódu navíc s identickou funkčností 8-|

Edit: Vidím, že sis to navíc zřejmě ani nepřečetl, když píšeš, že to je hra...

Editováno 23.7.2015 10:17
Odpovědět  +5 23.7.2015 10:16
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
mnauik
Člen
Avatar
mnauik:

Proč ne, programování je zábavné.... jako hra :D (A ne, nejsem na jeho straně :-P )

Odpovědět  +2 23.7.2015 13:04
minusuj mě, ale zdůvodni to ;)
Avatar
lastp
Redaktor
Avatar
lastp:

Proč autor článku tak jednoduchý algoritmus naprogramoval tak složitě ?
Zkusil jsem si to také a můj program má jen 78 řádek:

using System;
using System.Collections.Generic;
using System.Drawing;
using System.IO;
using System.Linq;

class Bludiste
{
    const int Width = 5, Height = 5;
    private static string[,] bludiste = new string[Width, Height];
    private static Stack<Point> nit = new Stack<Point>();
    private static Point vstupDoBludiste;
    private static Point[] Offset = new[] { new Point(0, -1), new Point(1, 0), new Point(0, 1), new Point(-1, 0) };

    static void nactiBludiste()
    {
        using (StreamReader sr = new StreamReader(@"..\..\Data\blud.txt"))
        {
            for (int j = 0; j < Height; j++)
            {
                string[] radek = sr.ReadLine().Split(' ');
                for (int i = 0; i < Width; i++)
                {
                    bludiste[i, j] = radek[i];
                    if (radek[i][0] == 'v') vstupDoBludiste = new Point(i, j);
                }
            }
        }
    }

    static void vypisBludiste()
    {
        for (int j = 0; j < Height; j++)
        {
            for (int i = 0; i < Width; i++)
                Console.Write(bludiste[i, j] + ' ');
            Console.WriteLine();
        }
        Console.WriteLine();
    }

    static void hledejCestu()
    {
        nit.Push(vstupDoBludiste);
        for (; ; )
        {
            Point aktualniKomnata = nit.Peek();
            for (int k = 0; k < 4; k++)
            {
                int i = aktualniKomnata.X, j = aktualniKomnata.Y;
                if (bludiste[i, j][k + 1] != '0')
                {
                    i += Offset[k].X; j += Offset[k].Y;
                    char znak = bludiste[i, j][0];
                    if (znak != '*' && znak != 'v')
                    {
                        nit.Push(new Point(i, j));
                        if (znak == 'm') return;
                        bludiste[i, j] = '*' + bludiste[i, j].Substring(1);
                        break;
                    }
                }
                if (k == 3) nit.Pop();
            }
        }
    }

    public static void Main()
    {
        nactiBludiste();
        vypisBludiste();
        hledejCestu();
        Console.Write("Cesta k Minotaurovi: ");
        foreach (Point p in nit.Reverse()) Console.Write("{0}, ", p);
        Console.WriteLine("\r\n\r\nMístnosti označené hvězdičkou byly navštíveny\r\n");
        vypisBludiste();
    }
}
 
Odpovědět 2.8.2015 12:01
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 7 zpráv z 7.