Prohledávání stavového prostoru
Napsal: 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...
nějaká reprezentace možností: napustit, vypustit, přelit:
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
Dalsi podpurne funkce - pro praci s hashem, a struktura pro vytvoreni stavoveho prostoru - orientovany graf.
V informovanem hledani pouzivame prioritni frontu podle nejakeho ohodnoceni, ja jsem pouzil celkem jednoduchou nasledujici funkci:
a vlastni main: - je tam natvrdo zadratovanej koncovej stav - tedy stav kam se snažíme dostat.
myslim ze kod je celkem samovysvetlujici...
jen vypichnu:
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
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