Αναζήτηση χωρίς πληροφόρηση

1. Κωδικοποίηση γραφήματος

Παράδειγμα ανάγνωσης ενός γραφήματος από αρχείο κειμένου καθώς και παρουσίασης της πληροφορίας του γραφήματος.

Μεταγλώττιση

g++ lab01_graph.cpp lab01_01.cpp -o lab01_01 -Wall -std=c++11

Εκτέλεση για τη φόρτωση του αρχείου tour_romania.txt από τον κατάλογο data

./lab01_01 data/tour_romania.txt

Έξοδος

Vertices=20
Vertex Arad(A)
Vertex Bucharest(B)
…
Vertex Zerind(Z)
Edges=46
Arad(A)--140-->Sibiu(S)
8
Arad(A)--118-->Timisoara(T)
…
Zerind(Z)--71-->Oradea(O)

2. Υλοποίηση βασικών μορφών των αλγορίθμων αναζήτησης πρώτα κατά βάθος (DFS) και αναζήτησης πρώτα κατά πλάτος (BFS)

Αναζήτηση πρώτα κατά βάθος (DFS) και αναζήτηση πρώτα κατά πλάτος (BFS) χωρίς να αποθηκεύεται η διαδρομή που εντοπίζει ο αλγόριθμος. Εμφανίζει τις πόλεις οι οποίες εξετάζονται κατά την αναζήτηση και εφόσον βρεθεί ο προορισμός το μήκος της διαδρομής όπως έχει εντοπιστεί από τον αλγόριθμο.

Μεταγλώττιση

g++ lab01_graph.cpp lab01_search_simple.cpp lab01_02.cpp -o lab01_02 -std=c++11

Εκτέλεση για την εφαρμογή του αλγορίθμου BFS στο αρχείο tour_romania.txt για τη μετάβαση από την πόλη C στην πόλη Β

./lab01_02 data/tour_romania.txt C B bfs

Έξοδος

BREADTH FIRST SEARCH
Starting from node C
current state: D
current state: P
current state: R
current state: C
current state: M
current state: B
Path to goal node B found with length 239

3. Υλοποίηση αλγορίθμων BFS, DFS και ομοιόμορφης αναζήτησης (UCS) με ταυτόχρονη αποθήκευση της διαδρομής από την αφετηρία προς τον προορισμό

Μεταγλώττιση

g++ lab01_graph.cpp lab01_search.cpp lab01_03.cpp -o lab01_03 -std=c++11

Εκτέλεση για την εφαρμογή του αλγορίθμου BFS στο αρχείο tour_romania.txt για τη μετάβαση από την πόλη C στην πόλη Β

./lab01_03 data/tour_romania.txt C B bfs

Έξοδος

BREADTH FIRST SEARCH
frontier:[(C)] closed set:[] current node:C successors:[D P R]
frontier:[(C-D)(C-P)(C-R)] closed set:[C] current node:D successors:[C M]
frontier:[(C-P)(C-R)(C-D-C)(C-D-M)] closed set:[C D] current node:P successors:[B C R]
frontier:[(C-R)(C-D-C)(C-D-M)(C-P-B)(C-P-C)(C-P-R)] closed set:[C D P] current node:R successors:[C P S]
frontier:[(C-D-C)(C-D-M)(C-P-B)(C-P-C)(C-P-R)(C-R-C)(C-R-P)(C-R-S)] closed set:[C D P R] current node:C successors:[loop]
frontier:[(C-D-M)(C-P-B)(C-P-C)(C-P-R)(C-R-C)(C-R-P)(C-R-S)] closed set:[C D P R] current node:M successors:[D L]
frontier:[(C-P-B)(C-P-C)(C-P-R)(C-R-C)(C-R-P)(C-R-S)(C-D-M-D)(C-D-M-L)] closed set:[C D M P R] current node:B successors:[F G P U]
Path to goal node found: (Craiova-Pitesti-Bucharest 239)

Εκτέλεση για την εφαρμογή του αλγορίθμου DFS στο αρχείο tour_romania.txt για τη μετάβαση από την πόλη C στην πόλη Β

./lab01_03 data/tour_romania.txt C B dfs

Έξοδος

DEPTH FIRST SEARCH
frontier:[(C)] closed set:[] current node:C successors:[D P R]
frontier:[(C-D)(C-P)(C-R)] closed set:[C] current node:D successors:[C M]
frontier:[(C-D-C)(C-D-M)(C-P)(C-R)] closed set:[C D] current node:C successors:[loop]
frontier:[(C-D-M)(C-P)(C-R)] closed set:[C D] current node:M successors:[D L]
frontier:[(C-D-M-D)(C-D-M-L)(C-P)(C-R)] closed set:[C D M] current node:D successors:[loop]
frontier:[(C-D-M-L)(C-P)(C-R)] closed set:[C D M] current node:L successors:[M T]
frontier:[(C-D-M-L-M)(C-D-M-L-T)(C-P)(C-R)] closed set:[C D L M] current node:M successors:[loop]
frontier:[(C-D-M-L-T)(C-P)(C-R)] closed set:[C D L M] current node:T successors:[A L]
frontier:[(C-D-M-L-T-A)(C-D-M-L-T-L)(C-P)(C-R)] closed set:[C D L M T] current node:A successors:[S T Z]
frontier:[(C-D-M-L-T-A-S)(C-D-M-L-T-A-T)(C-D-M-L-T-A-Z)(C-D-M-L-T-L)(C-P)(C-R)] closed set:[A C D L M T] current node:S successors:[A F O R]
frontier:[(C-D-M-L-T-A-S-A)(C-D-M-L-T-A-S-F)(C-D-M-L-T-A-S-O)(C-D-M-L-T-A-S-R)(C-D-M-L-T-A-T)(C-D-M-L-T-A-Z)(C-D-M-L-T-L)(C-P)(C-R)] closed set:[A C D L M S T] current node:A successors:[loop]
frontier:[(C-D-M-L-T-A-S-F)(C-D-M-L-T-A-S-O)(C-D-M-L-T-A-S-R)(C-D-M-L-T-A-T)(C-D-M-L-T-A-Z)(C-D-M-L-T-L)(C-P)(C-R)] closed set:[A C D L M S T] current node:F successors:[B S]
frontier:[(C-D-M-L-T-A-S-F-B)(C-D-M-L-T-A-S-F-S)(C-D-M-L-T-A-S-O)(C-D-M-L-T-A-S-R)(C-D-M-L-T-A-T)(C-D-M-L-T-A-Z)(C-D-M-L-T-L)(C-P)(C-R)] closed set:[A C D F L M S T] current node:B successors:[F G P U]
Path to goal node found: (Craiova-Drobeta-Mehadia-Lugoj-Timisoara-Arad-Sibiu-Fagaras-Bucharest 944)

Εκτέλεση για την εφαρμογή του αλγορίθμου UCS στο αρχείο tour_romania.txt για τη μετάβαση από την πόλη C στην πόλη Β

./lab01_03 data/tour_romania.txt C B ucs

Έξοδος

UNIFORM COST SEARCH
frontier:[(C 0)] closed set:[] current node:C successors:[D P R]
frontier:[(C-D 120)(C-P 138)(C-R 146)] closed set:[C] current node:D successors:[C M]
frontier:[(C-P 138)(C-R 146)(C-D-M 195)(C-D-C 240)] closed set:[C D] current node:P successors:[B C R]
frontier:[(C-R 146)(C-D-M 195)(C-P-R 235)(C-P-B 239)(C-D-C 240)(C-P-C 276)] closed set:[C D P] current node:R successors:[C P S]
frontier:[(C-D-M 195)(C-R-S 226)(C-P-R 235)(C-P-B 239)(C-D-C 240)(C-R-P 243)(C-P-C 276)(C-R-C 292)] closed set:[C D P R] current node:M successors:[D L]
frontier:[(C-R-S 226)(C-P-R 235)(C-P-B 239)(C-D-C 240)(C-R-P 243)(C-D-M-L 265)(C-D-M-D 270)(C-P-C 276)(C-R-C 292)] closed set:[C D M P R] current node:S successors:[A F O R]
frontier:[(C-P-R 235)(C-P-B 239)(C-D-C 240)(C-R-P 243)(C-D-M-L 265)(C-D-M-D 270)(C-P-C 276)(C-R-C 292)(C-R-S-R 306)(C-R-S-F 325)(C-R-S-A 366)(C-R-S-O 377)] closed set:[C D M P R S] current node:R successors:[loop]
frontier:[(C-P-B 239)(C-D-C 240)(C-R-P 243)(C-D-M-L 265)(C-D-M-D 270)(C-P-C 276)(C-R-C 292)(C-R-S-R 306)(C-R-S-F 325)(C-R-S-A 366)(C-R-S-O 377)] closed set:[C D M P R S] current node:B successors:[F G P U]
Path to goal node found: (Craiova-Pitesti-Bucharest 239)

Μεταγλώττιση και εκτέλεση όλων των παραδειγμάτων με makefile

makefile

make

Εκτέλεση παραδείγματος 1 (tour_romania.txt)

make run1

Εκτέλεση παραδείγματος 2 (tour_romania.txt, BFS, Arad–>Bucharest)

make run2

Εκτέλεση παραδείγματος 3 (tour_romania.txt, BFS, Arad–>Bucharest)

make run3

Διαγραφή των εκτελέσιμων

make clean

Ασκήσεις

Μεταγλώττιση όλων των ασκήσεων με makefile

exercises.mk

make -f exercises.mk

Εκτέλεση άσκησης 2

make -f exercises.mk exercise02

Εκτέλεση άσκησης 3

make -f exercises.mk exercise03

Εκτέλεση άσκησης 4

make -f exercises.mk exercise04

Εκτέλεση άσκησης 6

make -f exercises.mk exercise06

Εκτέλεση άσκησης 8

make -f exercises.mk exercise08

ceteiep_ai

AI: uninformed search, informed search, adversarial search, constraint satisfaction problems, logic programming with prolog

Αναζήτηση χωρίς πληροφόρηση

1. Κωδικοποίηση γραφήματος

2. Υλοποίηση βασικών μορφών των αλγορίθμων αναζήτησης πρώτα κατά βάθος (DFS) και αναζήτησης πρώτα κατά πλάτος (BFS)

3. Υλοποίηση αλγορίθμων BFS, DFS και ομοιόμορφης αναζήτησης (UCS) με ταυτόχρονη αποθήκευση της διαδρομής από την αφετηρία προς τον προορισμό

Ασκήσεις