Programming component

Please read the information on assignments and Python carefully to ensure that you are

using the correct version of Python and the correct style. For full marks, you are required

not only to have a correct solution, but also to adhere to the requirements of the assignment question and the style guide, including aspects of the design recipe!

Although submitting tests is not required, it is highly recommended thay you test your code. For each assignment question, create a testing file that imports your submission and tests the code. Do not submit your testing file.

The helper functions total and safe from the model solutions of Assignment 1 have been made available for your use in the file asst4helpers.py.

For any of the programming questions in this assignment / you may import any of the follow ing files: asst4helpers.py, check.py, graphs.py, equiv.py, and as well as built-in modules

such as math, itertools, copy, and random.

Be sure to read the instructions on the Python requirements page to ensure that you have imported the files as required.

Note:

P1: You can assume that weights are positive integers. P2: You can assume that weights are positive integers.

P1. [12 marks] Write a function safe_hill that consumes a graph and produces a list of IDs of vertices that forms a safe set, not necessarily of maximum total weight. You will use the heuristic of hill-climbing, starting with an arbitrary feasible solution of your choice.

At each step, you will either add a new vertex to the solution, or you will find a vertex

in the current solution to replace with a vertex outside the current solution such that the total weight of the new solution is greater than the total weight of the current solution.

If neither such change can be made, your function should stop the search and return the current solution.

Submit your work in a file with the name safehill.py.

P2. [13 marks] Write a function safe_set_bt that consumes a graph and produces a list of IDs of vertices that forms a safe set of maximum total weight. Your function should use backtracking.

Submit your work in a file with the name safesetbt.py.

测试用例自动生成与选择程序

需求

1.能随机生成n个测试数据作为基础测试用例集，并将数据输出到exel表格文件，如下图所示（数据个数、数据范围和维度可以自定义，比如随机生成-100 ~ 100 的整数数据，维度选择1、2、3维）。

2.随机生成k个测试数据放入基础测试用例集（个数自选，维度和上面一样）。新增了几个测试数据如下图所示，然后对这个测试用例集进行异常检测。（需要循环i次）

3.异常检测模块（可以检测出异常数据了，判断异常数据是否属于k个测试用例中的，如果是则放入到n个基础测试用例中），下图为一次异常检测结果。

并将k个数据中的异常数据保留到基础测试用例集中（假如k=3，有1个异常数据，2个正常数据，则只将1个异常的数据保留在基础测试用例集中，异常数据的Anomaly值为1，）

异常检测模块代码如下

import os
os.environ["KMP_DUPLICATE_LIB_OK"]="TRUE"


import pandas as pd
dataset = pd.read_excel(r'C:\Users\hechen\Desktop\1.xlsx')


data = dataset.sample(frac=1, random_state=123)
data_unseen = dataset.drop(data.index)
data.reset_index(drop=True, inplace=True)
data_unseen.reset_index(drop=True, inplace=True)


from pycaret.anomaly import *
exp_ano1 = setup(data, normalize = True, session_id = 123)


iforest = create_model('iforest', fraction = 0.2)


iforest_results = assign_model(iforest)
#可以读取到Anomaly等于1的数据
for i in range(41):
    if iforest_results['Anomaly'][i] == 1:       
        print(iforest_results["a"][i])
        print(iforest_results["b"][i])
        print(iforest_results["c"][i])
iforest_results.head()

4.最后输出最终的测试用例集到Excel表格，并计算此次运行时间。