Question regarding Basic simulation

[deminyau]

Good Day.

Question regarding Basic simulation

For basic simulation

1) Why we evaluate Vertex with id 4 first instead of 2,1,3 Since bfs/dfs is blind search algo, shoudn't we start from vertex with id 1? (the head should be warehouse node)

2) In vehicle 3, why will we go from 0->3->1->0, (we understand that the capacity of truck is not full so can add more customers) Can we use 0->4->1->0 or 0->2->1->0 instead since they are the same concept.

3) Similarly to question 3, why can't we tranverse 0->1->3->0? Are there any algorithm for the evaluation of nodes? (Based on distance, id etc) In the example output, it seems like every sequence of evaluated node are randomize.

4) We are required to do only one of the searching technique right since it wrote in the question BFS / DFS

Thank you for taking your time to answer our questions!

[NeverOnTimeSdnBhd]

Hi First of all, thanks for your questions and sorry for the parts I didn't make it clear.

1. Yes, logically it should always explore node with ID=1 first before 2, and followed by 3, 4, ..., N. When I am coding the sample solution for this question, I used some quick trick so that I can code less (yes I am lazy definitely), I am not using the conventional DFS/BFS. Thus, if you traverse your DFS/BFS search tree from ID 1 to N, then you should get 0 -> 1 -> 3 -> 0 for third route. In fact, this is just a matter of how you traverse the whole graph. There is no rule saying that you must always search from ID 1 so sequence is really not a matter here (as long as you are sure that the final tour found is having the lowest cost).

2. Nope, we can't use 0 -> 4 -> 1 -> 0 or 0 -> 2 -> 1 -> 0, these two routes will result in higher cost (distance travelled by vehicles) in total. Please kindly refer the following two tours, both of them are having higher cost than the one using route 0 -> 3 -> 1 -> 0 (Cost: 346.2483982181608).

Tour with 0 -> 4 -> 1 -> 0

Basic Simulation  
Tour
Tour Cost: 420.98628823988776
Vehicle 1
0 -> 2 -> 0
Capacity: 8
Cost: 173.29743217947575
Vehicle 2
0 -> 3 -> 0
Capacity: 6
Cost: 123.32072007574396
Vehicle 3
0 -> 4 -> 1 -> 0
Capacity: 6
Cost: 124.36813598466804

Tour with 0 -> 2 -> 1 -> 0

Basic Simulation  
Tour
Tour Cost: 357.0036710057715
Vehicle 1
0 -> 4 -> 0
Capacity: 5
Cost: 48.41487374764082
Vehicle 2
0 -> 3 -> 0
Capacity: 6
Cost: 123.32072007574396
Vehicle 3
0 -> 2 -> 1 -> 0
Capacity: 9
Cost: 185.26807718238663

3. I think this question is similar to Q1, yes you definitely can do 0 -> 1 -> 3 -> 0 as the order doesn't matter here (by order I mean reading the route from front or back, not the order of every node in a route).

4. Yes, either one.

P.S. I think the term I used in the question is a bit confusing. I am sorry about that. For Basic Simulation, instead of saying ... using Breadth-First-Search/Depth-First-Search traversal implementation ..., I think I should re-word it as ... using Breadth-First-Traversal/Depth-First-Traversal implementation .... You should not stop searching after you found a complete tour, you need to search for the lowest cost tour instead (the easiest way is to traverse whole search tree, but you can do some trick fasten the searching a bit).

[deminyau]

Good Day.

1) Can use different package for different solution so that the code is more tidy? Because we divide the tasks among group members

2) Can we use tree to fulfill BFS/DFS output? If no, can we use sequential traversal with reference to euclidean distance? If both approach is not correct, may we know what is the correct approach?

Thank you for taking your time to answer our questions!

[NeverOnTimeSdnBhd]

Hi

1. Unfortunately this is not something I can decide. It depends on your lecturer (since he/she will be the one giving you marks). If you ask my opinion, I will say I prefer make it as one package, and I personally think the code is more tidy this way (it also kind of prove that the data structure you choose to represent graph is able to support 3 types of simulations). However, I am not sure how you want to do this so I can't really say much on this and of course for me you always have the freedom to do whatever you want as long as you can produce what question is asking for. Again, please kindly consult your lecturer for permission on this!

2. I am not so sure whether I am understanding your question correctly, are you asking whether is it possible to find the lowest cost tour using search tree? If so, then my answer is Yes. You can represent your whole search space as a search tree and traverse the tree using either Breath-First-Traversal / Depth-First-Traversal. If I do not understand it correctly / or you need more clarification, more questions are welcome.

Note: The Basic Simulation output don't have to be exactly the same with the one shown in the question (let say you test it with the input in the question). It can be vary as long as the tour cost is the lowest one (for Basic Simulation).

[deminyau]

Thank you 😆

[zulfathihanafi]

Hi admin, May I ask for the Basic Simulation, we need to use either DFS/BFS for our search, but if i'm not mistaken, we learn in class that both search is uninformed search(does not take any cost into account). So how to implement it in this case,as we need to return the cost?

[NeverOnTimeSdnBhd]

Hi

Since some of you are keep confusing about DFS/BFS implementation, hence I created a documentation for the clarification. Here is the link: Basic Simulation Please have a read on that and if you still don't understand any concept or require further clarification then can raise the issue again.

Thanks!