I need help with Dr.Racket (Scheme, Lisp) . I just have to Implement \"find-solu

Question

I need help with Dr.Racket (Scheme, Lisp).

I just have to Implement "find-solution using A* search". I don't know what it is I just know that it's a Heuristic-based and it combines DFS and Breath-First Search. Please help.

Main ideas of A* search
. not every sequence needs to be explored
. visited successors can be ignored
. explore the most promising sequence first

ACCUMULATOR INVARIANTS:
. paths is a list of all seqsstarting at b generated so far that have no repeated nodes
. visited is the list of boards encountered on all sequences explored so far

However, below is an example of a Breath-First Search.

; find-solution-bfs: board --> seq

; Purpose: To find a solution to the given board

(define (find-solution-bfs b)

    (local [; search-paths: lseq --> seq

              ; Purpose: To find a solution to b by searching all possible paths

              ; ACCUMULATOR INVARIANT:
              ; paths is all paths starting at b generated so far from shortest to longest
              (define (search-paths paths)
                   (cond [(equal? (first (first paths)) WIN) (first paths)]
                         [else
                            (local [(define children (generate-children (first (first paths))))
                                (define new-paths (map (lambda (c) (cons c (first paths)))
                                                                           children))]
                 (search-paths (append (rest paths) new-paths)))]))]
(reverse (search-paths (list (list b))))))

Explanation / Answer

Program to print BFS traversal:

#include<iostream>
#include <list>

using namespace std;

// This class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void BFS(int s); // prints BFS traversal from a given source s
};

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;

// Create a queue for BFS
list<int> queue;

// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);

// 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;

while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();

// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for(i = adj[s].begin(); i != adj[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}

// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

cout << "Following is Breadth First Traversal " << "(starting from vertex 2) ";
g.BFS(2);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.