Yioop - PHP Search Engine

-- May 4 In-Class Exercise Thread

Possible triangles: 
 
I. Triangle (1, 2, 4) 
 
d(1,1) + d(4,2) >= d(4,2) 
1+ 2 >= 2
d(1,2) + d(2,4) >= d(1,4) 
1 + 2  >= 3
d(1,4) + d(4,2) >= d(1,2) 
3 + 2 >= 1 
 
Each edge obeys triangle inequality 
 
II. (Triangle 2, 3, 4) 
 
d(2,3) + d(2,4) >= d(3,4) 
1+ 2 >= 1
d(2,3) + d(3,4) >= d(2,4) 
1 + 1  >= 2
d(2,4) + d(3, 4) >= d(2,3) 
2 + 1 >= 1 
 
Each edge obeys triangle inequality 
 
III. Triangle (1, 3, 4) 
 
d(1,3) + d(1,4) >= d(4,3) 
2 + 3  >= 1
d(1,3) + d(3, 4) >= d(1,4) 
2 + 1 >= 3
d(1,4) + d(3,4) >= d(1,3) 
3+ 1 >= 2 
 
Each edge obeys triangle inequality 
 
IV. Triangle (1, 2, 3) 
 
d(2,3) + d(1, 3) >= d(1,2) 
1 + 2 >= 1
d(1,2) + d(2,3) >= d(1,3) 
1 + 1  >= 2
d(1,2) + d(1,3) >= d(3,2) 
1+ 2 >= 1 
 
Each edge obeys triangle inequality 
 
APPROX-TSP-TOUR:
(root = v1) 
 
Q = MAKE-QUEUE(G.V) 
[1, 0, 0
2, inf, NIL
3, inf, NIL
4, inf, NIL]
Q!=0 - (1)
U = 1,0,0
V = 2 , 0+1 < inf, true
V = 3 , 0+2 < inf, true
V = 4 , 0+3 < inf, true
Q = MAKE-QUEUE(G.V)
[2, 1, 1
3, 2, 1
4, 3, 1]
Q!=0 - (2)
U = 2,1,1
V = 3 , 1+1 < 2, true
V = 4 , 1+2 < 3, false
Q = MAKE-QUEUE(G.V)
[3, 2, 1
4, 3, 1]
Q!=0 - (3)
U = 3,1,1
V = 4 , 1+2 < 3, false
Q = MAKE-QUEUE(G.V)
[4, 3, 1]
Q!=0 - (4)
U = 4,3,1
V = empty set 
 
MST-PRIM => {1,2,3,4}
Thus, traversal order => 1,2,3,4
traversal cost = 1+1+1+3 = 6

<pre> Possible triangles: I. Triangle (1, 2, 4) d(1,1) + d(4,2) >= d(4,2) 1+ 2 >= 2 d(1,2) + d(2,4) >= d(1,4) 1 + 2 >= 3 d(1,4) + d(4,2) >= d(1,2) 3 + 2 >= 1 Each edge obeys triangle inequality II. (Triangle 2, 3, 4) d(2,3) + d(2,4) >= d(3,4) 1+ 2 >= 1 d(2,3) + d(3,4) >= d(2,4) 1 + 1 >= 2 d(2,4) + d(3, 4) >= d(2,3) 2 + 1 >= 1 Each edge obeys triangle inequality III. Triangle (1, 3, 4) d(1,3) + d(1,4) >= d(4,3) 2 + 3 >= 1 d(1,3) + d(3, 4) >= d(1,4) 2 + 1 >= 3 d(1,4) + d(3,4) >= d(1,3) 3+ 1 >= 2 Each edge obeys triangle inequality IV. Triangle (1, 2, 3) d(2,3) + d(1, 3) >= d(1,2) 1 + 2 >= 1 d(1,2) + d(2,3) >= d(1,3) 1 + 1 >= 2 d(1,2) + d(1,3) >= d(3,2) 1+ 2 >= 1 Each edge obeys triangle inequality APPROX-TSP-TOUR: (root = v1) Q = MAKE-QUEUE(G.V) [1, 0, 0 2, inf, NIL 3, inf, NIL 4, inf, NIL] Q!=0 - (1) U = 1,0,0 V = 2 , 0+1 < inf, true V = 3 , 0+2 < inf, true V = 4 , 0+3 < inf, true Q = MAKE-QUEUE(G.V) [2, 1, 1 3, 2, 1 4, 3, 1] Q!=0 - (2) U = 2,1,1 V = 3 , 1+1 < 2, true V = 4 , 1+2 < 3, false Q = MAKE-QUEUE(G.V) [3, 2, 1 4, 3, 1] Q!=0 - (3) U = 3,1,1 V = 4 , 1+2 < 3, false Q = MAKE-QUEUE(G.V) [4, 3, 1] Q!=0 - (4) U = 4,3,1 V = empty set MST-PRIM => {1,2,3,4} Thus, traversal order => 1,2,3,4 traversal cost = 1+1+1+3 = 6 </pre>

-- May 4 In-Class Exercise Thread

((resource:WhatsApp Image 2022-05-09 at 12.05.32 PM.jpeg|Resource Description for WhatsApp Image 2022-05-09 at 12.05.32 PM.jpeg))

-- May 4 In-Class Exercise Thread

Resource Description for WhatsApp Image 2022-05-09 at 12.26.20 PM.jpeg

((resource:WhatsApp Image 2022-05-09 at 12.26.20 PM (1).jpeg|Resource Description for WhatsApp Image 2022-05-09 at 12.26.20 PM (1).jpeg)) ((resource:WhatsApp Image 2022-05-09 at 12.26.20 PM.jpeg|Resource Description for WhatsApp Image 2022-05-09 at 12.26.20 PM.jpeg))

-- May 4 In-Class Exercise Thread

There are four possible triangles in the graph.

1. (Triangle 2, 3, 4)

d(2,3) + d(2,4) >= d(3,4) 1+ 2 >= 1 d(2,3) + d(3,4) >= d(2,4) 1 + 1 >= 2 d(2,4) + d(3, 4) >= d(2,3) 2 + 1 >= 1 Every edge obeys the triangle inequality

2. Triangle (1, 2, 4)

d(1,1) + d(4,2) >= d(4,2) 1+ 2 >= 2 d(1,2) + d(2,4) >= d(1,4) 1 + 2 >= 3 d(1,4) + d(4,2) >= d(1,2) 3 + 2 >= 1

 Every edge obeys the triangle inequality

3. Triangle (1, 3, 4)

d(1,3) + d(1,4) >= d(4,3) 2 + 3 >= 1 d(1,3) + d(3, 4) >= d(1,4) 2 + 1 >= 3 d(1,4) + d(3,4) >= d(1,3) 3+ 1 >= 2

Each edge obeys the triangle inequality

4. Triangle (1, 2, 3)

d(2,3) + d(1, 3) >= d(1,2) 1 + 2 >= 1 d(1,2) + d(2,3) >= d(1,3) 1 + 1 >= 2 d(1,2) + d(1,3) >= d(3,2) 1+ 2 >= 1

Each edge obeys the triangle inequality

APPROX-TSP-TOUR: (root = v1)

Q = MAKE-QUEUE(G.V) [1, 0, 0 2, inf, NIL 3, inf, NIL 4, inf, NIL] Q!=0 - (1) U = 1,0,0 V = 2 , 0+1 < inf, true V = 3 , 0+2 < inf, true V = 4 , 0+3 < inf, true Q = MAKE-QUEUE(G.V) [2, 1, 1 3, 2, 1 4, 3, 1] Q!=0 - (2) U = 2,1,1 V = 3 , 1+1 < 2, true V = 4 , 1+2 < 3, false Q = MAKE-QUEUE(G.V) [3, 2, 1 4, 3, 1] Q!=0 - (3) U = 3,1,1 V = 4 , 1+2 < 3, false Q = MAKE-QUEUE(G.V) [4, 3, 1] Q!=0 - (4) U = 4,3,1 V = empty set

MST-PRIM is {1,2,3,4} Thus, traversal order is 1,2,3,4 traversal cost = 1+1+1+3 = 6

There are four possible triangles in the graph. 1. (Triangle 2, 3, 4) d(2,3) + d(2,4) >= d(3,4) 1+ 2 >= 1 d(2,3) + d(3,4) >= d(2,4) 1 + 1 >= 2 d(2,4) + d(3, 4) >= d(2,3) 2 + 1 >= 1 Every edge obeys the triangle inequality 2. Triangle (1, 2, 4) d(1,1) + d(4,2) >= d(4,2) 1+ 2 >= 2 d(1,2) + d(2,4) >= d(1,4) 1 + 2 >= 3 d(1,4) + d(4,2) >= d(1,2) 3 + 2 >= 1 Every edge obeys the triangle inequality 3. Triangle (1, 3, 4) d(1,3) + d(1,4) >= d(4,3) 2 + 3 >= 1 d(1,3) + d(3, 4) >= d(1,4) 2 + 1 >= 3 d(1,4) + d(3,4) >= d(1,3) 3+ 1 >= 2 Each edge obeys the triangle inequality 4. Triangle (1, 2, 3) d(2,3) + d(1, 3) >= d(1,2) 1 + 2 >= 1 d(1,2) + d(2,3) >= d(1,3) 1 + 1 >= 2 d(1,2) + d(1,3) >= d(3,2) 1+ 2 >= 1 Each edge obeys the triangle inequality APPROX-TSP-TOUR: (root = v1) Q = MAKE-QUEUE(G.V) [1, 0, 0 2, inf, NIL 3, inf, NIL 4, inf, NIL] Q!=0 - (1) U = 1,0,0 V = 2 , 0+1 < inf, true V = 3 , 0+2 < inf, true V = 4 , 0+3 < inf, true Q = MAKE-QUEUE(G.V) [2, 1, 1 3, 2, 1 4, 3, 1] Q!=0 - (2) U = 2,1,1 V = 3 , 1+1 < 2, true V = 4 , 1+2 < 3, false Q = MAKE-QUEUE(G.V) [3, 2, 1 4, 3, 1] Q!=0 - (3) U = 3,1,1 V = 4 , 1+2 < 3, false Q = MAKE-QUEUE(G.V) [4, 3, 1] Q!=0 - (4) U = 4,3,1 V = empty set MST-PRIM is {1,2,3,4} Thus, traversal order is 1,2,3,4 traversal cost = 1+1+1+3 = 6

-- May 4 In-Class Exercise Thread

((resource:IMG-6980.jpg|Resource Description for IMG-6980.jpg))

-- May 4 In-Class Exercise Thread

((resource:inclass1.jpeg|Resource Description for inclass1.jpeg)) ((resource:inclass2.jpeg|Resource Description for inclass2.jpeg))

-- May 4 In-Class Exercise Thread

((resource:8.jpg|Resource Description for 8.jpg))

-- May 4 In-Class Exercise Thread

((resource:400BC3F5-4D9F-4C1E-8D50-7755975D51B5.jpeg|Resource Description for 400BC3F5-4D9F-4C1E-8D50-7755975D51B5.jpeg))

-- May 4 In-Class Exercise Thread

((resource:IMG_20220509_145739__01.jpg|Resource Description for IMG_20220509_145739__01.jpg))

-- May 4 In-Class Exercise Thread

((resource:unnamed (1).jpg|Resource Description for unnamed (1).jpg))