API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 19th, 2018
65
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.40 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5.  
  6. struct Node
  7. {
  8. int stepPathCost, numberOfChildren, heuristics, perviousPathCost;
  9. std::string name, path;
  10. std::vector<Node*> childNodes;
  11. };
  12. struct openSetAndclosedSetNode
  13. {
  14. std::string name, path;
  15. int stepPathCost;
  16. Node *referedNode;
  17. };
  18. Node* createNode(int stepPathCost, int numberOfChildren, int heuristics, std::string name, int perviousPathCost, std::string path, std::vector<Node*> childNodes)
  19. {
  20. Node *pnn = new Node();
  21. pnn->stepPathCost = stepPathCost;
  22. pnn->numberOfChildren = numberOfChildren;
  23. pnn->heuristics = heuristics;
  24. pnn->name = name;
  25. pnn->path = path;
  26. pnn->perviousPathCost = perviousPathCost;
  27. pnn->childNodes = childNodes;
  28. return pnn;
  29. }
  30. void searchForExistance(Node *pnn, std::string name, Node *&temp)
  31. {
  32. if (pnn->name == name) {
  33. temp = pnn;
  34. return;
  35. }
  36. if (pnn->childNodes.empty() == true) return;
  37.  
  38. for (int i = 0; i<pnn->numberOfChildren; i++) {
  39. //std::cout<<pnn->name<<"\n";
  40. searchForExistance(pnn->childNodes.at(i), name, temp);
  41. if (pnn->childNodes.at(i + 1) == NULL) return;
  42. }
  43. }
  44. void removeNullValues(std::vector<Node*> &pnn) {
  45. for (int k = 0; k < pnn.size(); k++) {
  46. if (pnn[k] == NULL) pnn.erase(pnn.begin()+k);
  47. }
  48. }
  49. void InsertChild(Node* pnn, int stepPathCost, int numberOfChildren, int heuristics, std::string name, int perviousPathCost, std::string path, Node *root)
  50. {
  51. Node *temp, *temp2;
  52. for (int i = 0; i<pnn->numberOfChildren; i++)
  53. {
  54. temp2 = NULL;
  55. std::cin >> name;
  56. std::cin >> stepPathCost;
  57. path = pnn->path + name;
  58. perviousPathCost = pnn->stepPathCost + pnn->perviousPathCost;
  59. searchForExistance(root, name, temp2);
  60. if (temp2 == NULL) {
  61. std::cin >> numberOfChildren >> heuristics;
  62. std::vector<Node*> childNodes;
  63. childNodes.empty();
  64.  
  65. temp = new Node();
  66. temp = createNode(stepPathCost, numberOfChildren, heuristics, name, perviousPathCost, path, childNodes);
  67. pnn->childNodes.insert(pnn->childNodes.begin() + i, temp);
  68. //std::cout<<"Child Added\n";
  69. pnn->childNodes.push_back(NULL);
  70. InsertChild(temp, stepPathCost, numberOfChildren, heuristics, name, perviousPathCost, path, root);
  71. }
  72. else {
  73. temp = new Node();
  74. temp = createNode(stepPathCost, temp2->numberOfChildren, temp2->heuristics, temp2->name, perviousPathCost, path, temp2->childNodes);
  75. pnn->childNodes.insert(pnn->childNodes.begin() + i, temp);
  76. //std::cout<<"Child Added\n";
  77. pnn->childNodes.push_back(NULL);
  78. }
  79. }
  80. }
  81. void sorting(std::vector<openSetAndclosedSetNode> &v) {
  82. for (int i = 1; i<v.size(); ++i) {
  83. for (int j = 0; j<v.size() - 1; ++j) {
  84. if (v[j].stepPathCost > v[i].stepPathCost) std::swap(v[j], v[i]);
  85. }
  86. }
  87. }
  88. void calculateAstar(Node *pnn, std::vector<openSetAndclosedSetNode> openSet, std::vector<std::string> closedSet, std::string theGoal, int &path, std::string &AStarPath)
  89. {
  90. openSetAndclosedSetNode x;
  91. bool isExist = false;
  92. auto i = openSet.begin();
  93.  
  94. while (!openSet.empty()) {
  95. if (i->name == theGoal) {
  96. path = i->stepPathCost;
  97. AStarPath = i->path;
  98. return;
  99. }
  100. else {
  101.  
  102. pnn = openSet.at(0).referedNode;
  103. removeNullValues(pnn->childNodes);
  104. i = openSet.begin();
  105. closedSet.push_back(i->name);
  106. openSet.erase(openSet.begin(), openSet.begin() + 1);
  107.  
  108. for (int j = 0; j<pnn->numberOfChildren; j++) {
  109. x.stepPathCost = pnn->childNodes.at(j)->stepPathCost + pnn->childNodes.at(j)->perviousPathCost + pnn->childNodes.at(j)->heuristics;
  110. x.name = pnn->childNodes.at(j)->name;
  111. x.path = pnn->path + x.name;
  112. x.referedNode = pnn->childNodes.at(j);
  113.  
  114. for (auto k = openSet.begin(); k != openSet.end(); k++) {
  115. if (k->name == x.name) {
  116. if (k->stepPathCost > x.stepPathCost) {
  117. for (int ff = 0; ff<x.referedNode->numberOfChildren; ff++) {
  118. x.referedNode->childNodes.at(ff)->perviousPathCost = x.stepPathCost;
  119. x.referedNode->childNodes.at(ff)->path = x.path + x.referedNode->childNodes.at(ff)->name;
  120. }
  121. openSet.erase(k);
  122. openSet.push_back(x);
  123. isExist = true;
  124. break;
  125. }
  126. else isExist = true;
  127. }
  128. }
  129. if (isExist == false) openSet.push_back(x);
  130. isExist = false;
  131. }
  132. sorting(openSet);
  133. i = openSet.begin();
  134. }
  135. }
  136. std::cout << "No Goal Achieved";
  137. }
  138.  
  139. void UniformCostSearch(Node *pnn, std::vector<openSetAndclosedSetNode> openSet, std::vector<std::string> closedSet, std::string theGoal, int &path, std::string &UniformCostSearchPath)
  140. {
  141. openSetAndclosedSetNode x;
  142. bool isExist = false;
  143. auto i = openSet.begin();
  144. while (!openSet.empty()) {
  145. if (i->name == theGoal) {
  146. path = i->stepPathCost;
  147. UniformCostSearchPath = i->path;
  148. return;
  149. }
  150. else {
  151.  
  152. pnn = openSet.at(0).referedNode;
  153. removeNullValues(pnn->childNodes);
  154. i = openSet.begin();
  155. closedSet.push_back(i->name);
  156. openSet.erase(openSet.begin(), openSet.begin() + 1);
  157.  
  158. for (int j = 0; j<pnn->numberOfChildren; j++) {
  159. x.stepPathCost = pnn->childNodes.at(j)->stepPathCost + pnn->childNodes.at(j)->perviousPathCost;
  160. x.name = pnn->childNodes.at(j)->name;
  161. x.path = pnn->path + x.name;
  162. x.referedNode = pnn->childNodes.at(j);
  163. for (auto k = openSet.begin(); k != openSet.end(); k++) {
  164. if (k->name == x.name) {
  165. if (k->stepPathCost > x.stepPathCost) {
  166. for (int ff = 0; ff<x.referedNode->numberOfChildren; ff++) {
  167. x.referedNode->childNodes.at(ff)->perviousPathCost = x.stepPathCost;
  168. x.referedNode->childNodes.at(ff)->path = x.path + x.referedNode->childNodes.at(ff)->name;
  169. }
  170. openSet.erase(k);
  171. openSet.push_back(x);
  172. isExist = true;
  173. break;
  174. }
  175. else isExist = true;
  176. }
  177. }
  178. if (isExist == false) openSet.push_back(x);
  179. isExist = false;
  180. }
  181. sorting(openSet);
  182. i = openSet.begin();
  183. }
  184. }
  185. std::cout << "No Goal Achieved";
  186. }
  187.  
  188. void GreedyFirstSearch(Node *pnn, std::vector<openSetAndclosedSetNode> openSet, std::vector<std::string> closedSet, std::string theGoal, int &path, std::string &GreedyFirstSearchPath)
  189. {
  190. openSetAndclosedSetNode x;
  191. bool isExist = false;
  192. auto i = openSet.begin();
  193. while (!openSet.empty()) {
  194. if (i->name == theGoal) {
  195. path = i->stepPathCost;
  196. GreedyFirstSearchPath = i->path;
  197. return;
  198. }
  199. else {
  200.  
  201. pnn = openSet.at(0).referedNode;
  202. removeNullValues(pnn->childNodes);
  203. i = openSet.begin();
  204. closedSet.push_back(i->name);
  205. openSet.erase(openSet.begin(), openSet.begin() + 1);
  206.  
  207. for (int j = 0; j<pnn->numberOfChildren; j++) {
  208. x.stepPathCost = pnn->childNodes.at(j)->heuristics;
  209. x.name = pnn->childNodes.at(j)->name;
  210. x.path = pnn->path + x.name;
  211. x.referedNode = pnn->childNodes.at(j);
  212. for (auto k = openSet.begin(); k != openSet.end(); k++) {
  213. if (k->name == x.name) {
  214. if (k->stepPathCost > x.stepPathCost) {
  215. for (int ff = 0; ff<x.referedNode->numberOfChildren; ff++) {
  216. x.referedNode->childNodes.at(ff)->perviousPathCost = x.stepPathCost;
  217. x.referedNode->childNodes.at(ff)->path = x.path + x.referedNode->childNodes.at(ff)->name;
  218. }
  219. openSet.erase(k);
  220. openSet.push_back(x);
  221. isExist = true;
  222. break;
  223. }
  224. else isExist = true;
  225. }
  226. }
  227. if (isExist == false) openSet.push_back(x);
  228. isExist = false;
  229. }
  230. sorting(openSet);
  231. i = openSet.begin();
  232. }
  233. }
  234. std::cout << "No Goal Achieved";
  235. }
  236.  
  237. std::string DepthFirstSearch(Node *pnn, std::vector<openSetAndclosedSetNode> openSet, std::vector<std::string> closedSet, std::string theGoal)
  238. {
  239. openSetAndclosedSetNode x;
  240. auto i = openSet.begin();
  241. bool isExist = false;
  242.  
  243. while (!openSet.empty()) {
  244. if (i->name == theGoal) {
  245. return i->path;
  246. }
  247. else {
  248. pnn = openSet.at(0).referedNode;
  249. removeNullValues(pnn->childNodes);
  250. i = openSet.begin();
  251. closedSet.push_back(i->name);
  252. openSet.erase(openSet.begin(), openSet.begin() + 1);
  253.  
  254. for (int j = pnn->numberOfChildren - 1; j >= 0; j--) {
  255. x.name = pnn->childNodes.at(j)->name;
  256. x.path = pnn->path + x.name;
  257. x.referedNode = pnn->childNodes.at(j);
  258.  
  259. for (auto k = openSet.begin(); k!=openSet.end(); k++) {
  260. if (k->name == x.name)isExist = true;
  261. }
  262.  
  263. if (isExist == false)openSet.insert(openSet.begin(), x);
  264. isExist = false;
  265. }
  266. i = openSet.begin();
  267. }
  268. }
  269. std::cout << "No Goal Achieved";
  270. return "";
  271. }
  272.  
  273. std::string BredthFirstSearch(Node *pnn, std::vector<openSetAndclosedSetNode> openSet, std::vector<std::string> closedSet, std::string theGoal)
  274. {
  275. openSetAndclosedSetNode x;
  276. auto i = openSet.begin();
  277. bool isExist = false;
  278.  
  279. while (!openSet.empty()) {
  280. if (i->name == theGoal) {
  281. return i->path;
  282. }
  283. else {
  284. pnn = openSet.at(0).referedNode;
  285. removeNullValues(pnn->childNodes);
  286. i = openSet.begin();
  287. closedSet.push_back(i->name);
  288. openSet.erase(openSet.begin(), openSet.begin() + 1);
  289.  
  290. for (int j = 0; j<pnn->numberOfChildren; j++) {
  291. x.name = pnn->childNodes.at(j)->name;
  292. x.path = pnn->path + x.name;
  293. x.referedNode = pnn->childNodes.at(j);
  294.  
  295. for (auto k = openSet.begin(); k!=openSet.end(); k++) {
  296. if (k->name == x.name)isExist = true;
  297. }
  298.  
  299. if (isExist == false) openSet.push_back(x);
  300. isExist = false;
  301. }
  302. i = openSet.begin();
  303. }
  304. }
  305. std::cout << "No Goal Achieved";
  306. return "";
  307. }
  308.  
  309. int main()
  310. {
  311. Node *root = new Node();
  312. std::string name, theGoal, path = "";
  313. int numberOfChildren, heuristics, perviousPathCost = 0;
  314. std::vector<openSetAndclosedSetNode> openSet;
  315. std::vector<std::string> closedSet;
  316.  
  317. std::cout << "Construct the root as follow\nName, NumberOfChildren, Heuristics\n";
  318. std::cin >> name;
  319. std::cin >> numberOfChildren >> heuristics;
  320. std::vector<Node*> childNodes;
  321. childNodes.empty();
  322.  
  323. std::cout << "Construct the Tree as follow\nName, PathCost, NumberOfChildren, Heuristics\nIf the Node already existed\nName, PathCost\n";
  324. root = createNode(0, numberOfChildren, heuristics, name, perviousPathCost, path, childNodes);
  325. InsertChild(root, 0, numberOfChildren, heuristics, name, perviousPathCost, path, root);
  326. std::cout << "Enter the Goal Name\n";
  327. std::cin >> theGoal;
  328.  
  329. openSetAndclosedSetNode x;
  330. int pathCost = 0;
  331. std::string searchPaths;
  332.  
  333. x.stepPathCost = heuristics;
  334. x.name = name;
  335. x.referedNode = root;
  336. openSet.push_back(x);
  337.  
  338. /* Depth First Search */
  339. std::string DepthFirstSearchPath = DepthFirstSearch(root, openSet, closedSet, theGoal);
  340. std::cout << "(DepthFirstSearch)" << root->name << DepthFirstSearchPath << "\n";
  341.  
  342. /* Bredth First Search */
  343. std::string BredthFirstSearchPath = BredthFirstSearch(root, openSet, closedSet, theGoal);
  344. std::cout << "(BredthFirstSearch)" << root->name << BredthFirstSearchPath << "\n";
  345.  
  346. /* A* */
  347. calculateAstar(root, openSet, closedSet, theGoal, pathCost, searchPaths);
  348. std::reverse(searchPaths.begin(), searchPaths.end());
  349. std::cout << "(A*)" << searchPaths << root->name << "=" << pathCost << "\n";
  350.  
  351. /* Uniform search cost */
  352. UniformCostSearch(root, openSet, closedSet, theGoal, pathCost, searchPaths);
  353. std::reverse(searchPaths.begin(), searchPaths.end());
  354. std::cout << "(UniformSearch)" << searchPaths << root->name << "=" << pathCost << "\n";
  355.  
  356. ///* Greedy First Search */
  357. GreedyFirstSearch(root, openSet, closedSet, theGoal, pathCost, searchPaths);
  358. std::reverse(searchPaths.begin(), searchPaths.end());
  359. std::cout << "(Greedy)" << searchPaths << root->name << "=" << pathCost << "\n";
  360.  
  361. system("pause");
  362. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!