Create three different search methods - Breadth first, depth first and iterative

Question

Create three different search methods - Breadth first, depth first and iterative deepening, in Python or Java.

The goal of this programming assignment is to develop search methods that we discussed in the class. To this effect, let us consider the road map of Romania (presented in Figure 3.2, page 68 of the book). Assume that the input is a text file that appears as presented in table 1. This essentially specifies the entire map. In each line, it specifies the distance between a pair of cities. Note that the distances are commutative, i.e., the distance between cities A and B is the same as the distance between B and A.

You are required to program three different search methods - Breadth first depth first and iterative deepening.

While submitting your code, you are also required to submit sample out- put as a separate pdf file The sample output file should have the paths between Arad and Bucharest, Sibiu and Eforie and between Drobeta and Fagaras.

Arad Sibiu 149

Zerind Arad 75

Oradea Zerind 71

Arad Timisoara 118

Timisora Lugoj 111

...

Table 1: Sample Input file

Chapter 3. Solving Problems by Searching 68 Oradea 71 Neamt 87 Zerind 151 75 lasi Arad 140 92 Sibiu Fagaras Vaslui 118 80 Kimnicu Vilcea Timisoara 142 Pitest211 Lugoj 97 98 70 Hirsova 146 85 Mehadia 101 Urziceni 86 75 138 Bucharest Drobeta 120 90 Eforie Craiova Giurgiu Figuure 3.2 A simplified road map of part of Romania

Explanation / Answer

Problem statement - Implement Depth-First Search and Breadth-First Search algorithms in the road map of Romania. The code keeps track of nodes expanded and computes the length of this list. All inputs will be given through command line in the following format. java SearchRomania searchtype srccityname destcityname Examples - java SearchRomania DFS arad oradea java SearchRomania BFS sibiu iasi */ import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; class Node { String city; LinkedList list; } public class SearchRomania { static Node[] node = new Node[20]; static LinkedList path = new LinkedList(); static LinkedList visited = new LinkedList(); static Queue queue = new LinkedList(); static boolean goalReached = false; static Map map = new HashMap(); public static void initialize() { for (int i = 0; i < 20; i++) { node[i] = new Node(); node[i].list = new LinkedList(); } node[0].city = "oradea"; node[1].city = "zerind"; node[2].city = "arad"; node[3].city = "timisoara"; node[4].city = "lugoj"; node[5].city = "mehadia"; node[6].city = "dobreta"; node[7].city = "sibiu"; node[8].city = "rimnicu_vilcea"; node[9].city = "craiova"; node[10].city = "fagaras"; node[11].city = "pitesti"; node[12].city = "bucharest"; node[13].city = "giurgiu"; node[14].city = "urziceni"; node[15].city = "vaslui"; node[16].city = "iasi"; node[17].city = "neamt"; node[18].city = "hirsova"; node[19].city = "eforie"; node[0].list.add(node[7]); node[0].list.add(node[1]); node[1].list.add(node[2]); node[1].list.add(node[0]); node[2].list.add(node[7]); node[2].list.add(node[3]); node[2].list.add(node[1]); node[3].list.add(node[2]); node[3].list.add(node[4]); node[4].list.add(node[5]); node[4].list.add(node[3]); node[5].list.add(node[6]); node[5].list.add(node[4]); node[6].list.add(node[9]); node[6].list.add(node[5]); node[7].list.add(node[2]); node[7].list.add(node[10]); node[7].list.add(node[0]); node[7].list.add(node[8]); node[8].list.add(node[9]); node[8].list.add(node[11]); node[8].list.add(node[7]); node[9].list.add(node[6]); node[9].list.add(node[11]); node[9].list.add(node[8]); node[10].list.add(node[12]); node[10].list.add(node[7]); node[11].list.add(node[12]); node[11].list.add(node[9]); node[11].list.add(node[8]); node[12].list.add(node[10]); node[12].list.add(node[13]); node[12].list.add(node[11]); node[12].list.add(node[14]); node[13].list.add(node[12]); node[14].list.add(node[12]); node[14].list.add(node[18]); node[14].list.add(node[15]); node[15].list.add(node[16]); node[15].list.add(node[14]); node[16].list.add(node[17]); node[16].list.add(node[15]); node[17].list.add(node[16]); node[18].list.add(node[19]); node[18].list.add(node[14]); node[19].list.add(node[18]); } static void dfs(Node current, Node goal) { if (goalReached == false) { path.add(current); visited.add(current); if (current.city.equals(goal.city)) { goalReached = true; for (Node p : path) { System.out.println(p.city); } } else { for (Node next : current.list) { if (!visited.contains(next)) { dfs(next, goal); } } path.removeLast(); } } } static void bfs(Node current, Node goal) { if (!visited.contains(current)) { visited.add(current); } if (goalReached == false) { for (Node child : current.list) { if (!visited.contains(child)) { visited.add(child); queue.add(child); map.put(child, current); if (child.city.equals(goal.city)) { goalReached = true; path.add(child); path.add(current); while (path.getLast() != visited.get(0)) { current = (Node) map.get(current); path.add(current); } while (!path.isEmpty()) { System.out.println(path.removeLast().city); } return; } } } bfs(queue.remove(), goal); } } public static void main(String[] args) { initialize(); Node start=node[0]; Node goal=node[1]; for (int i = 0; i < 20; i++) { if (node[i].city.equals(args[1])) { start = node[i]; } if (node[i].city.equals(args[2])) { goal =node[i]; } } if (args[0].equals("DFS")) { dfs(start, goal); } else if (args[0].equals("BFS")) { bfs(start, goal); } System.out.println("Total number of nodes expanded: " + visited.size()); } }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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