[go: up one dir, main page]
Menu ▾ ▴

[046f16]: / greed.py  Maximize  Restore  History

Download this file

103 lines (75 with data), 2.7 kB 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
# -*- coding: utf-8 -*-

#

# Author: Marcelo Costa Toyama - mctoyama@gmail.com

#

# License GPL v 3.0

#

# Description:

# Ant Colony optimization for TSP PROBLEMS

#



# each ant starts the trail in a distinct city

#

# update pheromone only the best path



# TSPLIB

# http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/





import math

from graph.distance_matrix import *

from graph.tsplib import *



# -------------------------------------------------------------------------

# class greed

# -------------------------------------------------------------------------

class Greed:

    """Greed algorithm"""



    def __init__(self, p_distance_matrix):

        """Constructor:

            - p_distance_matrix: distance matrix for nodes in the graph"""

        self._matrix = p_distance_matrix

        self._agents = self._matrix.all_nodes()

        self._best_path = list()

        self._best_path_len = -1



    def run(self):

        """Run the greed algorithm"""



        v_all_paths = {}

        v_best_path = list()

        v_best_path_len = -1



        for v_agent in self._agents:



            v_path = list()

            v_path.append(v_agent)



            v_cities = self._matrix.all_nodes()

            v_cities.remove( v_agent )

            v_cities.sort()



            v_end = False



            while not v_end:



                v_from = v_path[-1]

                v_next_city = -1

                v_next_dist = -1

                v_dist_array = {}



                for i in v_cities:

                    v_dist_array[i] = self._matrix.get(v_from, i)



                for v_city, v_dist in v_dist_array.items():

                    if v_next_dist == -1:

                        v_next_dist = v_dist

                        v_next_city = v_city

                    elif v_next_dist > v_dist:

                        v_next_dist = v_dist

                        v_next_city = v_city



                v_path.append(v_next_city)

                v_cities.remove( v_next_city)



                if len(v_cities) == 0:

                    v_end = True



            v_all_paths[v_agent] = v_path



        for v_city, v_path in v_all_paths.items():

            if v_best_path_len == -1:

                v_best_path = v_path

                v_best_path_len = self._matrix.path_len( v_best_path )

            elif v_best_path_len > self._matrix.path_len( v_path ):

                v_best_path = v_path

                v_best_path_len = self._matrix.path_len( v_best_path )



        return( v_best_path )



if __name__ == "__main__":



    # TSP LIB problem

    tsp_matrix = TSPLIB_matrix("berlin52.tsp")



    g = Greed( tsp_matrix )



    ret = g.run()



    print("greed path: ", ret)

    print("greed length: ", tsp_matrix.path_len( ret ))