18 maja 2007
Metody i algorytmy sztucznej inteligencji
Program rozwiązujacy krzyżówkę korzystając z Internetu
Wykonali:
Łukasz Dawidowicz 133068
Sebastian Wieczorek 128498
Prowadzący:
dr inż. Witold Paluszyński
Spis treści
1. Wstęp
2. Prezentacja projektu
3. Algorytm działania
4. Implementacja
5. Przykłady działania
6. Wnioski
7. Materiały
|
1. Wstęp
Bardzo często mamy problemy rozwiązując krzyżówkę z przeróżnych gazet, więc opracowaliśmy super wymiatający program który właśnie rozwiązuje ten nurtujący nas problem. Zwykle człowiekowi trudno jest znaleźć konkretne informacje, a jak ma to zrobić komputer?
Problem ten wydaje się trudny, jednak nie niemożliwy do rozwiązania. W dalszej części sprawozdania postaramy się o przedstawienie algorytmu rozwiązania tego problemu.
Nasze testy przeprowadziliśmy w oparciu o "300 krzyżówek panoramicznych".
Powrót do Spisu treści
2. Prezentacja projektu
Celem naszego projektu jest napisanie programu
do rozwiązywania krzyżówki panoramicznej. Program wyszukuje hasła w Internecie na stronie www.krzyżówki.info, Wikipedi oraz na podstawie kilku znanych liter.
Rozwiązywanie krzyżówki będzie polegało na wyszukaniu na początku w krzyżówce najdłuższego hasła, sprawdzeniu jakie jest do niego zapytanie i na zasadzie wyszukania w pytaniu słów kluczowych zostanie przeszukanie na początku w naszej bazie hasła a jeżeli się to nie powiedzie (hasło nie zostanie odnalezione) to odniesie się np. Wikipedi i to pominie to hasło i po zakończeniu rozwiązywaniu reszty haseł dopasuje odpowiednie słowa na podstawie wygenerowanych liter.
Dane do krzyżówki weźmiemy z podanych stron internetowych jak również z
"Rozrywka" magazyn dla krzyżówkowiczów dostępnej w kiosku.
Ocena czy program działa poprawnie polega na porównaniu rozwiązanej
krzyżówki z wzorcem krzyżówki z np. gazetki.
a program napisany w języku PHP.
Powrót do Spisu treści
3. Algorytm działania
Program po uruchomieniu wczytuje krzyżówkę z pliku tekstowego o odpowiednim formacie zapisu:
- W pliku znajdują się zarówno pytania jaki i układ krzyżówki.
- Następnie wyszukuje najdłuższe hasła i jeżeli znajdzie jednoznaczna odpowiedź zostanie ona wstawiona do krzyżówki, jeżeli odpowiedź nie jest jednoznaczna program sprawdza ją pod względem znaczeniowym na Wikipedi (sporządza odpowiednie zapytanie i wylicza sobie prawdopodobieństwo trafnego dopasowania).
- Program sprawdza czy zapytanie ma najwyższy współczynnik prawdopodobieństwa, program generuje liczbę pseudolosową od 0 do 1 jeżeli współczynnik jest większy od tej liczby to hasło jest wykorzystane w krzyżówce.
- Natepnie powtarza od punkt 2 aż do wypełnienia wszystkich pól bądź też do niemożliwości znalezienia kolejnych haseł
- Resztę haseł generuje na podstawie liter z krzyżówki oraz z słownika sprawdzając na Wikipedi czy mają zbliżone znaczenie do szukanych
- Program dopasowując hasła do krzyżówki stosuje wymyśloną przez nas metode, a mianowicie: hasła są dodawane jeżeli przekraczają próg pewnści w każdej kolejnej iteracji spada próg pewności a rośnie liczba haseł co powoduje że błędne hasła są odrzucane gdyż nie pasują literowo, im więcej iteracji tym więcej haseł dopasowanych.
- Program kończ pracę i zwraca rozwiązaną krzyżówkę
Powrót do Spisu treści
4. Implementacja
Program został napisany w języku PHP ponieważ jest to idealny język programowania zaawansowanych aplikacji internetowych, posiada wiele funkcji wspomagających operowanie w sieci Internet, takie jak:
- Łatwe używanie plików zdalnych
- Tworzenie zapytań do stron
- Posiada wiele funkcji tekstowych w których można używać wyrażeń regularnych co jest potrzebne w naszym projekcie, np. do parserowania stron, łatwego wyszukiwania informacji na stronie i szybkiego porównywania tekstu na stronie
- Jest to język skryptowy nie potrzebny jest nam kompilator, a całą aplikacje można napisać notatniku, czyli w całkowicie darmowym środowisku programistycznym.
Wczytywanie krzyżówki ze specjalnie sformatowanego pliku.
Format pliku z krzyżówką
Wpisywanie haseł poziomo
1 wiersz pliku „x” –szerokość
2 wiersz pliku „y” – wysokość
3 – (3+x) wierszy pliku „tablica” – kolejne wiersze krzyżówki
4+x wiersza – ilość pytań pionowo
5+x wiersza – pierwsze pytanie pionowo
6+x wiersza „b” – położenie y hasła
7+x wiersza „d” – długość hasła
idt.
Wpisywanie haseł pionowo przebiega identycznie jak da haseł poziomych
Kod programu wczytywania krzyżówki.
<?php
$nazwa='k1.kr';//nazwa pliku z krzyzowka
$plik=file($nazwa);
echo "Krzyzówka panoramiczna wczytana z pliku:$nazwa <br><br><br>";
echo '<center>Układ krzyżówki<br><table border="1">';
$pozycja=2;//wyswietla krzyzowke
for ($x=0;$x<$plik[0];$x++)
{
echo '<tr align="center" valign="middle">';
for ($y=0;$y<$plik[1];$y++)
{
if ($plik[$x+$pozycja][$y]!='#')
$tab[$x][$y]='.';
else
$tab[$x][$y]='#';
if ($plik[$x+2][$y]=='.')
echo '<td width="20"> </td>';
else
echo '<td width="20">'.$plik[$x+2][$y].'</td>';
}
echo '</tr>';
}
echo '</table>';
$pozycja+=$plik[0];
for ($p=0;$p<$plik[$pozycja];$p++)
{
$dane[$p][0]=1;
$dane[$p][1]=$plik[$pozycja+1+4*$p];
$dane[$p][2]=$plik[$pozycja+2+4*$p];
$dane[$p][3]=$plik[$pozycja+3+4*$p];
$dane[$p][4]=$plik[$pozycja+4+4*$p];
}
$ile=$plik[$pozycja];
$pozycja+=4*$plik[$pozycja]+1;
for ($p=0;$p<$plik[$pozycja];$p++)
{
$dane[$p+$ile][0]=0;
$dane[$p+$ile][1]=$plik[$pozycja+1+4*$p];
$dane[$p+$ile][2]=$plik[$pozycja+2+4*$p];
$dane[$p+$ile][3]=$plik[$pozycja+3+4*$p];
$dane[$p+$ile][4]=$plik[$pozycja+4+4*$p];
}
$pozycja=0;
echo '<br><br>Pytania do krzyżówki <br><table border="1"><tr><td width="300">Pionowo:</td><td width="300">Pionowo:</td></tr><tr><td>';
$licz=1;
for ($p=0;$p<sizeof($dane);$p++)
{
if (($pozycja==0)&&($dane[$p][0]==0))
{
$pozycja=1;
$licz=1;
echo '</td><td>';
}
echo "$licz.".$dane[$p][4].'<br>';
$licz++;
}
echo '</td></tr></table>';
echo '<br><br><br>Proponowane wypełnienie krzyżówki przez program:<br><table border="1">';//wyswietlanie rozwiazania
for ($x=0;$x<$plik[0];$x++)
{
echo '<tr align="center" valign="middle">';
for ($y=0;$y<$plik[1];$y++)
{
if ($tab[$x][$y]=='.')
echo '<td width="20"> </td>';
else
echo '<td width="20">'.$tab[$x][$y].'</td>';
}
echo '</tr>';
}
echo '</table></center>';
?>
Powrót do Spisu treści
5. Przykłady działania
Przykłady do testowania wzieliśmy z "300 panoramcznych".
|
| Tak wygląda pierwsze trona naszego programu.
Mamy podaną wprowadzoną uprzednio krzyżówkę, jeżeli mamy już wcześniej jakieś inne krzyżówki to wybieramy w niej jaką krzyzówke chcemy aby nasz program ją rozwiązał. |
Tak wygląda strona z krzyżowką którą chcemy rozwiązać
| | Dla prostych i małych krzyżówek program zwraca poprawne zupełne rozwiązanie |
| | Dla trudniejszych krzyżówek nie zwraca kompletnych wyników ponważ myli znaczenia haseł |
| | Dla dużych krzyżówek skala błędu jest dość duża. |
Powrót do Spisu treści
|
6. Wnioski
O programie.
Program wykorzystuje w pełni wszystkie możliwości, zwraca dość dobre wyniki, ale posiada również drobne ograniczenia między innymi przepustowości łącza i poprawności działania witryn z których korzysta np. Wikipedia lub krzyżówi.info, strony te są bądź źle skonfigurowane lub działają na słabych serwerach które przy częstym odpytywaniu wyrzucają dużo błędów lub się po prostu zawieszają.
Zastosowana pseudolosowość w naszym programie powoduje zróżnicowane wyniki działania algorytmu, jednak jego skuteczność wynosi za każdym razem ponad 50% odgadniętych haseł. Mimo posiadania szybkiego łącza internetowego odpytywanie jednej witryny zajmuje bardzo dużo czasu.
Naszym zamiarem w początkowej fazie projektu było stworzenie swojej bazy danych haseł w MySQL jednak, niemożliwe było zastosowanie serwera politechniki do naszej bazy danych porzuciliśmy ten projekt.
Dla małych krzyżówek program zwraca kompletne rozwiązania, przy większych krzyżówkach ma problemy z dopasowniem haseł co widać na załączonym przez nas przykładzie testującym.
Wynika to z faktu iż jeżeli krzyżówka jest duża to hasła w 100%, pewne nie zawsze mają częśći wspólne z wygenerowanymi niepewnymi hasłami, co powoduje że wstawiane są hasła losowe.
Powrót do Spisu treści
7. Materiały
- Masłowska Danuta, Masłowski Włodzimierz,
Wielki leksykon krzyżówkowy z anagramami, KDC, 06.2006
- Słownik języka polskiego PWN,
- Encyklopedia PWN
- Słownik wyrazów obcych PWN
- Wikipedia
- Słownik
- Szaradzista
- SłOWNIK KRZYŻÓWKI INFO
- Pomocniki do rozwiązywania krzyżówek
- Wyszukiwanie haseł do krzyżówki lub literaków:-)
- Kreator
|
Powrót do Spisu treści
|
|
|
