400 Bad Request

Bad Request

Your browser sent a request that this server could not understand.

Prohledávání stavového prostoru

Prohledávání stavového prostoru

Příspěvekod Ariczek » 23 říjen 2011 21:49:35

Jedná se o problémy, kdy se algoritmicky snažíme najít řešení nějakého problému. Například umělá inteligence ve hrách - dáma, šachy a podobně.
Studijní materiál: http://cs.wikipedia.org/wiki/Prohled%C3 ... o_prostoru

Ukážeme si informované i neinformované prohledávání.

Na čem si to ukážeme: Jeden celkem jednoduchý problém je tzv.problém kýblů: kdo viděl smrtonosnou past 3, je to ta scéna, kdy mají kýbl 5 litrů, kýbl 3 litry, a potřebují přesně 4 litry.

Obecnější definice:

Základní problém je definován takto: K dispozici jsou dva kýble (předem daných obecně rozdílných objemů), vodovodní kohoutek a kanál. Na počátku jsou oba kýble prázdné. Vaším úkolem je docílit toho, aby v jednom kýblu byla voda o předem stanoveném objemu, přičemž můžete pouze naplnit plný kýbl z kohoutku, vylít celý kýbl do kanálu a přelít jeden kýbl do druhého tak, aby druhý kýbl nepřetekl.

Nechá se to zobecnit, aby to nebyla taková nuda (přeci jen 2 kýble vyřeší každej za chvilku i na papíru, na to nepotřebujete počítač :)

Problém lze zobecnit tím, že připustíme užití většího počtu kýblů, aby na počátku řešení byla v kýblech nějaká voda, a že předepíšeme koncový objem vody v každém kýblu.

Takže jak tedy na to ?

includy a prototyp fce...
Kód: Vybrat vše
#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
int* rehash(int);


nějaká reprezentace možností: napustit, vypustit, přelit:

Kód: Vybrat vše
enum ADD {
   AKCE_NAPUSTIT = 0,
   AKCE_VYLEJT = 1,
   AKCE_PRELEJT = 2,
};
struct choice {
   int operace; // obsahuje ADD Enum
   int i;       // prvni operand - zdrojovy kybl
   int j;       // v pripade napustit a vylejt -1, jinak druhy operand - cilovy kybl
   int mnozstvi; // mnozstvi vody
};


tak, ted nejaka reprezentace celeho naseho problemu:
kostruktor ma v sobe natvrdo zadratovane jedno zadani - kapacity kyblu..., pocatecni stav
getOptions slouzi k expanzi - ziskani vsech stavu, do kterych se dostanu z tohoto stavu jednou akci.
makeHash vychazi z toho, ze maximalni kapacita kyblu je 14, takže se do 20ti vejdu, a muzu zakodovat 5 cisel do jednoho pres nasobeni 20ti

Kód: Vybrat vše
struct kyble {
   int pocetKyblu;
   int* kapacita;
   int* current;
   kyble() {
      pocetKyblu = 5;
      kapacita = new int[5];
      kapacita[0] = 14;
      kapacita[1] = 10;
      kapacita[2] = 12;
      kapacita[3] = 3;
      kapacita[4] = 8;
      current = new int[5];
      current[0] = 0;
      current[1] = 0;
      current[2] = 0;
      current[3] = 0;
      current[4] = 0;
   }
   ~kyble() {
      delete[] kapacita;
      delete[] current;
      kapacita = 0;
      current = 0;
      pocetKyblu = 0;
   }
   int makeHash() {
      int hash = current[0] + 20*(current[1]+20*(current[2] + 20* (current[3]+20*current[4])));
      return hash;
   }
   void loadHash(int hash) {
      int* pomoc = rehash(hash);
      current[0] = pomoc[0];
      current[1] = pomoc[1];
      current[2] = pomoc[2];
      current[3] = pomoc[3];
      current[4] = pomoc[4];
      delete[] pomoc;
   }
   queue<choice>* getOptions() {
      queue<choice>* fronta = new queue<choice>();
      choice ch;
      for (int i = 0; i < 5; i++) {
         for (int j = 0; j < 5; j++) {
            if (i!=j) {     // handlovani prelejvani vody z kyblu i do j
               if (current[j]<kapacita[j] && current[i]>0) {
                  ch.i = i;
                  ch.j = j;
                  ch.operace = AKCE_PRELEJT;
                  ch.mnozstvi = min(kapacita[j]-current[j],current[i]);
                  fronta->push(ch);
               }
            } else if (j==i) {     // handlovani napusteni ci vypusteni kyble i
               if (current[i] < kapacita[i]) {
                  ch.i = i;
                  ch.j = -1;
                  ch.operace = AKCE_NAPUSTIT;
                  ch.mnozstvi = kapacita[i]-current[i];
                  fronta->push(ch);
               }
               if (current[i] > 0) {
                  ch.i = i;
                  ch.j = -1;
                  ch.operace = AKCE_VYLEJT;
                  ch.mnozstvi = current[i];
                  fronta->push(ch);
               }
            }
         }
      }
      return fronta;
   }
   kyble* createNewState(choice* ch) {
      kyble* k = new kyble();
      k->current[0] = current[0];
      k->current[1] = current[1];
      k->current[2] = current[2];
      k->current[3] = current[3];
      k->current[4] = current[4];
      switch (ch->operace) {
            case AKCE_NAPUSTIT:
               k->current[ch->i] += ch->mnozstvi;
               break;
            case AKCE_VYLEJT:
               k->current[ch->i] -= ch->mnozstvi;
               break;
            case AKCE_PRELEJT:
               k->current[ch->i] -= ch->mnozstvi;
               k->current[ch->j] += ch->mnozstvi;
               break;
      }
      return k;
   }

};


Dalsi podpurne funkce - pro praci s hashem, a struktura pro vytvoreni stavoveho prostoru - orientovany graf.

Kód: Vybrat vše
struct uzel
{
   kyble* stav;
   choice odkud;
};

void vypishash(int hash) {
   int * a = rehash(hash);
   cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << " " << a[4] << endl;
}

int* rehash(int hash) {
   int* a = new int[5];
   a[0] = hash % 20;
   hash = (hash-a[0]) / 20;
   a[1] = hash % 20;
   hash = (hash - a[1]) / 20;
   a[2] = hash % 20;
   hash = (hash - a[2]) / 20;
   a[3] = hash % 20;
   a[4] = (hash - a[3]) / 20;
   return a;
}


V informovanem hledani pouzivame prioritni frontu podle nejakeho ohodnoceni, ja jsem pouzil celkem jednoduchou nasledujici funkci:

Kód: Vybrat vše
// funktor pro priority queue
struct Greater {
   bool operator()(kyble* x, kyble* y) {
      int koneck[5] = {7,0,7,0,7};
      int xw = 0;
      int yw = 0;
      for (int i = 0; i < 5; i++) {
         for (int j = 0; j < 5; j++) {
            if (i!=j) {
               if (x->current[i] == koneck[j]) xw+=1;
               if (y->current[i] == koneck[j]) yw+=1;
            }
         }
         if (x->current[i] == koneck[i])   xw+=3;
         if (y->current[i] == koneck[i]) yw+=3;
      }
      return yw > xw;
   }
};


a vlastni main: - je tam natvrdo zadratovanej koncovej stav - tedy stav kam se snažíme dostat.

Kód: Vybrat vše
int main(int argc, char* argv[]) {

   // 1 - nastaveni OPEN{S0} a CLOSED{}
   int koneck[5] = {7,0,7,0,7};
   int konec = koneck[0] + 20*(koneck[1]+20*(koneck[2] + 20* (koneck[3]+20*koneck[4])));
   int count = 0;
   set<int> open;
   set<int> closed;
   set<int>::iterator it;
   map<int,int> predci;
   //queue<kyble*>* openq = new queue<kyble*>();
   priority_queue< kyble*, vector<kyble*>, Greater >* openq = new priority_queue< kyble*, vector<kyble*>, Greater >();
   //stack<kyble*>* openq = new stack<kyble*>();
   queue<choice>* q;
   kyble* k = new kyble();
   int start = k->makeHash();
   kyble* help;
   open.insert(k->makeHash()); // pridani uvodniho uzlu do OPEN
   openq->push(k);
   if (start == konec) {
      cout << "Stratovni stav je roven cilovemu, ukoncuji..." << endl;
                delete k;
                delete openq;
      return 0;
   }
   while (true)
   {
      if (openq->empty()) { // krok 2
         cout << "Nepodarilo se najit cestu k reseni..." << endl;
         return 1;
      }
      k = openq->top(); // krok 3 - vyber prvni stav z open - dej ho do closed
      openq->pop();
      int predek = k->makeHash();
      open.erase(predek);
      closed.insert(predek);
      
      count++;
      q = k->getOptions();      // krok 4 - expanduj

      while (!q->empty()) {
         choice c = q->front();
         //cout << c.operace << " " << c.i << " " << c.j << " " << c.mnozstvi << endl;
         help = k->createNewState(&c);
         int hash = help->makeHash();
         if (hash == konec) {   // krok 5 - porovnani s koncovym hashem
            predci.insert(pair<int,int>(hash,predek));
            cout << "Podarilo se dorazit k cili" << endl;
            cout << "Pocet kroku: " << count << endl;
            count = 1;
            vypishash(hash);
            while(predci[hash] != start) {
               hash = predci[hash];
               vypishash(hash);
               count++;
            }
            vypishash(predci[hash]);
            cout << "Delka cesty: " << count << endl;
            return 0;
         }
         if (open.find(hash) == open.end() && closed.find(hash) == closed.end()) {
            predci.insert(pair<int,int>(hash,predek));
            open.insert(hash);
            openq->push(help);
         }
         q->pop();
      }

   }
}


myslim ze kod je celkem samovysvetlujici...
jen vypichnu:

Kód: Vybrat vše
//queue<kyble*>* openq = new queue<kyble*>();
   priority_queue< kyble*, vector<kyble*>, Greater >* openq = new priority_queue< kyble*, vector<kyble*>, Greater >();
   //stack<kyble*>* openq = new stack<kyble*>();


Tady se lame chleba o jaky algoritmus pujde! pri pouziti queue (1 radek) by slo o BFS - prohledávání do šířky, při použití stack (3 řádek) by šlo prohledávání do hloubky - DFS.
a pouze priority queue je informované hledání.

Tedy všechny tyhle algoritmy se liší jen tím, jak vybrat který uzel stavového prostoru budu prohledávat dále ? nejstarší (BFS), nejnovější (DFS), nebo něco mezi (informované) ? :)

Ariczek
Ariczek
 
Příspěvky: 51
Registrován: 21 říjen 2011 10:54:52

Re: Prohledávání stavového prostoru

Příspěvekod Wlezley » 24 říjen 2011 20:33:04

Ano, o těch "kýblech" jsme si povídali na WC IRC, totiž myslím WS IRC. :thumbup:
Uživatelský avatar
Wlezley
 
Příspěvky: 316
Registrován: 24 září 2011 22:54:46
Bydliště: Plzeň
Projekt: Wlezley EU

Re: Prohledávání stavového prostoru

Příspěvekod Ariczek » 24 říjen 2011 22:53:01

Wlezley píše:Ano, o těch "kýblech" jsme si povídali na WC IRC, totiž myslím WS IRC. :thumbup:


njn, nesmis hledat nelogicnost v zadani, ci si ho nejak upravovat, ale premejslet nad tim jak ho vyresit :D :D
Ariczek
 
Příspěvky: 51
Registrován: 21 říjen 2011 10:54:52

Re: Prohledávání stavového prostoru

Příspěvekod Wlezley » 26 říjen 2011 17:57:12

Jistě, ale když je to spatně podaný, tak se to jen těžko chápe. ;)
Uživatelský avatar
Wlezley
 
Příspěvky: 316
Registrován: 24 září 2011 22:54:46
Bydliště: Plzeň
Projekt: Wlezley EU


Zpět na C/C++

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 3 návštevníků


cron