Traveling Salesman algorithm using Dynamic Programming technique.

 Algorithm:

Algorithm TSP(distances)

{

 n:=length(distances);

 memo:=a 2D array of size n x (2^n) filled with None;

 dp(pos, visited)

 {

 if visited == (2^n) - 1 then

 return distances[pos][0], [0];

 if memo[pos][visited] is not None then

 return memo[pos][visited];

 shortest_dist := Infinity;

 shortest_path := [];

 for next_pos from 0 to n-1 do

 {

 if visited & (1 << next_pos) == 0 then

 {

 dist, path = dp(next_pos, visited | (1 << next_pos));

 dist := dist + distances[pos][next_pos];

 if dist < shortest_dist then

 {

 shortest_dist := dist;

shortest_path := [pos] + path;

 }

 }

 }

 memo[pos][visited] := (shortest_dist, shortest_path);

 return memo[pos][visited];

 }

 path := dp(0, 1);

 return path;

}


Source Code:

import sys

from typing import List, Tuple

def tsp(distances: List[List[int]]) -> Tuple[int, List[int]]:

 n = len(distances)

 memo = [[None] * (1 << n) for _ in range(n)]

 def dp(pos: int, visited: int) -> Tuple[int, List[int]]:

 if visited == (1 << n) - 1:

 return distances[pos][0], [0]

 if memo[pos][visited] is not None:

 return memo[pos][visited]

 shortest_dist, shortest_path = sys.maxsize, []

 for next_pos in range(n):

 if visited & (1 << next_pos) == 0:

 dist, path = dp(next_pos, visited | (1 << next_pos))

 dist += distances[pos][next_pos]

 if dist < shortest_dist:

shortest_dist = dist

shortest_path = [pos] + path

 memo[pos][visited] = (shortest_dist, shortest_path)

 return memo[pos][visited]

 _, path = dp(0, 1)

 return _, path

distances = [

 [0,3,2,0,3],

 [0,0,0,4,5],

 [0,0,0,5,4],

 [0,4,5,0,2],

 [3,5,4,2,0]

]

dist, path = tsp(distances)

print("Shortest distance:", dist)

print("Shortest path:", path)


Comments

Post a Comment

Popular posts from this blog

2. Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.Create 3 private networks namely N1, N2 and N3, Send the data from N1 to N2. If the packets are transferring from N3, it shouldn't accept the packets. Accordingly develop the security features.

Image
 In Cisco Packet Tracer, you can simulate this scenario by configuring access control lists (ACLs) on routers to control the flow of traffic between the networks. Here's a basic example: Procedure  1. **Create the Networks:**    - Place three routers on the workspace and label them R1, R2, and R3.    - Connect the routers as follows:      - Connect R1 to R2 and R3.      - Connect R2 to R3.    - Assign IP addresses to the router interfaces for each network (N1, N2, N3). 2. **Configure Router ACLs:**    - Access the CLI of each router.    For R1 (assuming FastEthernet interfaces):    ```bash    enable    configure terminal    interface FastEthernet0/0    ip address <N1_IP> <Subnet_Mask>    exit    interface FastEthernet0/1    ip address <N2_IP> <Subnet_Mask>    exit    access-li...
Read more

Kruskal algorithm using greedy technique.

Algorithm: Algorithm Kruskal(E, cost, n, t) { Construct a heap out of the edge costs using Heapify; for i:=1 to n, do parent[i]:=—1; i := O; mincost := 0.0; while ( (i < n — 1) and (heap not empty)) do       { Delete a minimum cost edge (u, v) from the heap and reheapify using Adjust; j:=Find(u); k := Find(v); if (j!=k) then        { i:=i+1; t[i, 1] := u; t[i, 2]:=v; mincost := mincost + cost[u, v]; Union(j, k); }                 } if (i != n — 1) then write ("No spanning tree"); else return mincost; } Source Code: def kruskal(E, cost, n): # E is the edge set, cost is the cost matrix, n is the number of vertices T = [] # T is the set of edges in the tree S = [] # S is the set of vertices in the tree while len(T) < n ...
Read more