You are camping in a haunted forest and hear a scream outside your tent. You lea

Question

You are camping in a haunted forest and hear a scream outside your tent. You leave to investigate and see a traveler approach your campsite, only to collapse dead before you can ask them any questions. You see a piece of paper in their hand, reach down, and grab it. Looking at the paper, you notice it is a map of the forest, drawn as an undirected graph, where vertices represent landmarks in the forest, and edges represent paths between the landmarks. (Paths start and end at landmarks and do not cross.) One of the vertices on your map you recognize as where you currently are, and several of the vertices on the outer boundary of the map are labeled EXIT.

On closer examination, you see that someone has writtena real number between 0 and 1 next to each vertex and each edge. This number represents the probability of encountering a ghost along the corresponding edge or at the corresponding vertex. Your plan is to leave the forest immediately.

a) Give an example G such that the path from your current location to the EXIT node that minimizes the expected number of ghost encounters is different from the path that minimizes the probability of encountering any ghosts at all. Explain why these two criteria lead to different answers.

b) Describe and analyze an efficient algorithm to find a path from your current location to an arbitrary EXIT node, such that the total number of expected ghost encounters along the path is as small as possible. Make sure to account for both the vertex and edge probabilities. HINT: this is clearly an SSSP problem, but you must identify how to reduce the input G to a form that can be solved by SSSP. Include the cost of this transformation in the running-time analysis.

c) Describe and analyze an efficient algorithm to find a path from your current location to an arbitrary EXIT node, such that the probability of encountering any ghosts at all is minimized.

Explanation / Answer

Graph:

A graph is a pictorial representation of objects which are connected by links. These objects are represented by vertices, and the links are called edges.

Formally, a graph G is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.

In a graph G, if all the edges are bidirectional then it undirected graph and if the edges are unidirectional then it is directed graph.

The graph are most commonly represented in two ways.

In the given problem the graph is undirected graph and we need to find the shortest path. To do so we use Dijikstra’s Algorithm.

The time complexity of Dijikstra Algorithm is O(V2). So we need to reduce the input graph. To reduce the input graph it should be represented by adjacency lists. This can be reduced to O(Elog v) with the help of binary heap.

// The main function that calulates distances of shortest paths from current position p to all vertices. It is a O(ElogV) function

void dijkstra(struct Graph* graph, int p)

{

    int V = graph->V;// Get the number of vertices in graph

    int dist[V];     

// minHeap represents set E

    struct MinHeap* minHeap = createMinHeap(V);

for (int i = 0; i < V; ++i)

    {

        dist[i] = INT_MAX;

        minHeap->a[i] = newMinHeapNode(v, dist[v]);

        minHeap->ind[i] = i;

    }

// set dist value of p to 0 to start with p

    minHeap->a[p] = newMinHeapNode(p, dist[p]);

    minHeap->ind[p]   = p;

    dist[p] = 0;

    reduceKey(minHeap, p, dist[p]);

// Initially size of min heap is equal to V

    minHeap->size = V;

    while (!isEmpty(minHeap))

    {

        // find the vertex with minimum distance

        struct MinHeapNode* minHeapNode = findMin(minHeap);

        int j = minHeapNode->v; // Store the vertex number found

// Traverse through all adjacent vertices of j and update their distances

        struct AdjListNode* q = graph->a[j].head;

        while (q != NULL)

        {

            int i = q->exit;

            if (isInMinHeap(minHeap, i) && dist[j] != INT_MAX && q->weight + dist[j] < dist[i])

            {

                dist[i] = dist[j] + q->weight;

// update distance value in min heap also

                reduceKey(minHeap, i, dist[i]);

            }

            q = q->next;

        }

    }

// print the calculated shortest distances

    show(dist, V);

}

Here we used adjacent lists and we have reduced it so that we can easily find the shortest path to exit.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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