ShortestPathComparison/comparator.py at master · thommath/ShortestPathComparison · GitHub

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
import argparse
from typing import List
import random
import math
from code import A


def generate_graph() -> List[List[str]]:
    x: int = round(random.random()*100)
    y: int = round(random.random()*100)
    options: str = "wmfgr"

    graph: List[List[str]] = []
    for n in range(x):
        line: List[str] = []
        for m in range(y):
            rand = random.random()
            elem = None
            if rand < 0.3 and n > 0:
                elem = graph[n-1][m]
            elif rand < 0.6 and n > 0 and m > 0:
                elem = line[-1]

            # If not elem set, pick random elem
            if not elem:
                elem = options[math.floor(random.random()*len(options))]

            line.append(elem)
        graph.append(line)

    a = (0, 0)
    b = (0, 0)
    while a == b:
        a = (math.floor(x*random.random()), math.floor(y*random.random()))
        b = (math.floor(x*random.random()), math.floor(y*random.random()))

    graph[a[0]][a[1]] = 'A'
    graph[b[0]][b[1]] = 'B'

    return graph


def run_algorithms(grid, penelty_for_suboptimal_solution:int = 200):
    a = A(grid)

    # Run algorithms

    a.h = lambda n: (n - a.goal)
    res_a = a.best_first_search(lambda x: x.f)

    a.h = lambda n: (n - a.goal) * (n.g / (n-a.start)) if n-a.start > 0 else n-a.goal
    res_a2 = a.best_first_search(lambda x: x.f)

    a.h = lambda n: (n - a.goal) * 1.001
    res_a3 = a.best_first_search(lambda x: x.f)

    res_d = a.best_first_search(lambda x: x.g)

    score: List[int] = []

    score.append((res_a[0]-res_d[0])*penelty_for_suboptimal_solution + len(res_a[2]))
    score.append((res_a2[0]-res_d[0])*penelty_for_suboptimal_solution + len(res_a2[2]))
    score.append((res_a3[0]-res_d[0])*penelty_for_suboptimal_solution + len(res_a3[2]))
    score.append(len(res_d[2]))
#    score_d = len(res_d[2])
#    score_b = (res_b[0]-res_d[0])*penelty_for_suboptimal_solution + len(res_b[2])

    return score


def write_file(grid: List[List[str]], file: str):
    # Write the map to file
    with open(file, 'w') as f:
        for l in grid:
            s = ''
            for i in l:
                s+=i
            f.write(s + '\n')


def main(iterations: int) -> None:
    """Main run function"""

    score: List[int] = []
    victories: List[int] = []

    for i in range(iterations):
        print('Iteration ', i)

        grid: List[List[str]] = generate_graph()
        write_file(grid, 'compare-' + str(i) + '.txt')

        res = run_algorithms(grid)

        if score == []:
            score = res
        else:
            score = [score[i]+res[i] for i in range(len(res))]

        if victories == []:
            victories = [0 for i in range(len(res))]
        victories[res.index(min(res))] += 1

        # Print result
        print('A*\t', score[0], victories[0])
        print('A*g\t', score[1], victories[1])
        print('A*2\t', score[2], victories[2])
        print('Dji.\t', score[-1], victories[-1])
#        print('BFS\t', score[3], victories[3])
        print()

    with open('out.txt', 'w') as f:
        f.write(str(score) + '\n' + str(victories))


    # Write the map to file
#    if output != '':
#        with open(output, 'w') as f:
#            for l in grid:
#                s = ''
#                for i in l:
#                    s+=i
#                f.write(s + '\n')

    # # Run algorithms
    # res_a = a.best_first_search(lambda x: x.f)
    # res_d = a.best_first_search(lambda x: x.g)
    # res_b = a.best_first_search(lambda x: 0)

    # # Print result
    # print('A*\t', res_a[0].g, '\tclosed nodes:\t', len(res_a[2]))
    # print('Dji.\t', res_d[0].g, '\tclosed nodes:\t', len(res_d[2]))
    # print('BFS\t', res_b[0].g, '\tclosed nodes:\t', len(res_b[2]))


if __name__ == "__main__":
    # Define arguments
    parser = argparse.ArgumentParser()
    # parser.add_argument("-o", "--output", default='', help="Path to output file")
    # parser.add_argument("-u", "--uncertain", action='store_const', const=True, default=False, help="Pay accuracy for speed")
    parser.add_argument("-i", "--iterations", default=1, help="Define number of iterations")

    # Parse arguments
    args = parser.parse_args()

    # Run the program
   # main(args.uncertain, args.output)
    main(int(args.iterations))