Source code for titan_pylib.others.SA

 1import sys
 2from time import process_time
 3from math import exp
 4from typing import TypeVar
 5from titan_pylib.algorithm.random.random import Random
 6
 7

[docs]
 8class State:
 9
10    def __init__(self) -> None:
11        pass
12

[docs]
13    def copy(self) -> "State":
14        pass


15
16

[docs]
17class SA:
18
19    Changed = TypeVar("Changed")
20
21    def __init__(self):
22        self.random = Random()
23

[docs]
24    def make_ans_init(self) -> tuple[State, int]:
25        return

26

[docs]
27    def modify(self, state: State) -> tuple[int, Changed]:
28        # state は変更される
29        return

30

[docs]
31    def rollback(self, state: State, changed: Changed) -> None:
32        return

33

[docs]
34    def sovle(
35        self, START_TEMP: float = 100, END_TEMP: float = 10, TIME_LIMIT: float = 1.8
36    ) -> tuple[State, int]:
37        START_TIME = process_time()
38        random = self.random
39        ans, score = self.make_ans_init()
40        vest_ans = ans.copy()
41        vest_score = score
42        cnt = 0
43        while True:
44            now_time = process_time() - START_TIME
45            if now_time > TIME_LIMIT:
46                break
47            cnt += 1
48            diff_score, changed = self.modify(ans)
49            new_score = score + diff_score
50            temp = START_TEMP + (END_TEMP - START_TEMP) * now_time / TIME_LIMIT
51            arg = new_score - score
52            if arg >= 1 or exp(arg / temp) > random.random():
53                score = new_score
54                if new_score > vest_score:
55                    vest_score = new_score
56                    vest_ans = ans.copy()
57            else:
58                self.rollback(ans, changed)
59        print(f"{cnt=}", file=sys.stderr)
60        return vest_ans, vest_score