---
tags: Math, AISearch, Homework
title: AISearch
author: Vo Hoang Anh - SPyofgame
license: Private Use
---
Use this link in case of broken PDF: https://hackmd.io/@spyofgame/AISearch
## 1. Descriptions
- Actually, I **did** implement 27 different search algorithms.
- I remove most of them to ensure the PDF is no more than 15Mb
- Other than 7 required algorithms, I only keep Dijkstra to ensure correctness.
- The time complexity and memory complexity is the same as your slides.
- Further optimizations is possible, but that will make the code hard to read.
- Other than these requirements, I also added tracking methods.
- To ensure correctness, I also added some validations before output.
- The comparisons are trivial, as `2.` sections didnt require further.
- Notice that the output (memory and runtime) can not be reproducible.
- The result can be differ at most by `25%` (`int` is **implementation defined**)
- The files are handled specifically based on major compiler
```cpp=983
bool openFiles(const string& baseFilename)
{
string inputFilename = baseFilename + ".inp";
string outputFilename = baseFilename + ".out";
#ifdef _MSC_VER // x64 msvc v19.latest
FILE* file;
errno_t err;
err = fopen_s(&file, inputFilename.c_str(), "r");
if (err == 0) {
freopen_s(&file, inputFilename.c_str(), "r", stdin);
freopen_s(&file, outputFilename.c_str(), "w", stdout);
return true;
}
else {
cerr << "Error: Failed to open input file." << endl;
return false;
}
#else // x86-64 gcc 14.1 or x86-64 clang 18.1.0
if (freopen(inputFilename.c_str(), "r", stdin) && freopen(outputFilename.c_str(), "w", stdout)) {
return true;
}
else {
cerr << "Error: Failed to open input file." << endl;
return false;
}
#endif
}
```
- For DFS, I use boolean function to detect whether or not we should early break.
```cpp=565
// ::spy::algo::class DFS::RecursiveSearch(...)
if (node == G.goal || G.matrix[node][G.goal]) {
path.push_back(G.goal);
return true;
}
```
```cpp=574
// ::spy::algo::class DFS::RecursiveSearch(...)
if (RecursiveSearch(next, visited, path)) {
return true;
}
```
- For BFS, we also have early check, safe check and shortcut check
```cpp=599
// ::spy::algo::class BFS::Search(...)
if (G.start == G.goal) {
trace[G.goal] = G.start;
return TracePath(G.goal, trace);
}
```
```cpp=607
// ::spy::algo::class BFS::Search(...)
if (node == G.goal) {
break
}
```
```cpp=611
// ::spy::algo::class BFS::Search(...)
if (next == G.goal) {
return TracePath(G.goal, trace);
}
```
- For GBFS, we also have early check and shortcut check
```cpp=653
// ::spy::algo::class GFS::Search(...)
if (G.start == G.goal) {
trace[G.goal] = G.start;
return TracePath(G.goal, trace);
}
```
```cpp=661
// ::spy::algo::class GFS::Search(...)
if (next == G.goal) {
return TracePath(G.goal, trace);
}
```
- For UCS, we also have early check and expanded check
```cpp=700
// ::spy::algo::class UCS::Search(...)
if (G.start == G.goal) {
trace[G.goal] = G.start;
return TracePath(G.goal, trace);
}
```
```cpp=710
// ::spy::algo::class UCS::Search(...)
if (node == G.goal) {
return TracePath(G.goal, trace);
}
```
- For A\*S, I only implement expanded check and unconnected graph check
- The requirement didnt specify behaviour of A* for that special case
```cpp=841
// ::spy::algo::class ASS::Search(...)
if (node == G.goal) {
return TracePath(node, trace);
}
```
```cpp=857
// ::spy::algo::class ASS::Search(...)
return vec_int();
```
- For HCS, I do check on failure that return INVALID PATH
```cpp=803
// ::spy::algo::class HCS::Search(...)
if (next_step == -1) {
return vec_int();
}
```
## 2. Requirements
### 2.1 - Programming Language
:::warning
:::
- `C++` is used, as a single file.
- No preprocessor is used.
- No external library needed to be included.
- Only STL library
```cpp=1
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <cstdio>
#include <chrono>
#include <memory>
#include <queue>
#include <map>
#include <set>
```
- Adapted to many compilers and environments (Windows, Linux, Mac)
```yml
> https://godbolt.org/z/GPqhv4c4v - STRICTLY NO_WARNING_OR_ERROR ALLOWED
> GCC: x84-64 gcc 14.1 -std=c++14 -Wall -Wpedantic
> CLANG: x86-64 clang 18.1.0 -std=c++14 -Wall -Wpedantic
> MCSV: x64 mcsv latest 19 /std:c++14 /permissive- /W3
```
### 2.2 - Input
- The graph only using required data, without precalculation.
```cpp=331
namespace spy
{
namespace graph
{
struct Graph
{
int node_count, start, goal;
vector<vector<int>> matrix;
vector<int> heurs;
Graph() : node_count(0), start(0), goal(0) {}
```
```cpp=533
}
};
}
}
```
- The input is read correctly
```cpp=510
// ::spy::graph::class Graph
friend istream& operator >> (istream& cin, Graph& G)
{
cin >> G.node_count >> G.start >> G.goal;
G.matrix.resize(G.node_count);
for (auto& arr : G.matrix) {
arr.resize(G.node_count);
for (auto& value : arr) {
cin >> value;
}
}
G.heurs.resize(G.node_count);
for (auto& value : G.heurs) {
cin >> value;
}
return cin;
}
```
### 2.3 - Output
- See `E.0` for more details
- Apparently my algorithms did more than every required.
#### 2.3-a) Tracking path
- Some algorithms have the path declared in `.Search()`
```cpp=554
// ::spy::algo::class DFS::Search()
vec_int path(Alloc<int>("DFS::path[]"));
```
```cpp=754
// ::spy::algo::class IDS::Search()::for loop
vec_int path(Alloc<int>("IDS::path[]"));
```
```cpp=7901
// ::spy::algo::class HCS::Search()
vec_int path(Alloc<int>("HCS::path[]"));
```
- But the others have `TracePath()` method
```cpp=624
// ::spy::algo::class BFS::
vec_int TracePath(int goal, const vec_int& trace)
{
vec_int path(Alloc<int>("BFS::path[]"));
for (int v = goal; v != -1; v = trace[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
return path;
}
```
- They use `trace[]` that will eventually being converted into `path[]`
```cpp=592
// ::spy::algo::class BFS::Search()
vec_int trace(G.node_count, -1, Alloc<int>("BFS::trace[]"));
```
```cpp=642
// ::spy::algo::class GFS::Search()
vec_int trace(G.node_count, -1, Alloc<int>("GFS::trace[]"));
```
```cpp=697
// ::spy::algo::class UCS::Search()
vec_int trace(G.node_count, -1, Alloc<int>("UCS::trace[]"));
```
```cpp=829
// ::spy::algo::class ASS::Search()
vec_int trace(G.node_count, -1, Alloc<int>("ASS::trace[]"));
```
```cpp=883
// ::spy::algo::class SPS::Search()
vec_int trace(G.node_count, -1, Alloc<int>("SPS::trace[]"));
```
#### 2.3-b) Printing path
- The path is output as
```cpp=211
// ::spy::memory::
template<class T1, class T2>
void PrintPath(const vector<T1>& path, const vector<T2>& cost)
{
cout << "|| Indexed_Path[" << path.size() << "] = " << PathOutput(path, false) << endl;
cout << "|| Lexical_Path[" << path.size() << "] = " << PathOutput(path, true) << endl;
bool is_valid_path = (cost.size() == path.size());
string path_cost_name = (is_valid_path ? "SumCost_Path" : "Invalid_Path");
string path_cost_value = is_valid_path ? CostPathOutput(path, cost, true) : PathOutput(cost, false);
cout << "|| " << path_cost_name << "[" << cost.size() << "] = " << path_cost_value << endl;
cout << "|| Total Cost = " << cost.back() << (is_valid_path ? "" : " INVALID PATH") << endl;
}
```
- The output of path can be either lexical or numerical
```cpp=178
// ::spy::memory::
template<class T>
string PathOutput(const vector<T>& path, bool lex)
{
ostringstream oss;
if (path.empty()) {
oss << "-1 (no path found)";
}
else {
for (size_t i = 0; i < path.size(); ++i) {
if (i > 0) oss << " -> ";
const int node = static_cast<int>(path[i]);
oss << ToLex(node, lex);
}
}
return oss.str();
}
```
- A more fancy version of it output combined with sum cost upto that path
```cpp=195
// ::spy::memory::
template<class T1, class T2>
string CostPathOutput(const vector<T1>& path, const vector<T2>& cost, bool lex)
{
ostringstream oss;
if (path.empty()) {
oss << "-1 (no path found)";
}
else {
for (size_t i = 0; i < path.size(); ++i) {
if (i > 0) oss << " -> ";
oss << ToLex(path[i], lex) << "[" << cost[i] << "]";
}
}
return oss.str();
}
```
#### 2.3-c) Tracking runtime
- Using the `clock_t` defined as a `steady_clock` of that point
```cpp=43
// ::spy::memory::
using clock_t = chrono::steady_clock::time_point;
clock_t start;
```
- The `start` clock should be `Reset()` before it can be used
```cpp=56
// ::spy::memory::Reset():
start = chrono::steady_clock::now();
...
```
- We only need to have the `stop` timer to calculated elapsed time.
```cpp=260
// ::spy::memory::
template<class T1, class T2>
void PrintTimeMem(const string& name, const vector<T1>& path, const vector<T2>& CostPath)
{
const clock_t stop = chrono::steady_clock::now();
cout << name << endl;
PrintPath(path, CostPath);
PrintTime(stop);
PrintMem();
}
```
#### 2.3-d) Printing runtime
- As mentioned ealier, using both `start` and `stop`, we can calculate runtime
```cpp=223
// ::spy::memory::
void PrintTime(const clock_t& stop)
{
auto elapsed_time = stop - start;
auto duration = chrono::duration_cast<chrono::duration<double>>(elapsed_time);
double runtime = duration.count();
cout << "|| Runtime = " << fixed << setprecision(6) << runtime << " seconds" << endl;
}
```
- To calculate the runtime for each specific algorithm only, `Reset()` on each run
```cpp=953
// ::spy::Search(...)
auto performSearch = [&](auto& algorithm, const string& name, const string& alias = "") {
memory::Reset();
auto path = RemoveAllocator(algorithm.Search());
const string details = name + "::Search(Graph)" + alias;
memory::PrintTimeMem(details, path, G.CostPath(path));
separator();
};
```
#### 2.3-e) Tracking memory
- Create a custom allocator that can be tracked with static variable
```cpp=270
// ::spy::memory::
template<typename T>
struct Alloc
{
using value_type = T;
string name;
Alloc(const string& name = "unknown") : name(name)
{
Create(name);
}
template<typename U>
constexpr Alloc(const Alloc<U>& other) noexcept : name(other.name)
{
Create(name);
}
T* allocate(size_t n)
{
Update(name, ALLOCATE, n * sizeof(T));
if (n > allocator_traits<Alloc>::max_size(*this)) {
throw bad_alloc();
}
return static_cast<T*>(::operator new(n * sizeof(T)));
}
void deallocate(T* p, size_t size) noexcept
{
Update(name, DEALLOCATE, size * sizeof(T));
::operator delete(p);
}
template<typename U, typename... Args>
void construct(U* p, Args&&... args)
{
Update(name, CONSTRUCT, sizeof...(args) * sizeof(T));
new (p) U(std::forward<Args>(args)...);
}
template<typename U>
void destroy(U* p) noexcept
{
Update(name, DESTROY, sizeof(U));
p->~U();
}
friend int operator==(const Alloc&, const Alloc&)
{
return true;
}
friend int operator!=(const Alloc&, const Alloc&)
{
return false;
}
};
```
- Use such allocator on STL containers to track their memory consumptions
```cpp=541
// ::spy::algo::
using vec_int = vector<int, Alloc<int>>;
using queue_int = queue<int, deque<int, Alloc<int>>>;
using couple = pair<int, int>;
using container = vector<couple, Alloc<couple>>;
using min_heap = priority_queue<couple, container, greater<couple>>;
```
- We can use `RemoveAllocator` to avoid `path[]` being tracked during output
```cpp=923
// ::spy::
template<class T, class Alloc_T>
vector<T> RemoveAllocator(const vector<T, Alloc_T>& alloc_path) {
return vector<T>(alloc_path.begin(), alloc_path.end());
}
```
```cpp=955
// ::spy::Search(...)
auto performSearch = [&](auto& algorithm, const string& name, const string& alias = "") {
memory::Reset();
auto path = RemoveAllocator(algorithm.Search());
const string details = name + "::Search(Graph)" + alias;
memory::PrintTimeMem(details, path, G.CostPath(path));
separator();
};
```
#### 2.3-f) Printing memory
- We can output the memory in details
```cpp=260
// ::spy::memory::
template<class T1, class T2>
void PrintTimeMem(const string& name, const vector<T1>& path, const vector<T2>& CostPath)
{
const clock_t stop = chrono::steady_clock::now();
cout << name << endl;
PrintPath(path, CostPath);
PrintTime(stop);
PrintMem();
}
```
```cpp=231
// ::spy::memory::
void PrintMem()
{
size_t memory = op_holding_size;
for (size_t code = 0; code < OP_SIZE; ++code) {
int sign = (code == ALLOCATE || code == CONSTRUCT) ? +1 : -1;
memory += sign * op_tracker[code];
}
size_t max_length = 0;
for (size_t code = 0; code < OP_SIZE; ++code) {
if (op_names[code].length() > max_length) {
max_length = op_names[code].length();
}
}
size_t object_pos = 0;
for (string target : targets) {
cout << "|| Tracking memory of Object[" << ++object_pos << "]: ";
cout << "\"" << target << "\" " << endl;
}
cout << "|| Detected Bad Memory Leak = " << ByteFormat(memory) << endl;
cout << "|| Peak Used Memory At Time = " << ByteFormat(op_peak_size) << endl;
cout << "|| Affected Memory Full Sum = " << ByteFormat(op_affect_size + op_holding_size) << endl;
for (size_t code = 0; code < OP_SIZE; ++code) {
cout << "|| Affected::" << left << setw(max_length) << op_names[code] << " Sum = ";
cout << ByteFormat(op_tracker[code]) << endl;
}
}
```
### 2.4 - Report
- This note itself is already a docs
- Self-references: https://hackmd.io/@spyofgame/AISearch
- Every other specific requirement is already satisfied.
- Testcases are described in `E. Experiments` as required.
- It is unavoidable to have bad page break, since the pdf is auto generated.
### 2.5 - Submission
- If you can see **this**, then I'm pretty sure it is well submitted.
## 3. Assessment
- The algorithms are tested with generator for more than 1.000.000 tests.
- With 5 years in C++ Competitive Programming, I can ensure the correctness.
- We use different tests based on given homework slides.
- The `start_node` and `goal_node` are the naming for `Graph.start` and `Graph.goal`
- Since the requirement isnt consistent in style, I conveniently direct it internally.
```cpp=1013
int main(int argc, char* argv[], char* envp[])
{
// https://godbolt.org/z/GPqhv4c4v
auto all_tests = { "p1s", "i2q1p6", "i2q1p7", "i2q1p8", "i2q1p9" };
for (const string filename : all_tests)
{
cerr << "Trying to open testcase \"" << filename << "\"" << endl;
if (openFiles(filename)) {
cerr << "Success to open the testcase \"" << filename << "\"" << endl;
cout << "Output result \"" << filename << ".out\"" << " <- ";
cout << "Testcase \"" << filename << ".inp\"" << endl;
string start_node = (filename == "i2q1p8" || filename == "i2q1p9") ? "A" : "S";
string end_node = (filename == "i2q1p9") ? "H" : "G";
spy::Search(start_node, end_node);
}
else {
cerr << "Failed to opened the testcase \"" << filename << "\"" << endl;
return 1; // Return error code if file opening fails
}
}
return 0;
}
```
## 4. Notices
- I ain't even trust no one nor having "bestfriend" to ask about stuff, `:(`
- The code is macro-free, no external uses, no hidden dependency.
- The code can be compiled with online compiler without further dependency.
- The code is clear and clean without any obfuscation or abusive of features.
- Proof of work
## E. Experiments
### E.0 - Experiments
- Applied 5 testcases that based on provided homework.
- Each testcase is a pair of `filename.inp` and `filename.out`
- The output is separated into parts by
```cpp=
================================================================
```
#### E.0-a) Core parts
##### E.0-a::i) Ensuring the file is correctly used
```cpp=1
Output result "p1s.out" <- Testcase "p1s.inp"
```
##### E.0-a::ii) Ensuring the algorithms are correctly called
```cpp=99
(DFS)::Search(Graph), based on Lexical, also known as Depth-First-Search
```
```cpp=115
(BFS)::Search(Graph), based on Lexical, also known as Breadth-First-Search
```
```cpp=133
(GFS)::Search(Graph), also known as Greedy-Best-First-Search, GBFS
```
```cpp=151
(UCS)::Search(Graph), also known as Uniform-Cost-Search
```
```cpp=170
(IDS)::Search(Graph), also known as Iterative-Deepening-Search, IDDFS
```
```cpp=186
(HCS)::Search(Graph), also known as Hill-Climbing-Search
```
```cpp=202
(ASS)::Search(Graph), also known as A-Star-Search, A*
```
```cpp=221
(SPS)::Search(Graph), using Dijkstra, also known as Shortest-Path-Search
```
#### E.0-b) Ensuring the input matrix is correctly read
##### E.0-b::i) Basic data
```cpp=3
Graph::node_count = 5 || Graph::edge_count = 14
Graph::start = 0 || Graph::goal = 3
```
```cpp=51
Graph::node_count = 5 || Graph::edge_count = 14
Graph::start = S || Graph::goal = G
```
##### E.0-b::ii) Adjacency matrix
```cpp=5
Graph::adj_matrix[5] = {
+--+--+--+--+--+--+
| |#0|#1|#2|#3|#4|
+--+--+--+--+--+--+
|#0| 0| 4| 5| 0| 0|
+--+--+--+--+--+--+
|#1| 4| 0| 2| 5| 6|
+--+--+--+--+--+--+
|#2| 5| 2| 0| 3| 0|
+--+--+--+--+--+--+
|#3| 0| 5| 3| 0| 1|
+--+--+--+--+--+--+
|#4| 0| 6| 0| 1| 0|
+--+--+--+--+--+--+
}
```
```cpp=53
Graph::adj_matrix[5] = {
+--+--+--+--+--+--+
| |#S|#A|#B|#G|#C|
+--+--+--+--+--+--+
|#S| 0| 4| 5| 0| 0|
+--+--+--+--+--+--+
|#A| 4| 0| 2| 5| 6|
+--+--+--+--+--+--+
|#B| 5| 2| 0| 3| 0|
+--+--+--+--+--+--+
|#G| 0| 5| 3| 0| 1|
+--+--+--+--+--+--+
|#C| 0| 6| 0| 1| 0|
+--+--+--+--+--+--+
}
```
##### E.0-b::iii) Adjacency lists transformation
```cpp=20
Graph::adj_list[5] = {
adj_0 = { 1 2 }
adj_1 = { 0 2 3 4 }
adj_2 = { 0 1 3 }
adj_3 = { 1 2 4 }
adj_4 = { 1 3 }
}
```
```cpp=68
Graph::adj_list[5] = {
adj_S = { A B }
adj_A = { S B G C }
adj_B = { S A G }
adj_G = { A B C }
adj_C = { A G }
}
```
##### E.0-b::iv) Edge list transformation
```cpp=27
Graph::edge[14] = {
0 -> 1 || weight = 4
0 -> 2 || weight = 5
1 -> 0 || weight = 4
1 -> 2 || weight = 2
1 -> 3 || weight = 5
1 -> 4 || weight = 6
2 -> 0 || weight = 5
2 -> 1 || weight = 2
2 -> 3 || weight = 3
3 -> 1 || weight = 5
3 -> 2 || weight = 3
3 -> 4 || weight = 1
4 -> 1 || weight = 6
4 -> 3 || weight = 1
}
```
```cpp=75
Graph::edge[14] = {
S -> A || weight = 4
S -> B || weight = 5
A -> S || weight = 4
A -> B || weight = 2
A -> G || weight = 5
A -> C || weight = 6
B -> S || weight = 5
B -> A || weight = 2
B -> G || weight = 3
G -> A || weight = 5
G -> B || weight = 3
G -> C || weight = 1
C -> A || weight = 6
C -> G || weight = 1
}
```
##### E.0-b::v) Heuristic array
```cpp=43
Graph::heuristic[5] = {
heurs[0] = 8
heurs[1] = 5
heurs[2] = 3
heurs[3] = 0
heurs[4] = 1
}
```
```cpp=91
Graph::heuristic[5] = {
heurs[S] = 8
heurs[A] = 5
heurs[B] = 3
heurs[G] = 0
heurs[C] = 1
}
```
#### E.0-c) Algorithm output format
- For this example
```cpp=98
================================================================
(DFS)::Search(Graph), based on Lexical, also known as Depth-First-Search
|| Indexed_Path[3] = 0 -> 1 -> 3
|| Lexical_Path[3] = S -> A -> G
|| SumCost_Path[3] = S[0] -> A[4] -> G[9]
|| Total Cost = 9
|| Runtime = 0.000046 seconds
|| Tracking memory of Object[1]: "DFS::path[]"
|| Tracking memory of Object[2]: "DFS::visited[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 112 Bytes | 0.11 KB | 0.00 MB
|| Affected Memory Full Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Allocate Sum = 76 Bytes | 0.07 KB | 0.00 MB
|| Affected::Deallocate Sum = 76 Bytes | 0.07 KB | 0.00 MB
|| Affected::Construct Sum = 44 Bytes | 0.04 KB | 0.00 MB
|| Affected::Destroy Sum = 44 Bytes | 0.04 KB | 0.00 MB
================================================================
```
#### E.0-c::i) Ensuring the returning path is correct
- For every algorithm, I ensure its path is indeed correct
```cpp=100
|| Indexed_Path[3] = 0 -> 1 -> 3
|| Lexical_Path[3] = S -> A -> G
|| SumCost_Path[3] = S[0] -> A[4] -> G[9]
|| Total Cost = 9
```
#### E.0-c::ii) Evaluation of runtime
```cpp=104
|| Runtime = 0.000046 seconds
```
#### E.0-c::iii) Tracking memory consumptions using Allocator
```cpp=105
|| Tracking memory of Object[1]: "DFS::path[]"
|| Tracking memory of Object[2]: "DFS::visited[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 112 Bytes | 0.11 KB | 0.00 MB
|| Affected Memory Full Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Allocate Sum = 76 Bytes | 0.07 KB | 0.00 MB
|| Affected::Deallocate Sum = 76 Bytes | 0.07 KB | 0.00 MB
|| Affected::Construct Sum = 44 Bytes | 0.04 KB | 0.00 MB
|| Affected::Destroy Sum = 44 Bytes | 0.04 KB | 0.00 MB
```
### E.1 - Test 1: `p1s.inp` -> `p1s.out`
#### E.1-a) Test data `p1s.inp`
```cpp=
5
0 3
0 4 5 0 0
4 0 2 5 6
5 2 0 3 0
0 5 3 0 1
0 6 0 1 0
8 5 3 0 1
```
#### E.1-b) Test output `p1s.out`
:::success
```cpp=
Output result "p1s.out" <- Testcase "p1s.inp"
================================================================
Graph::node_count = 5 || Graph::edge_count = 14
Graph::start = 0 || Graph::goal = 3
Graph::adj_matrix[5] = {
+--+--+--+--+--+--+
| |#0|#1|#2|#3|#4|
+--+--+--+--+--+--+
|#0| 0| 4| 5| 0| 0|
+--+--+--+--+--+--+
|#1| 4| 0| 2| 5| 6|
+--+--+--+--+--+--+
|#2| 5| 2| 0| 3| 0|
+--+--+--+--+--+--+
|#3| 0| 5| 3| 0| 1|
+--+--+--+--+--+--+
|#4| 0| 6| 0| 1| 0|
+--+--+--+--+--+--+
}
Graph::adj_list[5] = {
adj_0 = { 1 2 }
adj_1 = { 0 2 3 4 }
adj_2 = { 0 1 3 }
adj_3 = { 1 2 4 }
adj_4 = { 1 3 }
}
Graph::edge[14] = {
0 -> 1 || weight = 4
0 -> 2 || weight = 5
1 -> 0 || weight = 4
1 -> 2 || weight = 2
1 -> 3 || weight = 5
1 -> 4 || weight = 6
2 -> 0 || weight = 5
2 -> 1 || weight = 2
2 -> 3 || weight = 3
3 -> 1 || weight = 5
3 -> 2 || weight = 3
3 -> 4 || weight = 1
4 -> 1 || weight = 6
4 -> 3 || weight = 1
}
Graph::heuristic[5] = {
heurs[0] = 8
heurs[1] = 5
heurs[2] = 3
heurs[3] = 0
heurs[4] = 1
}
================================================================
Graph::node_count = 5 || Graph::edge_count = 14
Graph::start = S || Graph::goal = G
Graph::adj_matrix[5] = {
+--+--+--+--+--+--+
| |#S|#A|#B|#G|#C|
+--+--+--+--+--+--+
|#S| 0| 4| 5| 0| 0|
+--+--+--+--+--+--+
|#A| 4| 0| 2| 5| 6|
+--+--+--+--+--+--+
|#B| 5| 2| 0| 3| 0|
+--+--+--+--+--+--+
|#G| 0| 5| 3| 0| 1|
+--+--+--+--+--+--+
|#C| 0| 6| 0| 1| 0|
+--+--+--+--+--+--+
}
Graph::adj_list[5] = {
adj_S = { A B }
adj_A = { S B G C }
adj_B = { S A G }
adj_G = { A B C }
adj_C = { A G }
}
Graph::edge[14] = {
S -> A || weight = 4
S -> B || weight = 5
A -> S || weight = 4
A -> B || weight = 2
A -> G || weight = 5
A -> C || weight = 6
B -> S || weight = 5
B -> A || weight = 2
B -> G || weight = 3
G -> A || weight = 5
G -> B || weight = 3
G -> C || weight = 1
C -> A || weight = 6
C -> G || weight = 1
}
Graph::heuristic[5] = {
heurs[S] = 8
heurs[A] = 5
heurs[B] = 3
heurs[G] = 0
heurs[C] = 1
}
================================================================
(DFS)::Search(Graph), based on Lexical, also known as Depth-First-Search
|| Indexed_Path[3] = 0 -> 1 -> 3
|| Lexical_Path[3] = S -> A -> G
|| SumCost_Path[3] = S[0] -> A[4] -> G[9]
|| Total Cost = 9
|| Runtime = 0.000042 seconds
|| Tracking memory of Object[1]: "DFS::path[]"
|| Tracking memory of Object[2]: "DFS::visited[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 112 Bytes | 0.11 KB | 0.00 MB
|| Affected Memory Full Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Allocate Sum = 76 Bytes | 0.07 KB | 0.00 MB
|| Affected::Deallocate Sum = 76 Bytes | 0.07 KB | 0.00 MB
|| Affected::Construct Sum = 44 Bytes | 0.04 KB | 0.00 MB
|| Affected::Destroy Sum = 44 Bytes | 0.04 KB | 0.00 MB
================================================================
(BFS)::Search(Graph), based on Lexical, also known as Breadth-First-Search
|| Indexed_Path[3] = 0 -> 1 -> 3
|| Lexical_Path[3] = S -> A -> G
|| SumCost_Path[3] = S[0] -> A[4] -> G[9]
|| Total Cost = 9
|| Runtime = 0.000063 seconds
|| Tracking memory of Object[1]: "BFS::trace[]"
|| Tracking memory of Object[2]: "BFS::visited[]"
|| Tracking memory of Object[3]: "BFS::queue[]"
|| Tracking memory of Object[4]: "BFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 268 Bytes | 0.26 KB | 0.00 MB
|| Affected Memory Full Sum = 568 Bytes | 0.55 KB | 0.00 MB
|| Affected::Allocate Sum = 208 Bytes | 0.20 KB | 0.00 MB
|| Affected::Deallocate Sum = 208 Bytes | 0.20 KB | 0.00 MB
|| Affected::Construct Sum = 76 Bytes | 0.07 KB | 0.00 MB
|| Affected::Destroy Sum = 76 Bytes | 0.07 KB | 0.00 MB
================================================================
(GFS)::Search(Graph), also known as Greedy-Best-First-Search, GBFS
|| Indexed_Path[3] = 0 -> 2 -> 3
|| Lexical_Path[3] = S -> B -> G
|| SumCost_Path[3] = S[0] -> B[5] -> G[8]
|| Total Cost = 8
|| Runtime = 0.000062 seconds
|| Tracking memory of Object[1]: "GFS::trace[]"
|| Tracking memory of Object[2]: "GFS::visited[]"
|| Tracking memory of Object[3]: "GFS::frontier[]"
|| Tracking memory of Object[4]: "GFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 216 Bytes | 0.21 KB | 0.00 MB
|| Affected Memory Full Sum = 512 Bytes | 0.50 KB | 0.00 MB
|| Affected::Allocate Sum = 152 Bytes | 0.15 KB | 0.00 MB
|| Affected::Deallocate Sum = 152 Bytes | 0.15 KB | 0.00 MB
|| Affected::Construct Sum = 104 Bytes | 0.10 KB | 0.00 MB
|| Affected::Destroy Sum = 104 Bytes | 0.10 KB | 0.00 MB
================================================================
(UCS)::Search(Graph), also known as Uniform-Cost-Search
|| Indexed_Path[3] = 0 -> 2 -> 3
|| Lexical_Path[3] = S -> B -> G
|| SumCost_Path[3] = S[0] -> B[5] -> G[8]
|| Total Cost = 8
|| Runtime = 0.000071 seconds
|| Tracking memory of Object[1]: "UCS::trace[]"
|| Tracking memory of Object[2]: "UCS::cost[]"
|| Tracking memory of Object[3]: "UCS::visited[]"
|| Tracking memory of Object[4]: "UCS::frontier[]"
|| Tracking memory of Object[5]: "UCS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 280 Bytes | 0.27 KB | 0.00 MB
|| Affected Memory Full Sum = 736 Bytes | 0.72 KB | 0.00 MB
|| Affected::Allocate Sum = 212 Bytes | 0.21 KB | 0.00 MB
|| Affected::Deallocate Sum = 212 Bytes | 0.21 KB | 0.00 MB
|| Affected::Construct Sum = 156 Bytes | 0.15 KB | 0.00 MB
|| Affected::Destroy Sum = 156 Bytes | 0.15 KB | 0.00 MB
================================================================
(IDS)::Search(Graph), also known as Iterative-Deepening-Search, IDDFS
|| Indexed_Path[3] = 0 -> 1 -> 3
|| Lexical_Path[3] = S -> A -> G
|| SumCost_Path[3] = S[0] -> A[4] -> G[9]
|| Total Cost = 9
|| Runtime = 0.000063 seconds
|| Tracking memory of Object[1]: "IDS::visited[]"
|| Tracking memory of Object[2]: "IDS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 112 Bytes | 0.11 KB | 0.00 MB
|| Affected Memory Full Sum = 608 Bytes | 0.59 KB | 0.00 MB
|| Affected::Allocate Sum = 196 Bytes | 0.19 KB | 0.00 MB
|| Affected::Deallocate Sum = 196 Bytes | 0.19 KB | 0.00 MB
|| Affected::Construct Sum = 108 Bytes | 0.11 KB | 0.00 MB
|| Affected::Destroy Sum = 108 Bytes | 0.11 KB | 0.00 MB
================================================================
(HCS)::Search(Graph), also known as Hill-Climbing-Search
|| Indexed_Path[3] = 0 -> 2 -> 3
|| Lexical_Path[3] = S -> B -> G
|| SumCost_Path[3] = S[0] -> B[5] -> G[8]
|| Total Cost = 8
|| Runtime = 0.000022 seconds
|| Tracking memory of Object[1]: "HCS::path[]"
|| Tracking memory of Object[2]: ""
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 56 Bytes | 0.05 KB | 0.00 MB
|| Affected Memory Full Sum = 160 Bytes | 0.16 KB | 0.00 MB
|| Affected::Allocate Sum = 56 Bytes | 0.05 KB | 0.00 MB
|| Affected::Deallocate Sum = 56 Bytes | 0.05 KB | 0.00 MB
|| Affected::Construct Sum = 24 Bytes | 0.02 KB | 0.00 MB
|| Affected::Destroy Sum = 24 Bytes | 0.02 KB | 0.00 MB
================================================================
(ASS)::Search(Graph), also known as A-Star-Search, A*
|| Indexed_Path[3] = 0 -> 2 -> 3
|| Lexical_Path[3] = S -> B -> G
|| SumCost_Path[3] = S[0] -> B[5] -> G[8]
|| Total Cost = 8
|| Runtime = 0.000062 seconds
|| Tracking memory of Object[1]: "ASS::trace[]"
|| Tracking memory of Object[2]: "ASS::cost[]"
|| Tracking memory of Object[3]: "ASS::visited[]"
|| Tracking memory of Object[4]: "ASS::frontier[]"
|| Tracking memory of Object[5]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 264 Bytes | 0.26 KB | 0.00 MB
|| Affected Memory Full Sum = 624 Bytes | 0.61 KB | 0.00 MB
|| Affected::Allocate Sum = 188 Bytes | 0.18 KB | 0.00 MB
|| Affected::Deallocate Sum = 188 Bytes | 0.18 KB | 0.00 MB
|| Affected::Construct Sum = 124 Bytes | 0.12 KB | 0.00 MB
|| Affected::Destroy Sum = 124 Bytes | 0.12 KB | 0.00 MB
================================================================
(SPS)::Search(Graph), using Dijkstra, also known as Shortest-Path-Search
|| Indexed_Path[3] = 0 -> 2 -> 3
|| Lexical_Path[3] = S -> B -> G
|| SumCost_Path[3] = S[0] -> B[5] -> G[8]
|| Total Cost = 8
|| Runtime = 0.000061 seconds
|| Tracking memory of Object[1]: "SPS::trace[]"
|| Tracking memory of Object[2]: "SPS::dist[]"
|| Tracking memory of Object[3]: "SPS::frontier[]"
|| Tracking memory of Object[4]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 208 Bytes | 0.20 KB | 0.00 MB
|| Affected Memory Full Sum = 640 Bytes | 0.62 KB | 0.00 MB
|| Affected::Allocate Sum = 176 Bytes | 0.17 KB | 0.00 MB
|| Affected::Deallocate Sum = 176 Bytes | 0.17 KB | 0.00 MB
|| Affected::Construct Sum = 144 Bytes | 0.14 KB | 0.00 MB
|| Affected::Destroy Sum = 144 Bytes | 0.14 KB | 0.00 MB
================================================================
```
:::
## T.2 - Test 2: `i2q1p6.inp` -> `i2q1p6.out`
#### E.2-a) Test data `i2q1p6.inp`
```cpp=
8
0 7
0 5 10 5 0 0 0 0
0 0 0 0 0 4 0 0
0 0 0 0 0 2 0 0
0 0 4 0 0 0 6 0
0 0 0 0 0 0 0 4
0 0 0 0 4 0 0 6
0 0 0 0 0 1 0 3
0 0 0 0 0 0 0 0
2 6 4 6 2 2 3 0
```
#### E.2-b) Test output `p1s.out`
:::success
```cpp=
Output result "i2q1p6.out" <- Testcase "i2q1p6.inp"
================================================================
Graph::node_count = 8 || Graph::edge_count = 12
Graph::start = 0 || Graph::goal = 7
Graph::adj_matrix[8] = {
+--+--+--+--+--+--+--+--+--+
| |#0|#1|#2|#3|#4|#5|#6|#7|
+--+--+--+--+--+--+--+--+--+
|#0| 0| 5|10| 5| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#1| 0| 0| 0| 0| 0| 4| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#2| 0| 0| 0| 0| 0| 2| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#3| 0| 0| 4| 0| 0| 0| 6| 0|
+--+--+--+--+--+--+--+--+--+
|#4| 0| 0| 0| 0| 0| 0| 0| 4|
+--+--+--+--+--+--+--+--+--+
|#5| 0| 0| 0| 0| 4| 0| 0| 6|
+--+--+--+--+--+--+--+--+--+
|#6| 0| 0| 0| 0| 0| 1| 0| 3|
+--+--+--+--+--+--+--+--+--+
|#7| 0| 0| 0| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
}
Graph::adj_list[8] = {
adj_0 = { 1 2 3 }
adj_1 = { 5 }
adj_2 = { 5 }
adj_3 = { 2 6 }
adj_4 = { 7 }
adj_5 = { 4 7 }
adj_6 = { 5 7 }
adj_7 = { }
}
Graph::edge[12] = {
0 -> 1 || weight = 5
0 -> 2 || weight = 10
0 -> 3 || weight = 5
1 -> 5 || weight = 4
2 -> 5 || weight = 2
3 -> 2 || weight = 4
3 -> 6 || weight = 6
4 -> 7 || weight = 4
5 -> 4 || weight = 4
5 -> 7 || weight = 6
6 -> 5 || weight = 1
6 -> 7 || weight = 3
}
Graph::heuristic[8] = {
heurs[0] = 2
heurs[1] = 6
heurs[2] = 4
heurs[3] = 6
heurs[4] = 2
heurs[5] = 2
heurs[6] = 3
heurs[7] = 0
}
================================================================
Graph::node_count = 8 || Graph::edge_count = 12
Graph::start = S || Graph::goal = G
Graph::adj_matrix[8] = {
+--+--+--+--+--+--+--+--+--+
| |#S|#A|#B|#C|#D|#E|#F|#G|
+--+--+--+--+--+--+--+--+--+
|#S| 0| 5|10| 5| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#A| 0| 0| 0| 0| 0| 4| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#B| 0| 0| 0| 0| 0| 2| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#C| 0| 0| 4| 0| 0| 0| 6| 0|
+--+--+--+--+--+--+--+--+--+
|#D| 0| 0| 0| 0| 0| 0| 0| 4|
+--+--+--+--+--+--+--+--+--+
|#E| 0| 0| 0| 0| 4| 0| 0| 6|
+--+--+--+--+--+--+--+--+--+
|#F| 0| 0| 0| 0| 0| 1| 0| 3|
+--+--+--+--+--+--+--+--+--+
|#G| 0| 0| 0| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
}
Graph::adj_list[8] = {
adj_S = { A B C }
adj_A = { E }
adj_B = { E }
adj_C = { B F }
adj_D = { G }
adj_E = { D G }
adj_F = { E G }
adj_G = { }
}
Graph::edge[12] = {
S -> A || weight = 5
S -> B || weight = 10
S -> C || weight = 5
A -> E || weight = 4
B -> E || weight = 2
C -> B || weight = 4
C -> F || weight = 6
D -> G || weight = 4
E -> D || weight = 4
E -> G || weight = 6
F -> E || weight = 1
F -> G || weight = 3
}
Graph::heuristic[8] = {
heurs[S] = 2
heurs[A] = 6
heurs[B] = 4
heurs[C] = 6
heurs[D] = 2
heurs[E] = 2
heurs[F] = 3
heurs[G] = 0
}
================================================================
(DFS)::Search(Graph), based on Lexical, also known as Depth-First-Search
|| Indexed_Path[4] = 0 -> 1 -> 5 -> 7
|| Lexical_Path[4] = S -> A -> E -> G
|| SumCost_Path[4] = S[0] -> A[5] -> E[9] -> G[15]
|| Total Cost = 15
|| Runtime = 0.000042 seconds
|| Tracking memory of Object[1]: "DFS::path[]"
|| Tracking memory of Object[2]: "DFS::visited[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 152 Bytes | 0.15 KB | 0.00 MB
|| Affected Memory Full Sum = 352 Bytes | 0.34 KB | 0.00 MB
|| Affected::Allocate Sum = 104 Bytes | 0.10 KB | 0.00 MB
|| Affected::Deallocate Sum = 104 Bytes | 0.10 KB | 0.00 MB
|| Affected::Construct Sum = 72 Bytes | 0.07 KB | 0.00 MB
|| Affected::Destroy Sum = 72 Bytes | 0.07 KB | 0.00 MB
================================================================
(BFS)::Search(Graph), based on Lexical, also known as Breadth-First-Search
|| Indexed_Path[4] = 0 -> 1 -> 5 -> 7
|| Lexical_Path[4] = S -> A -> E -> G
|| SumCost_Path[4] = S[0] -> A[5] -> E[9] -> G[15]
|| Total Cost = 15
|| Runtime = 0.000068 seconds
|| Tracking memory of Object[1]: "BFS::trace[]"
|| Tracking memory of Object[2]: "BFS::visited[]"
|| Tracking memory of Object[3]: "BFS::queue[]"
|| Tracking memory of Object[4]: "BFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 352 Bytes | 0.34 KB | 0.00 MB
|| Affected Memory Full Sum = 792 Bytes | 0.77 KB | 0.00 MB
|| Affected::Allocate Sum = 264 Bytes | 0.26 KB | 0.00 MB
|| Affected::Deallocate Sum = 264 Bytes | 0.26 KB | 0.00 MB
|| Affected::Construct Sum = 132 Bytes | 0.13 KB | 0.00 MB
|| Affected::Destroy Sum = 132 Bytes | 0.13 KB | 0.00 MB
================================================================
(GFS)::Search(Graph), also known as Greedy-Best-First-Search, GBFS
|| Indexed_Path[4] = 0 -> 2 -> 5 -> 7
|| Lexical_Path[4] = S -> B -> E -> G
|| SumCost_Path[4] = S[0] -> B[10] -> E[12] -> G[18]
|| Total Cost = 18
|| Runtime = 0.000070 seconds
|| Tracking memory of Object[1]: "GFS::trace[]"
|| Tracking memory of Object[2]: "GFS::visited[]"
|| Tracking memory of Object[3]: "GFS::frontier[]"
|| Tracking memory of Object[4]: "GFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 296 Bytes | 0.29 KB | 0.00 MB
|| Affected Memory Full Sum = 784 Bytes | 0.77 KB | 0.00 MB
|| Affected::Allocate Sum = 216 Bytes | 0.21 KB | 0.00 MB
|| Affected::Deallocate Sum = 216 Bytes | 0.21 KB | 0.00 MB
|| Affected::Construct Sum = 176 Bytes | 0.17 KB | 0.00 MB
|| Affected::Destroy Sum = 176 Bytes | 0.17 KB | 0.00 MB
================================================================
(UCS)::Search(Graph), also known as Uniform-Cost-Search
|| Indexed_Path[4] = 0 -> 3 -> 6 -> 7
|| Lexical_Path[4] = S -> C -> F -> G
|| SumCost_Path[4] = S[0] -> C[5] -> F[11] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000091 seconds
|| Tracking memory of Object[1]: "UCS::trace[]"
|| Tracking memory of Object[2]: "UCS::cost[]"
|| Tracking memory of Object[3]: "UCS::visited[]"
|| Tracking memory of Object[4]: "UCS::frontier[]"
|| Tracking memory of Object[5]: "UCS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 368 Bytes | 0.36 KB | 0.00 MB
|| Affected Memory Full Sum = 1120 Bytes | 1.09 KB | 0.00 MB
|| Affected::Allocate Sum = 296 Bytes | 0.29 KB | 0.00 MB
|| Affected::Deallocate Sum = 296 Bytes | 0.29 KB | 0.00 MB
|| Affected::Construct Sum = 264 Bytes | 0.26 KB | 0.00 MB
|| Affected::Destroy Sum = 264 Bytes | 0.26 KB | 0.00 MB
================================================================
(IDS)::Search(Graph), also known as Iterative-Deepening-Search, IDDFS
|| Indexed_Path[4] = 0 -> 1 -> 5 -> 7
|| Lexical_Path[4] = S -> A -> E -> G
|| SumCost_Path[4] = S[0] -> A[5] -> E[9] -> G[15]
|| Total Cost = 15
|| Runtime = 0.000102 seconds
|| Tracking memory of Object[1]: "IDS::visited[]"
|| Tracking memory of Object[2]: "IDS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 152 Bytes | 0.15 KB | 0.00 MB
|| Affected Memory Full Sum = 1152 Bytes | 1.12 KB | 0.00 MB
|| Affected::Allocate Sum = 336 Bytes | 0.33 KB | 0.00 MB
|| Affected::Deallocate Sum = 336 Bytes | 0.33 KB | 0.00 MB
|| Affected::Construct Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Destroy Sum = 240 Bytes | 0.23 KB | 0.00 MB
================================================================
(HCS)::Search(Graph), also known as Hill-Climbing-Search
|| Indexed_Path[4] = 0 -> 2 -> 5 -> 7
|| Lexical_Path[4] = S -> B -> E -> G
|| SumCost_Path[4] = S[0] -> B[10] -> E[12] -> G[18]
|| Total Cost = 18
|| Runtime = 0.000027 seconds
|| Tracking memory of Object[1]: "HCS::path[]"
|| Tracking memory of Object[2]: ""
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 72 Bytes | 0.07 KB | 0.00 MB
|| Affected Memory Full Sum = 224 Bytes | 0.22 KB | 0.00 MB
|| Affected::Allocate Sum = 72 Bytes | 0.07 KB | 0.00 MB
|| Affected::Deallocate Sum = 72 Bytes | 0.07 KB | 0.00 MB
|| Affected::Construct Sum = 40 Bytes | 0.04 KB | 0.00 MB
|| Affected::Destroy Sum = 40 Bytes | 0.04 KB | 0.00 MB
================================================================
(ASS)::Search(Graph), also known as A-Star-Search, A*
|| Indexed_Path[4] = 0 -> 3 -> 6 -> 7
|| Lexical_Path[4] = S -> C -> F -> G
|| SumCost_Path[4] = S[0] -> C[5] -> F[11] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000099 seconds
|| Tracking memory of Object[1]: "ASS::trace[]"
|| Tracking memory of Object[2]: "ASS::cost[]"
|| Tracking memory of Object[3]: "ASS::visited[]"
|| Tracking memory of Object[4]: "ASS::frontier[]"
|| Tracking memory of Object[5]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 408 Bytes | 0.40 KB | 0.00 MB
|| Affected Memory Full Sum = 1280 Bytes | 1.25 KB | 0.00 MB
|| Affected::Allocate Sum = 344 Bytes | 0.34 KB | 0.00 MB
|| Affected::Deallocate Sum = 344 Bytes | 0.34 KB | 0.00 MB
|| Affected::Construct Sum = 296 Bytes | 0.29 KB | 0.00 MB
|| Affected::Destroy Sum = 296 Bytes | 0.29 KB | 0.00 MB
================================================================
(SPS)::Search(Graph), using Dijkstra, also known as Shortest-Path-Search
|| Indexed_Path[4] = 0 -> 3 -> 6 -> 7
|| Lexical_Path[4] = S -> C -> F -> G
|| SumCost_Path[4] = S[0] -> C[5] -> F[11] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000081 seconds
|| Tracking memory of Object[1]: "SPS::trace[]"
|| Tracking memory of Object[2]: "SPS::dist[]"
|| Tracking memory of Object[3]: "SPS::frontier[]"
|| Tracking memory of Object[4]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected Memory Full Sum = 960 Bytes | 0.94 KB | 0.00 MB
|| Affected::Allocate Sum = 248 Bytes | 0.24 KB | 0.00 MB
|| Affected::Deallocate Sum = 248 Bytes | 0.24 KB | 0.00 MB
|| Affected::Construct Sum = 232 Bytes | 0.23 KB | 0.00 MB
|| Affected::Destroy Sum = 232 Bytes | 0.23 KB | 0.00 MB
================================================================
```
:::
## T.3 - Test 3: `i2q1p7.inp` -> `i2q1p7.out`
#### E.3-a) Test data `i2q1p7.inp`
```cpp=
8
0 7
0 2 3 0 0 0 0 0
0 0 0 4 0 0 0 0
0 0 0 5 3 0 0 0
0 0 0 0 0 4 2 0
0 0 0 0 0 0 4 0
0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
6 5 3 3 4 3 1 0
```
#### E.3-b) Test output `p1s.out`
:::success
```cpp=
Output result "i2q1p7.out" <- Testcase "i2q1p7.inp"
================================================================
Graph::node_count = 8 || Graph::edge_count = 10
Graph::start = 0 || Graph::goal = 7
Graph::adj_matrix[8] = {
+--+--+--+--+--+--+--+--+--+
| |#0|#1|#2|#3|#4|#5|#6|#7|
+--+--+--+--+--+--+--+--+--+
|#0| 0| 2| 3| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#1| 0| 0| 0| 4| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#2| 0| 0| 0| 5| 3| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#3| 0| 0| 0| 0| 0| 4| 2| 0|
+--+--+--+--+--+--+--+--+--+
|#4| 0| 0| 0| 0| 0| 0| 4| 0|
+--+--+--+--+--+--+--+--+--+
|#5| 0| 0| 0| 0| 0| 0| 0| 4|
+--+--+--+--+--+--+--+--+--+
|#6| 0| 0| 0| 0| 0| 0| 0| 1|
+--+--+--+--+--+--+--+--+--+
|#7| 0| 0| 0| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
}
Graph::adj_list[8] = {
adj_0 = { 1 2 }
adj_1 = { 3 }
adj_2 = { 3 4 }
adj_3 = { 5 6 }
adj_4 = { 6 }
adj_5 = { 7 }
adj_6 = { 7 }
adj_7 = { }
}
Graph::edge[10] = {
0 -> 1 || weight = 2
0 -> 2 || weight = 3
1 -> 3 || weight = 4
2 -> 3 || weight = 5
2 -> 4 || weight = 3
3 -> 5 || weight = 4
3 -> 6 || weight = 2
4 -> 6 || weight = 4
5 -> 7 || weight = 4
6 -> 7 || weight = 1
}
Graph::heuristic[8] = {
heurs[0] = 6
heurs[1] = 5
heurs[2] = 3
heurs[3] = 3
heurs[4] = 4
heurs[5] = 3
heurs[6] = 1
heurs[7] = 0
}
================================================================
Graph::node_count = 8 || Graph::edge_count = 10
Graph::start = S || Graph::goal = G
Graph::adj_matrix[8] = {
+--+--+--+--+--+--+--+--+--+
| |#S|#A|#B|#C|#D|#E|#F|#G|
+--+--+--+--+--+--+--+--+--+
|#S| 0| 2| 3| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#A| 0| 0| 0| 4| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#B| 0| 0| 0| 5| 3| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#C| 0| 0| 0| 0| 0| 4| 2| 0|
+--+--+--+--+--+--+--+--+--+
|#D| 0| 0| 0| 0| 0| 0| 4| 0|
+--+--+--+--+--+--+--+--+--+
|#E| 0| 0| 0| 0| 0| 0| 0| 4|
+--+--+--+--+--+--+--+--+--+
|#F| 0| 0| 0| 0| 0| 0| 0| 1|
+--+--+--+--+--+--+--+--+--+
|#G| 0| 0| 0| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
}
Graph::adj_list[8] = {
adj_S = { A B }
adj_A = { C }
adj_B = { C D }
adj_C = { E F }
adj_D = { F }
adj_E = { G }
adj_F = { G }
adj_G = { }
}
Graph::edge[10] = {
S -> A || weight = 2
S -> B || weight = 3
A -> C || weight = 4
B -> C || weight = 5
B -> D || weight = 3
C -> E || weight = 4
C -> F || weight = 2
D -> F || weight = 4
E -> G || weight = 4
F -> G || weight = 1
}
Graph::heuristic[8] = {
heurs[S] = 6
heurs[A] = 5
heurs[B] = 3
heurs[C] = 3
heurs[D] = 4
heurs[E] = 3
heurs[F] = 1
heurs[G] = 0
}
================================================================
(DFS)::Search(Graph), based on Lexical, also known as Depth-First-Search
|| Indexed_Path[5] = 0 -> 1 -> 3 -> 5 -> 7
|| Lexical_Path[5] = S -> A -> C -> E -> G
|| SumCost_Path[5] = S[0] -> A[2] -> C[6] -> E[10] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000050 seconds
|| Tracking memory of Object[1]: "DFS::path[]"
|| Tracking memory of Object[2]: "DFS::visited[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 172 Bytes | 0.17 KB | 0.00 MB
|| Affected Memory Full Sum = 440 Bytes | 0.43 KB | 0.00 MB
|| Affected::Allocate Sum = 128 Bytes | 0.12 KB | 0.00 MB
|| Affected::Deallocate Sum = 128 Bytes | 0.12 KB | 0.00 MB
|| Affected::Construct Sum = 92 Bytes | 0.09 KB | 0.00 MB
|| Affected::Destroy Sum = 92 Bytes | 0.09 KB | 0.00 MB
================================================================
(BFS)::Search(Graph), based on Lexical, also known as Breadth-First-Search
|| Indexed_Path[5] = 0 -> 1 -> 3 -> 5 -> 7
|| Lexical_Path[5] = S -> A -> C -> E -> G
|| SumCost_Path[5] = S[0] -> A[2] -> C[6] -> E[10] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000076 seconds
|| Tracking memory of Object[1]: "BFS::trace[]"
|| Tracking memory of Object[2]: "BFS::visited[]"
|| Tracking memory of Object[3]: "BFS::queue[]"
|| Tracking memory of Object[4]: "BFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 368 Bytes | 0.36 KB | 0.00 MB
|| Affected Memory Full Sum = 880 Bytes | 0.86 KB | 0.00 MB
|| Affected::Allocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Deallocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Construct Sum = 152 Bytes | 0.15 KB | 0.00 MB
|| Affected::Destroy Sum = 152 Bytes | 0.15 KB | 0.00 MB
================================================================
(GFS)::Search(Graph), also known as Greedy-Best-First-Search, GBFS
|| Indexed_Path[5] = 0 -> 2 -> 3 -> 6 -> 7
|| Lexical_Path[5] = S -> B -> C -> F -> G
|| SumCost_Path[5] = S[0] -> B[3] -> C[8] -> F[10] -> G[11]
|| Total Cost = 11
|| Runtime = 0.000082 seconds
|| Tracking memory of Object[1]: "GFS::trace[]"
|| Tracking memory of Object[2]: "GFS::visited[]"
|| Tracking memory of Object[3]: "GFS::frontier[]"
|| Tracking memory of Object[4]: "GFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 324 Bytes | 0.32 KB | 0.00 MB
|| Affected Memory Full Sum = 1000 Bytes | 0.98 KB | 0.00 MB
|| Affected::Allocate Sum = 272 Bytes | 0.27 KB | 0.00 MB
|| Affected::Deallocate Sum = 272 Bytes | 0.27 KB | 0.00 MB
|| Affected::Construct Sum = 228 Bytes | 0.22 KB | 0.00 MB
|| Affected::Destroy Sum = 228 Bytes | 0.22 KB | 0.00 MB
================================================================
(UCS)::Search(Graph), also known as Uniform-Cost-Search
|| Indexed_Path[5] = 0 -> 1 -> 3 -> 6 -> 7
|| Lexical_Path[5] = S -> A -> C -> F -> G
|| SumCost_Path[5] = S[0] -> A[2] -> C[6] -> F[8] -> G[9]
|| Total Cost = 9
|| Runtime = 0.000089 seconds
|| Tracking memory of Object[1]: "UCS::trace[]"
|| Tracking memory of Object[2]: "UCS::cost[]"
|| Tracking memory of Object[3]: "UCS::visited[]"
|| Tracking memory of Object[4]: "UCS::frontier[]"
|| Tracking memory of Object[5]: "UCS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 380 Bytes | 0.37 KB | 0.00 MB
|| Affected Memory Full Sum = 1064 Bytes | 1.04 KB | 0.00 MB
|| Affected::Allocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Deallocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Construct Sum = 244 Bytes | 0.24 KB | 0.00 MB
|| Affected::Destroy Sum = 244 Bytes | 0.24 KB | 0.00 MB
================================================================
(IDS)::Search(Graph), also known as Iterative-Deepening-Search, IDDFS
|| Indexed_Path[5] = 0 -> 1 -> 3 -> 5 -> 7
|| Lexical_Path[5] = S -> A -> C -> E -> G
|| SumCost_Path[5] = S[0] -> A[2] -> C[6] -> E[10] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000139 seconds
|| Tracking memory of Object[1]: "IDS::visited[]"
|| Tracking memory of Object[2]: "IDS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 172 Bytes | 0.17 KB | 0.00 MB
|| Affected Memory Full Sum = 1616 Bytes | 1.58 KB | 0.00 MB
|| Affected::Allocate Sum = 464 Bytes | 0.45 KB | 0.00 MB
|| Affected::Deallocate Sum = 464 Bytes | 0.45 KB | 0.00 MB
|| Affected::Construct Sum = 344 Bytes | 0.34 KB | 0.00 MB
|| Affected::Destroy Sum = 344 Bytes | 0.34 KB | 0.00 MB
================================================================
(HCS)::Search(Graph), also known as Hill-Climbing-Search
|| Indexed_Path[5] = 0 -> 2 -> 3 -> 6 -> 7
|| Lexical_Path[5] = S -> B -> C -> F -> G
|| SumCost_Path[5] = S[0] -> B[3] -> C[8] -> F[10] -> G[11]
|| Total Cost = 11
|| Runtime = 0.000033 seconds
|| Tracking memory of Object[1]: "HCS::path[]"
|| Tracking memory of Object[2]: ""
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 92 Bytes | 0.09 KB | 0.00 MB
|| Affected Memory Full Sum = 312 Bytes | 0.30 KB | 0.00 MB
|| Affected::Allocate Sum = 96 Bytes | 0.09 KB | 0.00 MB
|| Affected::Deallocate Sum = 96 Bytes | 0.09 KB | 0.00 MB
|| Affected::Construct Sum = 60 Bytes | 0.06 KB | 0.00 MB
|| Affected::Destroy Sum = 60 Bytes | 0.06 KB | 0.00 MB
================================================================
(ASS)::Search(Graph), also known as A-Star-Search, A*
|| Indexed_Path[5] = 0 -> 1 -> 3 -> 6 -> 7
|| Lexical_Path[5] = S -> A -> C -> F -> G
|| SumCost_Path[5] = S[0] -> A[2] -> C[6] -> F[8] -> G[9]
|| Total Cost = 9
|| Runtime = 0.000099 seconds
|| Tracking memory of Object[1]: "ASS::trace[]"
|| Tracking memory of Object[2]: "ASS::cost[]"
|| Tracking memory of Object[3]: "ASS::visited[]"
|| Tracking memory of Object[4]: "ASS::frontier[]"
|| Tracking memory of Object[5]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 404 Bytes | 0.39 KB | 0.00 MB
|| Affected Memory Full Sum = 1192 Bytes | 1.16 KB | 0.00 MB
|| Affected::Allocate Sum = 320 Bytes | 0.31 KB | 0.00 MB
|| Affected::Deallocate Sum = 320 Bytes | 0.31 KB | 0.00 MB
|| Affected::Construct Sum = 276 Bytes | 0.27 KB | 0.00 MB
|| Affected::Destroy Sum = 276 Bytes | 0.27 KB | 0.00 MB
================================================================
(SPS)::Search(Graph), using Dijkstra, also known as Shortest-Path-Search
|| Indexed_Path[5] = 0 -> 1 -> 3 -> 6 -> 7
|| Lexical_Path[5] = S -> A -> C -> F -> G
|| SumCost_Path[5] = S[0] -> A[2] -> C[6] -> F[8] -> G[9]
|| Total Cost = 9
|| Runtime = 0.000080 seconds
|| Tracking memory of Object[1]: "SPS::trace[]"
|| Tracking memory of Object[2]: "SPS::dist[]"
|| Tracking memory of Object[3]: "SPS::frontier[]"
|| Tracking memory of Object[4]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 292 Bytes | 0.29 KB | 0.00 MB
|| Affected Memory Full Sum = 904 Bytes | 0.88 KB | 0.00 MB
|| Affected::Allocate Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Deallocate Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Construct Sum = 212 Bytes | 0.21 KB | 0.00 MB
|| Affected::Destroy Sum = 212 Bytes | 0.21 KB | 0.00 MB
================================================================
```
:::
## T.4 - Test 4: `i2q1p8.inp` -> `i2q1p8.out`
#### E.4-a) Test data `i2q1p8.inp`
```cpp=
9
0 6
0 2 3 4 0 0 0 0 0
0 0 0 0 2 3 0 0 0
0 0 0 0 0 0 0 0 7
0 0 0 0 0 0 0 4 0
0 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 3 0 0
0 0 0 0 0 0 4 0 0
7 5 9 6 3 5 0 3 4
```
- **HIGHLY NOTICE THAT** I use `I` instead of `J`
- Adding more parameter will introduce uncessary complexity.
- The requirement didnt specify such behaviour for others nodes.
#### E.4-b) Test output `p1s.out`
:::success
```cpp=
Output result "i2q1p8.out" <- Testcase "i2q1p8.inp"
================================================================
Graph::node_count = 9 || Graph::edge_count = 10
Graph::start = 0 || Graph::goal = 6
Graph::adj_matrix[9] = {
+--+--+--+--+--+--+--+--+--+--+
| |#0|#1|#2|#3|#4|#5|#6|#7|#8|
+--+--+--+--+--+--+--+--+--+--+
|#0| 0| 2| 3| 4| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#1| 0| 0| 0| 0| 2| 3| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#2| 0| 0| 0| 0| 0| 0| 0| 0| 7|
+--+--+--+--+--+--+--+--+--+--+
|#3| 0| 0| 0| 0| 0| 0| 0| 4| 0|
+--+--+--+--+--+--+--+--+--+--+
|#4| 0| 0| 0| 0| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#5| 0| 0| 0| 2| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#6| 0| 0| 0| 0| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#7| 0| 0| 0| 0| 0| 0| 3| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#8| 0| 0| 0| 0| 0| 0| 4| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
}
Graph::adj_list[9] = {
adj_0 = { 1 2 3 }
adj_1 = { 4 5 }
adj_2 = { 8 }
adj_3 = { 7 }
adj_4 = { }
adj_5 = { 3 }
adj_6 = { }
adj_7 = { 6 }
adj_8 = { 6 }
}
Graph::edge[10] = {
0 -> 1 || weight = 2
0 -> 2 || weight = 3
0 -> 3 || weight = 4
1 -> 4 || weight = 2
1 -> 5 || weight = 3
2 -> 8 || weight = 7
3 -> 7 || weight = 4
5 -> 3 || weight = 2
7 -> 6 || weight = 3
8 -> 6 || weight = 4
}
Graph::heuristic[9] = {
heurs[0] = 7
heurs[1] = 5
heurs[2] = 9
heurs[3] = 6
heurs[4] = 3
heurs[5] = 5
heurs[6] = 0
heurs[7] = 3
heurs[8] = 4
}
================================================================
Graph::node_count = 9 || Graph::edge_count = 10
Graph::start = A || Graph::goal = G
Graph::adj_matrix[9] = {
+--+--+--+--+--+--+--+--+--+--+
| |#A|#B|#C|#D|#E|#F|#G|#H|#I|
+--+--+--+--+--+--+--+--+--+--+
|#A| 0| 2| 3| 4| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#B| 0| 0| 0| 0| 2| 3| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#C| 0| 0| 0| 0| 0| 0| 0| 0| 7|
+--+--+--+--+--+--+--+--+--+--+
|#D| 0| 0| 0| 0| 0| 0| 0| 4| 0|
+--+--+--+--+--+--+--+--+--+--+
|#E| 0| 0| 0| 0| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#F| 0| 0| 0| 2| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#G| 0| 0| 0| 0| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#H| 0| 0| 0| 0| 0| 0| 3| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
|#I| 0| 0| 0| 0| 0| 0| 4| 0| 0|
+--+--+--+--+--+--+--+--+--+--+
}
Graph::adj_list[9] = {
adj_A = { B C D }
adj_B = { E F }
adj_C = { I }
adj_D = { H }
adj_E = { }
adj_F = { D }
adj_G = { }
adj_H = { G }
adj_I = { G }
}
Graph::edge[10] = {
A -> B || weight = 2
A -> C || weight = 3
A -> D || weight = 4
B -> E || weight = 2
B -> F || weight = 3
C -> I || weight = 7
D -> H || weight = 4
F -> D || weight = 2
H -> G || weight = 3
I -> G || weight = 4
}
Graph::heuristic[9] = {
heurs[A] = 7
heurs[B] = 5
heurs[C] = 9
heurs[D] = 6
heurs[E] = 3
heurs[F] = 5
heurs[G] = 0
heurs[H] = 3
heurs[I] = 4
}
================================================================
(DFS)::Search(Graph), based on Lexical, also known as Depth-First-Search
|| Indexed_Path[6] = 0 -> 1 -> 5 -> 3 -> 7 -> 6
|| Lexical_Path[6] = A -> B -> F -> D -> H -> G
|| SumCost_Path[6] = A[0] -> B[2] -> F[5] -> D[7] -> H[11] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000053 seconds
|| Tracking memory of Object[1]: "DFS::path[]"
|| Tracking memory of Object[2]: "DFS::visited[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 180 Bytes | 0.18 KB | 0.00 MB
|| Affected Memory Full Sum = 472 Bytes | 0.46 KB | 0.00 MB
|| Affected::Allocate Sum = 132 Bytes | 0.13 KB | 0.00 MB
|| Affected::Deallocate Sum = 132 Bytes | 0.13 KB | 0.00 MB
|| Affected::Construct Sum = 104 Bytes | 0.10 KB | 0.00 MB
|| Affected::Destroy Sum = 104 Bytes | 0.10 KB | 0.00 MB
================================================================
(BFS)::Search(Graph), based on Lexical, also known as Breadth-First-Search
|| Indexed_Path[4] = 0 -> 2 -> 8 -> 6
|| Lexical_Path[4] = A -> C -> I -> G
|| SumCost_Path[4] = A[0] -> C[3] -> I[10] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000073 seconds
|| Tracking memory of Object[1]: "BFS::trace[]"
|| Tracking memory of Object[2]: "BFS::visited[]"
|| Tracking memory of Object[3]: "BFS::queue[]"
|| Tracking memory of Object[4]: "BFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 364 Bytes | 0.36 KB | 0.00 MB
|| Affected Memory Full Sum = 832 Bytes | 0.81 KB | 0.00 MB
|| Affected::Allocate Sum = 272 Bytes | 0.27 KB | 0.00 MB
|| Affected::Deallocate Sum = 272 Bytes | 0.27 KB | 0.00 MB
|| Affected::Construct Sum = 144 Bytes | 0.14 KB | 0.00 MB
|| Affected::Destroy Sum = 144 Bytes | 0.14 KB | 0.00 MB
================================================================
(GFS)::Search(Graph), also known as Greedy-Best-First-Search, GBFS
|| Indexed_Path[6] = 0 -> 1 -> 5 -> 3 -> 7 -> 6
|| Lexical_Path[6] = A -> B -> F -> D -> H -> G
|| SumCost_Path[6] = A[0] -> B[2] -> F[5] -> D[7] -> H[11] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000086 seconds
|| Tracking memory of Object[1]: "GFS::trace[]"
|| Tracking memory of Object[2]: "GFS::visited[]"
|| Tracking memory of Object[3]: "GFS::frontier[]"
|| Tracking memory of Object[4]: "GFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 332 Bytes | 0.32 KB | 0.00 MB
|| Affected Memory Full Sum = 1056 Bytes | 1.03 KB | 0.00 MB
|| Affected::Allocate Sum = 280 Bytes | 0.27 KB | 0.00 MB
|| Affected::Deallocate Sum = 280 Bytes | 0.27 KB | 0.00 MB
|| Affected::Construct Sum = 248 Bytes | 0.24 KB | 0.00 MB
|| Affected::Destroy Sum = 248 Bytes | 0.24 KB | 0.00 MB
================================================================
(UCS)::Search(Graph), also known as Uniform-Cost-Search
|| Indexed_Path[4] = 0 -> 3 -> 7 -> 6
|| Lexical_Path[4] = A -> D -> H -> G
|| SumCost_Path[4] = A[0] -> D[4] -> H[8] -> G[11]
|| Total Cost = 11
|| Runtime = 0.000092 seconds
|| Tracking memory of Object[1]: "UCS::trace[]"
|| Tracking memory of Object[2]: "UCS::cost[]"
|| Tracking memory of Object[3]: "UCS::visited[]"
|| Tracking memory of Object[4]: "UCS::frontier[]"
|| Tracking memory of Object[5]: "UCS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 392 Bytes | 0.38 KB | 0.00 MB
|| Affected Memory Full Sum = 1152 Bytes | 1.12 KB | 0.00 MB
|| Affected::Allocate Sum = 308 Bytes | 0.30 KB | 0.00 MB
|| Affected::Deallocate Sum = 308 Bytes | 0.30 KB | 0.00 MB
|| Affected::Construct Sum = 268 Bytes | 0.26 KB | 0.00 MB
|| Affected::Destroy Sum = 268 Bytes | 0.26 KB | 0.00 MB
================================================================
(IDS)::Search(Graph), also known as Iterative-Deepening-Search, IDDFS
|| Indexed_Path[4] = 0 -> 2 -> 8 -> 6
|| Lexical_Path[4] = A -> C -> I -> G
|| SumCost_Path[4] = A[0] -> C[3] -> I[10] -> G[14]
|| Total Cost = 14
|| Runtime = 0.000112 seconds
|| Tracking memory of Object[1]: "IDS::visited[]"
|| Tracking memory of Object[2]: "IDS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 160 Bytes | 0.16 KB | 0.00 MB
|| Affected Memory Full Sum = 1240 Bytes | 1.21 KB | 0.00 MB
|| Affected::Allocate Sum = 352 Bytes | 0.34 KB | 0.00 MB
|| Affected::Deallocate Sum = 352 Bytes | 0.34 KB | 0.00 MB
|| Affected::Construct Sum = 268 Bytes | 0.26 KB | 0.00 MB
|| Affected::Destroy Sum = 268 Bytes | 0.26 KB | 0.00 MB
================================================================
(HCS)::Search(Graph), also known as Hill-Climbing-Search
|| Indexed_Path[0] = -1 (no path found)
|| Lexical_Path[0] = -1 (no path found)
|| Invalid_Path[1] = -1
|| Total Cost = -1 INVALID PATH
|| Runtime = 0.000023 seconds
|| Tracking memory of Object[1]: "HCS::path[]"
|| Tracking memory of Object[2]: "unknown"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 56 Bytes | 0.05 KB | 0.00 MB
|| Affected Memory Full Sum = 160 Bytes | 0.16 KB | 0.00 MB
|| Affected::Allocate Sum = 56 Bytes | 0.05 KB | 0.00 MB
|| Affected::Deallocate Sum = 56 Bytes | 0.05 KB | 0.00 MB
|| Affected::Construct Sum = 24 Bytes | 0.02 KB | 0.00 MB
|| Affected::Destroy Sum = 24 Bytes | 0.02 KB | 0.00 MB
================================================================
(ASS)::Search(Graph), also known as A-Star-Search, A*
|| Indexed_Path[4] = 0 -> 3 -> 7 -> 6
|| Lexical_Path[4] = A -> D -> H -> G
|| SumCost_Path[4] = A[0] -> D[4] -> H[8] -> G[11]
|| Total Cost = 11
|| Runtime = 0.000092 seconds
|| Tracking memory of Object[1]: "ASS::trace[]"
|| Tracking memory of Object[2]: "ASS::cost[]"
|| Tracking memory of Object[3]: "ASS::visited[]"
|| Tracking memory of Object[4]: "ASS::frontier[]"
|| Tracking memory of Object[5]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 392 Bytes | 0.38 KB | 0.00 MB
|| Affected Memory Full Sum = 1136 Bytes | 1.11 KB | 0.00 MB
|| Affected::Allocate Sum = 308 Bytes | 0.30 KB | 0.00 MB
|| Affected::Deallocate Sum = 308 Bytes | 0.30 KB | 0.00 MB
|| Affected::Construct Sum = 260 Bytes | 0.25 KB | 0.00 MB
|| Affected::Destroy Sum = 260 Bytes | 0.25 KB | 0.00 MB
================================================================
(SPS)::Search(Graph), using Dijkstra, also known as Shortest-Path-Search
|| Indexed_Path[4] = 0 -> 3 -> 7 -> 6
|| Lexical_Path[4] = A -> D -> H -> G
|| SumCost_Path[4] = A[0] -> D[4] -> H[8] -> G[11]
|| Total Cost = 11
|| Runtime = 0.000081 seconds
|| Tracking memory of Object[1]: "SPS::trace[]"
|| Tracking memory of Object[2]: "SPS::dist[]"
|| Tracking memory of Object[3]: "SPS::frontier[]"
|| Tracking memory of Object[4]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 304 Bytes | 0.30 KB | 0.00 MB
|| Affected Memory Full Sum = 976 Bytes | 0.95 KB | 0.00 MB
|| Affected::Allocate Sum = 256 Bytes | 0.25 KB | 0.00 MB
|| Affected::Deallocate Sum = 256 Bytes | 0.25 KB | 0.00 MB
|| Affected::Construct Sum = 232 Bytes | 0.23 KB | 0.00 MB
|| Affected::Destroy Sum = 232 Bytes | 0.23 KB | 0.00 MB
================================================================
```
:::
## T.5 - Test 5: `i2q1p9.inp` -> `i2q1p9.out`
#### E.5-a) Test data `i2q1p9.inp`
```cpp=
8
0 7
0 3 3 0 0 0 0 0
3 0 0 2 0 0 0 0
3 0 0 0 0 3 0 0
0 2 0 0 4 0 0 0
0 0 0 4 0 1 2 0
0 0 3 0 1 0 3 0
0 0 0 0 2 3 0 2
0 0 0 0 0 0 2 0
5 6 8 4 4 5 2 0
```
#### E.5-b) Test output `p1s.out`
:::success
```cpp=
Output result "i2q1p9.out" <- Testcase "i2q1p9.inp"
================================================================
Graph::node_count = 8 || Graph::edge_count = 18
Graph::start = 0 || Graph::goal = 7
Graph::adj_matrix[8] = {
+--+--+--+--+--+--+--+--+--+
| |#0|#1|#2|#3|#4|#5|#6|#7|
+--+--+--+--+--+--+--+--+--+
|#0| 0| 3| 3| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#1| 3| 0| 0| 2| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#2| 3| 0| 0| 0| 0| 3| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#3| 0| 2| 0| 0| 4| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#4| 0| 0| 0| 4| 0| 1| 2| 0|
+--+--+--+--+--+--+--+--+--+
|#5| 0| 0| 3| 0| 1| 0| 3| 0|
+--+--+--+--+--+--+--+--+--+
|#6| 0| 0| 0| 0| 2| 3| 0| 2|
+--+--+--+--+--+--+--+--+--+
|#7| 0| 0| 0| 0| 0| 0| 2| 0|
+--+--+--+--+--+--+--+--+--+
}
Graph::adj_list[8] = {
adj_0 = { 1 2 }
adj_1 = { 0 3 }
adj_2 = { 0 5 }
adj_3 = { 1 4 }
adj_4 = { 3 5 6 }
adj_5 = { 2 4 6 }
adj_6 = { 4 5 7 }
adj_7 = { 6 }
}
Graph::edge[18] = {
0 -> 1 || weight = 3
0 -> 2 || weight = 3
1 -> 0 || weight = 3
1 -> 3 || weight = 2
2 -> 0 || weight = 3
2 -> 5 || weight = 3
3 -> 1 || weight = 2
3 -> 4 || weight = 4
4 -> 3 || weight = 4
4 -> 5 || weight = 1
4 -> 6 || weight = 2
5 -> 2 || weight = 3
5 -> 4 || weight = 1
5 -> 6 || weight = 3
6 -> 4 || weight = 2
6 -> 5 || weight = 3
6 -> 7 || weight = 2
7 -> 6 || weight = 2
}
Graph::heuristic[8] = {
heurs[0] = 5
heurs[1] = 6
heurs[2] = 8
heurs[3] = 4
heurs[4] = 4
heurs[5] = 5
heurs[6] = 2
heurs[7] = 0
}
================================================================
Graph::node_count = 8 || Graph::edge_count = 18
Graph::start = A || Graph::goal = H
Graph::adj_matrix[8] = {
+--+--+--+--+--+--+--+--+--+
| |#A|#B|#C|#D|#E|#F|#G|#H|
+--+--+--+--+--+--+--+--+--+
|#A| 0| 3| 3| 0| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#B| 3| 0| 0| 2| 0| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#C| 3| 0| 0| 0| 0| 3| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#D| 0| 2| 0| 0| 4| 0| 0| 0|
+--+--+--+--+--+--+--+--+--+
|#E| 0| 0| 0| 4| 0| 1| 2| 0|
+--+--+--+--+--+--+--+--+--+
|#F| 0| 0| 3| 0| 1| 0| 3| 0|
+--+--+--+--+--+--+--+--+--+
|#G| 0| 0| 0| 0| 2| 3| 0| 2|
+--+--+--+--+--+--+--+--+--+
|#H| 0| 0| 0| 0| 0| 0| 2| 0|
+--+--+--+--+--+--+--+--+--+
}
Graph::adj_list[8] = {
adj_A = { B C }
adj_B = { A D }
adj_C = { A F }
adj_D = { B E }
adj_E = { D F G }
adj_F = { C E G }
adj_G = { E F H }
adj_H = { G }
}
Graph::edge[18] = {
A -> B || weight = 3
A -> C || weight = 3
B -> A || weight = 3
B -> D || weight = 2
C -> A || weight = 3
C -> F || weight = 3
D -> B || weight = 2
D -> E || weight = 4
E -> D || weight = 4
E -> F || weight = 1
E -> G || weight = 2
F -> C || weight = 3
F -> E || weight = 1
F -> G || weight = 3
G -> E || weight = 2
G -> F || weight = 3
G -> H || weight = 2
H -> G || weight = 2
}
Graph::heuristic[8] = {
heurs[A] = 5
heurs[B] = 6
heurs[C] = 8
heurs[D] = 4
heurs[E] = 4
heurs[F] = 5
heurs[G] = 2
heurs[H] = 0
}
================================================================
(DFS)::Search(Graph), based on Lexical, also known as Depth-First-Search
|| Indexed_Path[7] = 0 -> 1 -> 3 -> 4 -> 5 -> 6 -> 7
|| Lexical_Path[7] = A -> B -> D -> E -> F -> G -> H
|| SumCost_Path[7] = A[0] -> B[3] -> D[5] -> E[9] -> F[10] -> G[13] -> H[15]
|| Total Cost = 15
|| Runtime = 0.000061 seconds
|| Tracking memory of Object[1]: "DFS::path[]"
|| Tracking memory of Object[2]: "DFS::visited[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 208 Bytes | 0.20 KB | 0.00 MB
|| Affected Memory Full Sum = 584 Bytes | 0.57 KB | 0.00 MB
|| Affected::Allocate Sum = 164 Bytes | 0.16 KB | 0.00 MB
|| Affected::Deallocate Sum = 164 Bytes | 0.16 KB | 0.00 MB
|| Affected::Construct Sum = 128 Bytes | 0.12 KB | 0.00 MB
|| Affected::Destroy Sum = 128 Bytes | 0.12 KB | 0.00 MB
================================================================
(BFS)::Search(Graph), based on Lexical, also known as Breadth-First-Search
|| Indexed_Path[5] = 0 -> 2 -> 5 -> 6 -> 7
|| Lexical_Path[5] = A -> C -> F -> G -> H
|| SumCost_Path[5] = A[0] -> C[3] -> F[6] -> G[9] -> H[11]
|| Total Cost = 11
|| Runtime = 0.000077 seconds
|| Tracking memory of Object[1]: "BFS::trace[]"
|| Tracking memory of Object[2]: "BFS::visited[]"
|| Tracking memory of Object[3]: "BFS::queue[]"
|| Tracking memory of Object[4]: "BFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 364 Bytes | 0.36 KB | 0.00 MB
|| Affected Memory Full Sum = 880 Bytes | 0.86 KB | 0.00 MB
|| Affected::Allocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Deallocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Construct Sum = 152 Bytes | 0.15 KB | 0.00 MB
|| Affected::Destroy Sum = 152 Bytes | 0.15 KB | 0.00 MB
================================================================
(GFS)::Search(Graph), also known as Greedy-Best-First-Search, GBFS
|| Indexed_Path[6] = 0 -> 1 -> 3 -> 4 -> 6 -> 7
|| Lexical_Path[6] = A -> B -> D -> E -> G -> H
|| SumCost_Path[6] = A[0] -> B[3] -> D[5] -> E[9] -> G[11] -> H[13]
|| Total Cost = 13
|| Runtime = 0.000082 seconds
|| Tracking memory of Object[1]: "GFS::trace[]"
|| Tracking memory of Object[2]: "GFS::visited[]"
|| Tracking memory of Object[3]: "GFS::frontier[]"
|| Tracking memory of Object[4]: "GFS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 316 Bytes | 0.31 KB | 0.00 MB
|| Affected Memory Full Sum = 912 Bytes | 0.89 KB | 0.00 MB
|| Affected::Allocate Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Deallocate Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Construct Sum = 216 Bytes | 0.21 KB | 0.00 MB
|| Affected::Destroy Sum = 216 Bytes | 0.21 KB | 0.00 MB
================================================================
(UCS)::Search(Graph), also known as Uniform-Cost-Search
|| Indexed_Path[5] = 0 -> 2 -> 5 -> 6 -> 7
|| Lexical_Path[5] = A -> C -> F -> G -> H
|| SumCost_Path[5] = A[0] -> C[3] -> F[6] -> G[9] -> H[11]
|| Total Cost = 11
|| Runtime = 0.000093 seconds
|| Tracking memory of Object[1]: "UCS::trace[]"
|| Tracking memory of Object[2]: "UCS::cost[]"
|| Tracking memory of Object[3]: "UCS::visited[]"
|| Tracking memory of Object[4]: "UCS::frontier[]"
|| Tracking memory of Object[5]: "UCS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 372 Bytes | 0.36 KB | 0.00 MB
|| Affected Memory Full Sum = 1080 Bytes | 1.05 KB | 0.00 MB
|| Affected::Allocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Deallocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Construct Sum = 252 Bytes | 0.25 KB | 0.00 MB
|| Affected::Destroy Sum = 252 Bytes | 0.25 KB | 0.00 MB
================================================================
(IDS)::Search(Graph), also known as Iterative-Deepening-Search, IDDFS
|| Indexed_Path[5] = 0 -> 2 -> 5 -> 6 -> 7
|| Lexical_Path[5] = A -> C -> F -> G -> H
|| SumCost_Path[5] = A[0] -> C[3] -> F[6] -> G[9] -> H[11]
|| Total Cost = 11
|| Runtime = 0.000150 seconds
|| Tracking memory of Object[1]: "IDS::visited[]"
|| Tracking memory of Object[2]: "IDS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 172 Bytes | 0.17 KB | 0.00 MB
|| Affected Memory Full Sum = 1656 Bytes | 1.62 KB | 0.00 MB
|| Affected::Allocate Sum = 464 Bytes | 0.45 KB | 0.00 MB
|| Affected::Deallocate Sum = 464 Bytes | 0.45 KB | 0.00 MB
|| Affected::Construct Sum = 364 Bytes | 0.36 KB | 0.00 MB
|| Affected::Destroy Sum = 364 Bytes | 0.36 KB | 0.00 MB
================================================================
(HCS)::Search(Graph), also known as Hill-Climbing-Search
|| Indexed_Path[6] = 0 -> 1 -> 3 -> 4 -> 6 -> 7
|| Lexical_Path[6] = A -> B -> D -> E -> G -> H
|| SumCost_Path[6] = A[0] -> B[3] -> D[5] -> E[9] -> G[11] -> H[13]
|| Total Cost = 13
|| Runtime = 0.000043 seconds
|| Tracking memory of Object[1]: "HCS::path[]"
|| Tracking memory of Object[2]: ""
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 92 Bytes | 0.09 KB | 0.00 MB
|| Affected Memory Full Sum = 320 Bytes | 0.31 KB | 0.00 MB
|| Affected::Allocate Sum = 96 Bytes | 0.09 KB | 0.00 MB
|| Affected::Deallocate Sum = 96 Bytes | 0.09 KB | 0.00 MB
|| Affected::Construct Sum = 64 Bytes | 0.06 KB | 0.00 MB
|| Affected::Destroy Sum = 64 Bytes | 0.06 KB | 0.00 MB
================================================================
(ASS)::Search(Graph), also known as A-Star-Search, A*
|| Indexed_Path[5] = 0 -> 2 -> 5 -> 6 -> 7
|| Lexical_Path[5] = A -> C -> F -> G -> H
|| SumCost_Path[5] = A[0] -> C[3] -> F[6] -> G[9] -> H[11]
|| Total Cost = 11
|| Runtime = 0.000092 seconds
|| Tracking memory of Object[1]: "ASS::trace[]"
|| Tracking memory of Object[2]: "ASS::cost[]"
|| Tracking memory of Object[3]: "ASS::visited[]"
|| Tracking memory of Object[4]: "ASS::frontier[]"
|| Tracking memory of Object[5]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 380 Bytes | 0.37 KB | 0.00 MB
|| Affected Memory Full Sum = 1080 Bytes | 1.05 KB | 0.00 MB
|| Affected::Allocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Deallocate Sum = 288 Bytes | 0.28 KB | 0.00 MB
|| Affected::Construct Sum = 252 Bytes | 0.25 KB | 0.00 MB
|| Affected::Destroy Sum = 252 Bytes | 0.25 KB | 0.00 MB
================================================================
(SPS)::Search(Graph), using Dijkstra, also known as Shortest-Path-Search
|| Indexed_Path[5] = 0 -> 2 -> 5 -> 6 -> 7
|| Lexical_Path[5] = A -> C -> F -> G -> H
|| SumCost_Path[5] = A[0] -> C[3] -> F[6] -> G[9] -> H[11]
|| Total Cost = 11
|| Runtime = 0.000078 seconds
|| Tracking memory of Object[1]: "SPS::trace[]"
|| Tracking memory of Object[2]: "SPS::dist[]"
|| Tracking memory of Object[3]: "SPS::frontier[]"
|| Tracking memory of Object[4]: "ASS::path[]"
|| Detected Bad Memory Leak = 0 Bytes | 0.00 KB | 0.00 MB
|| Peak Used Memory At Time = 292 Bytes | 0.29 KB | 0.00 MB
|| Affected Memory Full Sum = 920 Bytes | 0.90 KB | 0.00 MB
|| Affected::Allocate Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Deallocate Sum = 240 Bytes | 0.23 KB | 0.00 MB
|| Affected::Construct Sum = 220 Bytes | 0.21 KB | 0.00 MB
|| Affected::Destroy Sum = 220 Bytes | 0.21 KB | 0.00 MB
================================================================
```
Sign in with Wallet
Connect another wallet