最少次数切水果问题

问题描述

小明在玩切水果游戏，已知屏幕上有若干水果，只允许用直线切水果，一次只允许划出一条直线，直线上的水果都会被消除掉；请求出小明最少需要切多少次才能把屏幕上的水果都切掉。已知屏幕由40X50的小方格组成，经过每个方格划出的直线最多只有4条，如下图所示经过红色方格（标注为8）能划出直线最多为4条，其中相同数字的方格属于同一直线（0为空）；屏幕左上角坐标为(0,0)，右下角坐标为(39,49)。

输入描述

第一行输入整数N（0<N<=36），接下来N行，每行两个整数X，Y（0<=X<40, 0<=Y<50）用空格隔开，表示水果所在方格的X坐标和Y坐标，不同水果的坐标一定不同，输入保证合法。

输出描述

程序输出一个整数并换行，表示小明需要切水果的最少次数。

贪心算法（贪婪最佳优先搜索）

贪心算法(贪婪算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。

算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

以当前的切水果次数最少问题，若使用贪心算法求出的结果，有时候不一定是最优的结果，因为有可能成本问题不是最好的，但是它是相对接近最优解的。

贪心算法经典问题：信号塔城市覆盖问题。

现在有北京、上海、天津、深圳、广州、成都、杭州、大连共8个城市需要覆盖广播信号，针对该工程，供应商推出5种信号塔，K1｛北京、上海、天津｝，K2{广州、北京、深圳}、K3｛成都、上海、杭州｝、K4{上海、天津}、K5｛杭州、大连｝。为了控制成本，要求尽可能的用最少的信号塔覆盖全部城市。

站点	覆盖城市
K1	北京，上海，天津
K2	广州，北京，深圳
K3	成都，上海，杭州
K4	上海，天津
K5	杭州，大连

信号塔覆盖问题使用贪心算法解决思路如下：

列举需要覆盖的城市：北京、上海、天津、广州、深圳、成都、杭州、大连；
列举出每个广播站点的覆盖地区数量；
每次找到广播站点的覆盖地区数量值最大；
下一次比较的时候，去掉上次覆盖地区，重新找到覆盖地区数量最大的广播站点。

也就是每一步都选择可以覆盖城市最多的站点，达到局部最优，直至全部城市覆盖完成。

解决思路

与上述的信号塔覆盖问题相似，站点可以等效为当前问题的切水果的位置，城市则可以等效为水果，用最少的站点覆盖全部城市，与当前问题：用最少的次数切完全部水果，问题相近。这里切水果问题也是需要寻找最少的切水果次数遍历全部水果。

先用二维列表position记录下所有水果的位置坐标；
再用一个三维列表map_list表示每个位置的水果在横切、竖切、左上至右下切、右上至左下切四种方式下能够切到的其他的水果的index；
然后用一个一维列表count记录每个位置的水果在一刀下能切掉水果的最多数目；
接着每次都选择能够切掉最多水果的那个位置下的那一刀，并将已经切掉的水果从记录水果位置坐标的二维列表position中删除；
之后依照新的位置记录二维列表position重新建立map_list和count，重复上述过程，直至所有水果都消除。

python程序流程图

程序演示

这里为了方便图示，特将水果横、纵坐标限制在10范围以内，以便绘图。

设置水果数量为15
坐标依次为(0,0)，(1,7)，(2,0)，(2,3)，(3,2)，(3,5)，(4,3)，(4,4)，(6,3)，(6,7)，(6,9)，(7,5)，(8,1)，(8,3)，(8,8)。

终端程序运行结果

运行结果：共切7次完成全部水果的遍历。

7次水果切向位置示意图如下，

原始水果位置图，

切水果第1刀位置，

切水果第2刀位置，

切水果第3、4、5、6、7刀位置示意图，

python源程序

import platform
import csv
import copy
import time

# 获取当前环境版本
print("当前环境python版本为" + platform.python_version())
map_list = []  # 用于记录有水果位置四个方向上的能切到其它水果的index
count = []  # 用于记录每个水果位置下四个方向上可以切到其它水果的最大数量
dir_str = ['垂直方向切', '水平方向切', '左上至右下切', '右上至左下切']  # 定义切水果方向提示字符串list
File = "./fruit5" # 读取的文件名（.csv）

'''
Hori函数对序号为index水果位置处，水平方向上的水果进行计数
'''


def Hori(index, position):
    pos_now = position[index]
    length = len(position)
    for i in range(length):  # 遍历除去当前位置的所有水果
        if (i != index):
            node = position[i]
            if (node[1] == pos_now[1]):  # 判断水果的y坐标是否相同
                map_list[index][0].append(i)


'''
Vert函数对序号为index水果位置处，垂直方向上的水果进行计数
'''


def Vert(index, position):
    pos_now = position[index]
    length = len(position)
    for i in range(length):  # 遍历除去当前位置的所有水果
        if (i != index):
            node = position[i]
            if (node[0] == pos_now[0]):  # 判断水果的x坐标是否相同
                map_list[index][1].append(i)  # 记录下水果index值


'''
Left函数对序号为index水果位置处，左上至右下方向上的水果进行计数
'''


def Left(index, position):
    pos_now = position[index]
    length = len(position)
    for i in range(length):  # 遍历除去当前位置的所有水果
        if (i != index):
            node = position[i]
            if ((node[0] - node[1]) == (pos_now[0] - pos_now[1])):  # 判断水果的y-x坐标是否相同
                map_list[index][2].append(i)  # 记录下水果index值


'''
Right函数对序号为index水果位置处，右上至左下方向上的水果进行计数
'''


def Right(index, position):
    pos_now = position[index]
    length = len(position)
    for i in range(length):  # 遍历除去当前位置的所有水果
        if (i != index):
            node = position[i]
            if ((node[0] + node[1]) == (pos_now[0] + pos_now[1])):  # 判断水果的x+y坐标是否相同
                map_list[index][3].append(i)  # 记录下水果index值


'''
计算map_list中每个水果下四个方向上的切到水果数量最大值
'''


def CalMaxCount():
    n = len(map_list)
    for i in range(n):
        m = map_list[i]
        max_count = 0
        for j in range(4):
            length_m = len(m[j])
            max_count = max_count if max_count > length_m else length_m
        count[i] = max_count


'''
记录每个水果位置下，四个方向上水果的index
'''


def ConstMap(position):
    global map_list
    map_list.clear()  # 清缓存
    length = len(position)
    map_list = [[[] for n in range(4)] for m in range(length)]
    for i in range(length):
        Hori(i, position)
        Vert(i, position)
        Left(i, position)
        Right(i, position)
    CalMaxCount()


def PositionClear(index, position):
    direction = 0  # 0-水平，1-垂直，2-左上至右下，3-右上至左下
    max_count = 0
    length = len(position)
    m = map_list[index]
    for i in range(4):
        length_m = len(m[i])
        if (length_m > max_count):
            max_count = length_m
            direction = i
    node = map_list[index][direction]  # 当前水果index在direction方向上(数量最多)的水果合集
    print('切割方向：' + dir_str[direction])
    node.sort(reverse=True)  # 对水果合集里的index进行从大到小排序(为了避免先删除低index的值，会导致索引错位)
    for i in node:
        position.pop(i)  # 删除水果index在direction方向上的水果元素
    try:
        position.pop(index)  # 删除当前水果
    except:
        print()


def MaxValueIndex(count):
    max_value = max(count)
    count_max_index = count.index(max_value)
    return count_max_index


'''
从文件中读取水果数量和坐标
'''


def read_data(filename):
    f = open(filename + ".csv", 'r')
    reader = csv.reader(f)
    rows = [row for row in reader]
    data = [list(map(int, row)) for row in rows]
    n = data.pop(0)[0]  # 提取水果数量总数
    pos = copy.deepcopy(data)  # 水果位置list合集
    f.close()
    return [n, pos]


# main
N = 0
position = []
if (input("请选择数据输入方式：默认回车为从文件读取，任意输入非空字符后回车进入手动输入模式") == ""):
    [N, position] = read_data(File)
else:
    N = int(input('请输入整数水果数量N（0<N<=36）'))
    if (type(N) != int):
        print('当前输入为非整数，请重新输入！')
    if (N <= 0) or (N > 36):
        print('输入整数超出范围(0~36)，请重新输入！')
    print('当前输入的水果数量为：' + str(N))
    print('请依次输入水果的x,y坐标（每输入一个坐标，回车确认）')
    for i in range(N):
        x, y = map(int, input('输入第' + str(i + 1) + '个水果坐标，共' + str(N) + '个水果' + '(x,y空格隔开):').split())
        position.append([x, y])

time_start = time.perf_counter()  # 记录开始时间

num = 0  # 切水果计数

while (len(position) > 0):
    count = [0 for i in range(len(position))]
    ConstMap(position)
    max_index = MaxValueIndex(count)
    print('切水果坐标为(' + str(position[max_index][0]) + ',' + str(position[max_index][1]) + ')')
    PositionClear(max_index, position)
    num = num + 1

time_end = time.perf_counter()  # 记录结束时间
time_sum = time_end - time_start  # 计算的时间差为程序的执行时间，单位为秒/s
print("运行时间" + str(time_sum) + "s")
print('共切次数' + str(num))

广度优先搜索算法

广度优先搜索算法（Breadth-First Search，BFS）是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。

广度优先搜索过程：

首先扩展根节点；
接着扩展根节点的所有后继节点；
然后再扩展后继节点的后继，依此类推；
在下一层任何节点扩展之前搜索树上的本层深度的所有节点都已经被扩展。

简单二叉树上的广度优先搜索（要扩展的节点箭头指示）示意图，

在本文中的切水果问题上，运用广度优先搜索的方式解决，大致思路是，先获取水果矩阵上所有可以构成的并且符合要求的直线（横、竖、左上至右下切、右上至左下），这些直线将作为每个节点执行动作的组合合集。从根节点扩展所有后继节点，对所扩展的后继节点进行搜索，检验该节点下水果剩余数是否为0，若不为0，则继续扩展后继节点，循环上述搜索检验过程，直至找到水果剩余数为0时终止。

解决思路

先用二维列表F记录下所有水果的位置坐标；
再用一个三维列表L记录水果矩阵上构成的所有直线（横、竖、左上至右下切、右上至左下），及当前直线上的所经过的水果位置坐标合集；
对根节点进行所有后继节点扩展，将节点信息用字典fringe依次存入；
从字典fringe取出第一个节点（队列先进先出原则），判断该节点（即直线）下，水果剩余是否为0，若为0则终止程序，否则继续扩展该节点下所有的后继节点，将后继节点信息依次存入字典fringe中；
重复上述步骤，从字典fringe取出下一个节点（队列先进先出原则），继续检验判断至当前节点下水果剩余是否为0。

python程序流程图

程序演示

输入水果数量为5的随机水果位置数据集合，运行结果如下所示，

5个随机生成的水果坐标表，

序号	x	y
1	26	2
2	38	20
3	32	35
4	17	36
5	21	12

终端程序运行结果（水果5个）示意图，

6个随机生成的水果坐标表，

序号	x	y
1	11	35
2	20	20
3	5	11
4	5	44
5	18	0
6	26	10

终端程序运行结果（水果6个）示意图，

这里仅演示水果数量为5和6的运行结果，更大数量由于运行时间问题不进行演示（具体分析见：算法对比）

python源程序

import platform
import csv
import copy
import time

'''
从文件中读取水果数量和坐标
'''


def read_data(filename):
    f = open(filename + ".csv", 'r')
    reader = csv.reader(f)
    rows = [row for row in reader]
    data = [list(map(int, row)) for row in rows]
    n = data.pop(0)[0]  # 提取水果数量总数
    pos = copy.deepcopy(data)  # 水果位置list合集
    f.close()
    return [n, pos]


# 获取当前环境版本
print("当前环境python版本为" + platform.python_version())

File = "./fruit5"  # 默认读取的水果文件
Fnum = 0  # 水果数量初始化
F = []  # 水果位置合集
L = []  # 有水果的直线集合
rowth = 40
colth = 50

if (input("请选择数据输入方式：默认回车为从文件读取，任意输入非空字符后回车进入手动输入模式") == ""):
    [Fnum, F] = read_data(File)
else:
    Fnum = int(input('请输入整数水果数量N（0<N<=36）'))
    if (type(Fnum) != int):
        print('当前输入为非整数，请重新输入！')
    if (Fnum <= 0) or (Fnum > 36):
        print('输入整数超出范围(0~36)，请重新输入！')
    print('当前输入的水果数量为：' + str(Fnum))
    print('请依次输入水果的x,y坐标（每输入一个坐标，回车确认）')
    for i in range(Fnum):
        x, y = map(int, input('输入第' + str(i + 1) + '个水果坐标，共' + str(Fnum) + '个水果' + '(x,y空格隔开):').split())
        F.append([x, y])

time_start = time.time()  # 记录开始时间
# time_start = time.perf_counter()  # 记录开始时间
# create search space(遍历水果，将所有有水果的直线列出，构成搜索空间）
for x in F:
    # row line横线记录
    m = "r" + str(x[0])
    templinename = []
    templinename.append(m)
    flag = True
    for y in L:  # 去重复直线
        if templinename[0] == y[0]:
            flag = False
    if flag:
        col = 1
        cellset = []
        num = 0
        while col <= colth:
            cell = [x[0], col]
            if cell in F:
                cellset.append(cell)
                num = num + 1
            col = col + 1
        templinename.append(num)
        templinename.append(cellset)
        L.append(templinename)

    # column line
    m = "c" + str(x[1])
    templinename = []
    templinename.append(m)
    flag = True
    for y in L:
        if templinename[0] == y[0]:
            flag = False
    if flag:
        row = 1
        cellset = []
        num = 0
        while row <= rowth:
            cell = [row, x[1]]
            if cell in F:
                cellset.append(cell)
                num = num + 1
            row = row + 1
        templinename.append(num)
        templinename.append(cellset)
        L.append(templinename)

        # LD
        row1 = x[0]
        col1 = x[1]
        while row1 > 0 and col1 > 0:
            row1 = row1 - 1
            col1 = col1 - 1
        if row1 <= 0 or col1 <= 0:
            m = "LD" + str(row1 + 1) + ":" + str(col1 + 1)
        templinename = []
        templinename.append(m)
        flag = True
        for y in L:
            if templinename[0] == y[0]:
                flag = False
        if flag:
            row = row1 + 1
            col = col1 + 1
            cellset = []
            num = 0
            while row <= rowth and col <= colth:
                cell = [row, col]
                if cell in F:
                    cellset.append(cell)
                    num = num + 1
                row = row + 1
                col = col + 1
            templinename.append(num)
            templinename.append(cellset)
            L.append(templinename)
        # RD
        row1 = x[0]
        col1 = x[1]
        while row1 > 0 and col1 <= colth:
            row1 = row1 - 1
            col1 = col1 + 1
        if row1 <= 0 or col1 > colth:
            m = "RD" + str(row1 + 1) + ":" + str(col1 - 1)
        templinename = []
        templinename.append(m)
        flag = True
        for y in L:
            if templinename[0] == y[0]:
                flag = False
        if flag:
            row = row1 + 1
            col = col1 - 1
            cellset = []
            num = 0
            while row <= rowth and col > 0:
                cell = [row, col]
                if cell in F:
                    cellset.append(cell)
                    num = num + 1
                row = row + 1
                col = col - 1
            templinename.append(num)
            templinename.append(cellset)
            L.append(templinename)
print("直线坐标: ", end="")
print(L)
# 搜索
# 创建根节点
temptreenode = {}
x = 'root'
temptreenode.setdefault('history', []).append(x)
temptreenode['fnumrest'] = Fnum  # Fnum为水果输入总数
temptreenode['Fnode'] = copy.deepcopy(F)  # F水果坐标合集
tempaction = []
for k in L:
    tempaction.append(k[0])
temptreenode['actionselect'] = copy.deepcopy(tempaction)
fringe = []
print("节点数据结构: ", end="")
print(temptreenode)
fringe.append(temptreenode)
fringenum = 1

# time_start = time.perf_counter()  # 记录开始时间
# time_start = time.perf_counter()  # 记录开始时间
while len(fringe) > 0:  # 边缘集合空？
    temptreenode = {}
    temptreenode = fringe.pop(0)
    fringenum = fringenum - 1
    if temptreenode['fnumrest'] == 0:  # 剩余水果数为0，成功
        print('sucess', end='')
        print(temptreenode['history'])
        break
    else:  # 扩展
        linesselect = []
        linesselect = copy.deepcopy(temptreenode['actionselect'])
        fruitnodes = []
        fruitnodes = copy.deepcopy(temptreenode['Fnode'])
        for x in linesselect:  # linf为该节点下所有可扩展节点（直线）
            # 判断直线上是否有未切的水果（直线上的水果集合与节点中剩余的水果集合是否相交）
            selected = False
            for k in L:
                if x == k[0]:
                    break  # 找到待扩展节点x在直线列表中的位置k[2]，以获取该直线对应的水果集合
            for y in k[2]:
                if y in fruitnodes:
                    selected = True
            if selected:  # 该直线上还有未切的水果，可以扩展
                # 创建新的子节点
                newtreenode = {}
                newtreenode['fnumrest'] = temptreenode['fnumrest']
                newtreenode['history'] = copy.deepcopy(temptreenode['history'])
                newtreenode['history'].append(x)
                newtreenode['actionselect'] = copy.deepcopy(linesselect)
                newtreenode['actionselect'].remove(x)
                newtreenode['Fnode'] = copy.deepcopy(fruitnodes)
                # 剩余水果数计算
                for k in L:
                    if k[0] == x:
                        break
                # 找到action直线k的信息
                templine = copy.deepcopy(k)
                for h in temptreenode['Fnode']:  # 根据水果集合，将#action直线上的水果移掉，重新计算剩余水果个数
                    if h in templine[2]:
                        newtreenode['Fnode'].remove(h)
                        newtreenode['fnumrest'] = newtreenode['fnumrest'] - 1
                fringe.append(newtreenode)  # 广度优先
                fringenum = fringenum + 1

time_end = time.time()  # 记录结束时间
# time_end = time.perf_counter()  # 记录结束时间
time_sum = time_end - time_start  # 计算的时间差为程序的执行时间，单位为秒/s 如果当前输出运行时间为0，请改用time.perf_counter()
print("运行时间" + str(time_sum) + "s")
print('共切次数' + str(len(temptreenode['history']) - 1))

算法对比（时间复杂度）

算法的时间复杂度，是一个用于度量一个算法的运算时间的一个描述，本质是一个函数，根据这个函数能在不用具体的测试数据来测试的情况下，粗略地估计算法的执行效率，换句话讲时间复杂度表示的只是代码执行时间随数据规模增长的变化趋势。

这里为了对比上述提出的贪心算法以及广度优先搜索算法两者之间的时间复杂度，在相同的运行环境以及相同的解决问题的水果集合下，进行程序运行时间上的对比。所指的程序运行时间具体描述为，解决问题程序所执行的时间，具体阶段在两个算法的程序流程图上已经标记。

为了实现相同的大量水果数据集下进行测试对比，故设计了一个简单的随机水果坐标小程序，进行任意水果数量的坐标生成。程序如下，

# 随机生成水果坐标
import random
import csv

x_max = 40
y_max = 50
N = 5  # 随机水果数量
filename = "fruit5"
f = open(filename + ".csv", 'w', newline='')
writer = csv.writer(f)
writer.writerow([N])
position = []  # 记录水果坐标
while len(position) < N:
    x_temp = random.randint(0, x_max - 1)
    y_temp = random.randint(0, y_max - 1)
    if [x_temp, y_temp] in position:
        continue
    else:
        position.append([x_temp, y_temp])
        writer.writerow([x_temp, y_temp])  # 写入文件中

f.close()

# print(position)

运行环境，系统Windows10，cpu-i5-8300H，内存16GB，平台IDE-Pycharm2020，python版本3.9.7。

这里分别随机生成了水果数量为5，6，7，8，9，10，50，100，1000，1500的数据集合，进行测试，实验结果如下两表所示，

贪心算法运行结果表，

水果总数	运行时间/s	切水果次数
5	0.0007159	5
10	0.0007554	7
20	0.0018087	13
50	0.009439	23
100	0.0559677	36
1000	7.6476467	40
1500	18.2472405	40

广度优先搜素运行结果表，

水果总数	运行时间/s	切水果次数
5	5.437181	5
6	9.936121	5
7	>600	--
8	>600	--
9	>600	--
10	>600	--

从上两表结果分析看到，对于当前贪心算法，水果数量较少时，运行时间比较稳定，大致是毫秒的运行时间，而当数量上升到一定时，运行时间将大幅增大，如水果为5~50之间时，运行时间大致为0.7ms~9.4ms，而当数量大于100时，运行时间增加为56.0ms；对于当前广度优先搜索算法，水果数量较少时，运行可以进行，但相较于贪心算法的运行时间，两者相差很大，如广度优先算法对于水果总数为5的运行时间为5.4s，而贪心算法只用0.7ms，这里不排除程序代码本身之间的优化问题所导致的差距。这里对两者之间算法背后的机理进行对比，对于贪心算法而言，总是选择当前离目标最近(最小代价)的节点进行扩展(搜索)局部最佳未必全局最佳—不是最优的，也就是选择可以消除水果的数量的直线进行扩展；而对于广度优先搜索，对于当前问题就是依次遍历所有直线，并依次检验扩展其后继节点。从算法而言，广度优先搜索更像是一种遍历模式，将所有可能进行了依次遍历，而贪心算法，存在一个约束，就是只对最优节点进行后继扩展。

A*算法（扩展）

A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。

A*算法需要维护两个数据结构：OPEN集和CLOSED集。OPEN集包含所有已搜索到的待检测节点。初始状态，OPEN集仅包含一个元素：开始节点。CLOSED集包含已检测的节点。初始状态，CLOSED集为空。每个节点还包含一个指向父节点的指针，以确定追踪关系。

A*算法会给每个搜索到的节点计算一个G+H的和值F：F=G+H

G：是从开始节点到当前节点的移动量。假设开始节点到相邻节点的移动量为1，该值会随着离开始点越来越远而增大。

H：是从当前节点到目标节点的移动量估算值。

算法有一个主循环，重复下面步骤直到到达目标节点：
每次从OPEN集中取一个最优节点n（即F值最小的节点）来检测。
将节点n从OPEN集中移除，然后添加到CLOSED集中。
如果n是目标节点，那么算法结束。
否则尝试添加节点n的所有邻节点n’。

邻节点在CLOSED集中，表示它已被检测过，则无需再添加。

邻节点在OPEN集中：

（1）如果重新计算的G值比邻节点保存的G值更小，则需要更新这个邻节点的G值和F值，以及父节点；

（2）否则不做操作；

否则将该邻节点加入OPEN集，设置其父节点为n，并设置它的G值和F值。

类比路径规划最短路径中使用A*方法的解决思路，在这里提出使用A*解决切水果问题的一般思路。当前切水果问题需要求得最少切水果次数。那么首先需要对F(n)=G(n)+H(n)，进行分别定义。在这里，节点定义为执行的直线动作，相较于最短路径问题，这里每个节点都互为邻节点；G定义为所执行直线切水果动作的次数累计值；H定义为执行至当前节点后水果剩余的数量。程序运行开始时，对水果合集进行直线构造，并记录每条直线下所遍历的水果位置；然后，将所有直线作为初节点放入OPEN合集中，对每个节点进行F值计算，并按照F值从大到小对节点进行排序，取出第一个节点放入CLOSED合集中，如果当前节点下水果剩余为0，则程序终止；否则，对OPEN合集中的所有节点进行更新，更新内容包括节点的F值，以及执行之前历史节点后，当前直线所遍历的水果位置，对OPEN合集继续按照F值从大到小排列，循环上述步骤，即取出第一个节点放入CLOSED合集中。循环操作，直至取出的节点下水果剩余为0。

python程序流程图

python源程序

import platform
import csv
import copy
import time



class Line_node:
    def __init__(self, node, fruit_remain, parent_node, G=0, H=0):
        self.parent_node = parent_node
        self.node = node
        self.fruit_remain = fruit_remain
        self.G = G
        self.H = H
        if node != None:
            self.line = self.node[0]  # 直线位置
            self.fruit_num = self.node[1]  # 直线上水果数量
            self.fruit_position = copy.deepcopy(self.node[2])  # 直线上水果坐标

    F = 0  # F=G+H

    def update_fruit(self):
        temp = []
        for i in self.fruit_position:
            if i in self.fruit_remain:
                continue
            else:
                temp.append(i)
        if len(temp) > 0:
            for m in temp:
                self.fruit_position.remove(m)
        self.fruit_num = len(self.fruit_position)

    def G_update(self):
        self.G = self.parent_node.G + 1  # 更新所执行至本节点的G值（切水果次数累计值）

    def H_update(self):
        self.H = len(self.fruit_remain) - len(self.fruit_position)

    def F_update(self):
        self.G_update()
        self.H_update()
        self.F = self.G + self.H

    def set_parent(self, parent):
        self.parent_node = parent

    def update(self, fruit_remain):
        self.fruit_remain = fruit_remain
        self.update_fruit()
        self.F_update()


class Astar:
    def __init__(self, Line_list, fruit_remain):
        self.line_list = Line_list
        self.fruit_remain = copy.deepcopy(fruit_remain)
        # 开放列表
        self.openList = []
        # 封闭列表
        self.closeList = []

    '''
    def sort_openList(self, arr):
        # 冒泡排序，按照F值从小到大
        if len(arr) <= 1:
            return
        i = 0
        # 外循环控制循环次数 每一次循环结束后，最大的数都会在后面
        while i < len(arr):
            j = 0
        # 内循环从0开始控制比较次数
        while j < len(arr) - 1 - i:
            # 比较 如果前一个数大于后一个数 则换位置
            if arr[j].F > arr[j + 1].F:
                temp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = temp
            j += 1
        i += 1
    '''

    def sort_openList(self):
        # 对openlist按照F值从小到大排序
        self.openList.sort(key=lambda x: x.F)

    def update_list(self, fruit_remain):
        for i in self.openList:
            i.update(fruit_remain)

    def start(self):
        parent_node = Line_node(None, None, None)
        Line_node_queue = [Line_node(i, self.fruit_remain, parent_node) for i in self.line_list]  # 创建直线 类队列
        self.openList = copy.deepcopy(Line_node_queue)  # 初始化将所有直线节点放入open列表中
        # 开始
        while len(self.fruit_remain) > 0:
            self.update_list(self.fruit_remain)
            self.sort_openList()
            Temp_node = self.openList.pop(0)  # 取出第一个节点
            for temp_position in Temp_node.fruit_position:
                self.fruit_remain.remove(temp_position)  # 对该直线下水果进行删除
            self.closeList.append(Temp_node)  # 放入close列表中
            if len(self.openList) > 0:
                for node in self.openList:
                    # 设置父节点
                    node.set_parent(Temp_node)


'''
从文件中读取水果数量和坐标
'''


def read_data(filename):
    f = open(filename + ".csv", 'r')
    reader = csv.reader(f)
    rows = [row for row in reader]
    data = [list(map(int, row)) for row in rows]
    n = data.pop(0)[0]  # 提取水果数量总数
    pos = copy.deepcopy(data)  # 水果位置list合集
    f.close()
    return [n, pos]


# 获取当前环境版本
print("当前环境python版本为" + platform.python_version())

File = "./fruit5"  # 默认读取的水果文件
Fnum = 0  # 水果数量初始化
F = []  # 水果位置合集
L = []  # 有水果的直线集合
rowth = 40
colth = 50

if (input("请选择数据输入方式：默认回车为从文件读取，任意输入非空字符后回车进入手动输入模式") == ""):
    [Fnum, F] = read_data(File)
else:
    Fnum = int(input('请输入整数水果数量N（0<N<=36）'))
    if (type(Fnum) != int):
        print('当前输入为非整数，请重新输入！')
    if (Fnum <= 0) or (Fnum > 36):
        print('输入整数超出范围(0~36)，请重新输入！')
    print('当前输入的水果数量为：' + str(Fnum))
    print('请依次输入水果的x,y坐标（每输入一个坐标，回车确认）')
    for i in range(Fnum):
        x, y = map(int, input('输入第' + str(i + 1) + '个水果坐标，共' + str(Fnum) + '个水果' + '(x,y空格隔开):').split())
        F.append([x, y])

time_start = time.time()  # 记录开始时间
# time_start = time.perf_counter()  # 记录开始时间
# create search space(遍历水果，将所有有水果的直线列出，构成搜索空间）
for x in F:
    # row line横线记录
    m = "r" + str(x[0])
    templinename = []
    templinename.append(m)
    flag = True
    for y in L:  # 去重复直线
        if templinename[0] == y[0]:
            flag = False
    if flag:
        col = 0
        cellset = []
        num = 0
        while col < colth:
            cell = [x[0], col]
            if cell in F:
                cellset.append(cell)
                num = num + 1
            col = col + 1
        templinename.append(num)
        templinename.append(cellset)
        L.append(templinename)

    # column line
    m = "c" + str(x[1])
    templinename = []
    templinename.append(m)
    flag = True
    for y in L:
        if templinename[0] == y[0]:
            flag = False
    if flag:
        row = 0
        cellset = []
        num = 0
        while row < rowth:
            cell = [row, x[1]]
            if cell in F:
                cellset.append(cell)
                num = num + 1
            row = row + 1
        templinename.append(num)
        templinename.append(cellset)
        L.append(templinename)

        # LD
        row1 = x[0]
        col1 = x[1]
        while row1 >= 0 and col1 >= 0:
            row1 = row1 - 1
            col1 = col1 - 1
        if row1 < 0 or col1 < 0:
            m = "LD" + str(row1 + 1) + ":" + str(col1 + 1)
        templinename = []
        templinename.append(m)
        flag = True
        for y in L:
            if templinename[0] == y[0]:
                flag = False
        if flag:
            row = row1 + 1
            col = col1 + 1
            cellset = []
            num = 0
            while row < rowth and col < colth:
                cell = [row, col]
                if cell in F:
                    cellset.append(cell)
                    num = num + 1
                row = row + 1
                col = col + 1
            templinename.append(num)
            templinename.append(cellset)
            L.append(templinename)
        # RD
        row1 = x[0]
        col1 = x[1]
        while row1 >= 0 and col1 < colth:
            row1 = row1 - 1
            col1 = col1 + 1
        if row1 < 0 or col1 >= colth:
            m = "RD" + str(row1 + 1) + ":" + str(col1 - 1)
        templinename = []
        templinename.append(m)
        flag = True
        for y in L:
            if templinename[0] == y[0]:
                flag = False
        if flag:
            row = row1 + 1
            col = col1 - 1
            cellset = []
            num = 0
            while row < rowth and col >= 0:
                cell = [row, col]
                if cell in F:
                    cellset.append(cell)
                    num = num + 1
                row = row + 1
                col = col - 1
            templinename.append(num)
            templinename.append(cellset)
            L.append(templinename)
print("直线坐标: ", end="")
print(L)

# main

A_star = Astar(L, F)
A_star.start()
time_end = time.time()  # 记录结束时间
# time_end = time.perf_counter()  # 记录结束时间
for i in A_star.closeList:
    print(i.line)
time_sum = time_end - time_start  # 计算的时间差为程序的执行时间，单位为秒/s 如果当前输出运行时间为0，请改用time.perf_counter()
print("运行时间" + str(time_sum) + "s")
print('共切次数' + str(len(A_star.closeList)))

程序运行说明

按照A*算法思路所编写的程序，在相同的水果数据合集下，表现出比贪心算法更快的求解速度，如A*搜索程序运行结果表所示。可以看到相较于贪心算法运行结果表，在大水果数据下，运行时间约1.14s远大于贪心算法18.25s，但在少量水果数据集合下，没有更大的优势。

A*搜索程序运行结果表，

水果总数	运行时间/s	切水果次数
5	0.001001	5
10	0.002021	7
20	0.004984	13
50	0.014016	24
100	0.03195	37
1000	0.548677	40
1500	1.135173	40

目前，关于贪心算法和A*搜索算法之间，在水果总是为50和100时，运行结果存在不一致的问题，这个我经过调试，暂时还未找到问题所在。

最少次数切水果问题

最少次数切水果问题

问题描述

贪心算法（贪婪最佳优先搜索）

解决思路

python程序流程图

程序演示

python源程序

广度优先搜索算法

解决思路

python程序流程图

程序演示

python源程序

算法对比（时间复杂度）

A*算法（扩展）

python程序流程图

python源程序

程序运行说明

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

最少次数切水果问题

最少次数切水果问题

问题描述

贪心算法（贪婪最佳优先搜索）

解决思路

python程序流程图

程序演示

python源程序

广度优先搜索算法

解决思路

python程序流程图

程序演示

python源程序

算法对比（时间复杂度）

A*算法（扩展）

python程序流程图

python源程序

程序运行说明

热门文章

最新文章

相关电子书