@Reference: Jack Cui | Github-Markov Junior | Wiki Markov algorithm 第一篇文章简要介绍了一下该编程语言能实现什么效果；第二个是官方repo，其文档和代码都有很强的借鉴意义；第三个是wikipedia对马尔可夫算法的解释，在该编程语言的实现中有重要的意义。 markov algorithm 马尔可夫算法指的是字符串重写算法，其基本逻辑如下: 自顶向下依次检查规则，看是否能在符号串中找到任何在箭头左边的字符串。 如果没有找到，停止执行算法。 如果找到一个或多个，把符号串中的最左匹配的文字替换为在第一个相应规则的箭头右边的字符串。 返回步骤1并继续。（如果应用的规则是终止规则，则停止执行算法。） [1] MarkovJunior Markov Junior是一种基于概率的编程语言，通过重写和传播规则（约束）来实现随机的生成和编写。最终对画布进行重写来实现随机的生成。 ...
@Reference: Github-Mxgmn | zhihu 概念简介和复习 本质上该方法的底层思想就是条件概率的启发式随机生成算法。 波函数坍塌 在介绍算法之前首先需要明确几个概念，第一个就是**“波函数坍塌”（名字的来源是量子力学中的概念），参考“薛定谔的猫”，可以理解成：在一系列的不确定像素（存在多种可能）的基础之上，通过确定的规则**、相关关系，随机的将所有的像素变成确定的状态。（可以通过给定种子来启动，也可以通过随机规则来启动），实现在一定规则或者模式下的随机生成。 熵 熵作为热力学中，表示物理状态的参量，其含义在于表示物质的混乱程度（正相关）。在当前的场景下，使用信息熵（而非热熵）来衡量变量的不确定程度（完全随机，或者有限随机，或者二选一等等）。 $$ H(X) = \sum_{x\in X}p(x)log p(x) $$ 式中描述的是信息熵的计算公式，在实际应用中，可以使用任何表示状态不确定程度的度量来进行一下的计算。 算法原理-流程 动态地使可选的范围越来越小，直到最后整体都是确定的状态。而缩小范围的方法核心可以总结为（数独）： 约束规则、状态传播、回溯 从最小熵的单位开始坍缩，保证最小概率的坍缩失败，从而减少大量的回溯过程，来减少计算量。 以地图生成为例： 约束规则：（选择一个熵最小的slot开始）针对于每个slot的坍缩，是在ModuleSet（可选模块集合）中随机取一个概率最高的模块，进行合成，而这个概率受我们制定的规则，周边的Slot的状态影响。 状态传播：模块确定后就将该状态和规则传递到相邻的moduleset中，删除不匹配的模块等。 回溯：当坍缩陷入矛盾（与规则相互矛盾，坍缩失效），就对状态进行回溯（Backtrack）重新进行状态搜索和回溯。 Read the input bitmap and count NxN patterns. (optional) Augment pattern data with rotations and reflections. Create an array with the dimensions of the output (called “wave” in the source). Each element of this array represents a state of an NxN region in the output. A state of an NxN region is a superposition of NxN patterns of the input with boolean coefficients (so a state of a pixel in the output is a superposition of input colors with real coefficients). False coefficient means that the corresponding pattern is forbidden, true coefficient means that the corresponding pattern is not yet forbidden. Initialize the wave in the completely unobserved state, i.e. with all the boolean coefficients being true. Repeat the following steps: Observation: Find a wave element with the minimal nonzero entropy. If there is no such elements (if all elements have zero or undefined entropy) then break the cycle (4) and go to step (5). Collapse this element into a definite state according to its coefficients and the distribution of NxN patterns in the input. Propagation: propagate information gained on the previous observation step. By now all the wave elements are either in a completely observed state (all the coefficients except one being zero) or in the contradictory state (all the coefficients being zero). In the first case return the output. In the second case finish the work without returning anything. Code 官方仓库中有诸多样例和各种代码版本的实现，可以参考并实现部分版本。 ...
记录各种排序操作，暂时不补充最基础的排序方式和理论，只记录排序算法的拓展应用。 在理论分析的部分主要使用cpp进行撰写，而在具体使用的时候，目前会主要按照python来进行编写，这主要是面向的场景不同决定的。 基础的排序理论，包括快排等等算法的分析在另一篇文章中记录（当初实习准备的时候有整理过，后续重新整理出来） 排序算法和理论 placeholder 排序算法应用 placeholder 同步排序 常用于Machine Learning中，将数据集中的数据和标签进行同步排序，避免打乱其中的对应关系。 使用numpy的 argsort功能来进行排序： python idx = np.argsort(labels) labels = labels[idx] datas = datas[idx,...] 使用sort中的args: key来进行同步排序，选出一个作为依据, 但是这种方式不支持存在np的情况，因为np无法建立hash，除非我们转化成tuple再转回来。 python # 默认按照第0维度进行排序 lables, datas = [list(x) for x in zip(*sorted(zip(labels, datas)))] # 若要指定特定维度 from operator import itemgetter datas, labels = [list(x) for x in zip(*sorted(zip(datas, labels), key=itemgetter(1)))] 额外介绍我的愚蠢实现思路： ...
A* 是一种在平面图形上计算最优路径的方法，通常用来做 2D 游戏的最短寻路，该算法是一种 Dijkstra 算法的变体，使用启发式的策略来提高算法的搜索效率。 wikipedia ；medium ；pythonf 基本思想 基于启发式的方法，基于BFS去做最短路径搜索，借助类似Manhattan距离作为启发，每次加入后续的多个点，然后按照后续点的属性去排序，不断的加入close的区间，直到第一次遍历到终点就是最短的路径。 $$ f(n) = g(n) + h(n) $$ f代表的是经过当前点，从起点到最终点的距离，g代表的是从起点到当前节点的距离，h代表的是启发式方法到终点的距离。 维护三个list：open(候选列表)、close（状态确定的列表）、children（等待操作的列表） 首先用 bfs 的方法，找到当前节点的可达后续节点，将这些节点加入 children，确定 child 不在 close_list 中后（即在 open 中）则判断哪个是最优解，然后更新 openlist 和 closelist 。 即：每次遍历的当前节点都从 open 中总距离最小的选，然后放入 close。直到 openlist 为空。 相关类别定义 python class node(): def __init__(self, parent=None, position=None): self.parent = parent self.position = position self.g = 0 self.h = 0 self.f = 0 def __eq__(self, o: object) -> bool: return o.position == self.position 具体代码实现 python def asterS(map,slope,start,end): # 在astar算法的基础上，我们需要加入的是高度的约束 # 阻碍的条件是高度不同同时没有slope的存在，这种就是wall # 其余的和Astar算法应该是一样的 # init the start and end node start_node = node(None,start) end_node = node(None,end) # init the open and closed lists open_list = [] close_list = [] # add the start node to the open list open_list.append(start_node) # loop util find the end_node while len(open_list)>0: # make the best node as current_node # init 1 current_node = open_list[0] current_index = 0 for index, nod in enumerate(open_list): if nod.f<current_node.f: current_node = nod current_index = index # pop the curr node off open list, add to close list open_list.pop(current_index) close_list.append(current_node) # terminal conditions (reach the end node ) if current_node == end_node: path = [] while(current_node is not None): path.append(current_node.position) current_node = current_node.parent # return the path we find. return path[::-1] # the body of the loop: update the nodes # find the available children nodes children = [] # define the adjacent squares positions = [(-1,0),(1,0),(0,-1),(0,1)] for pos in positions: # get childrens positions node_pos = (current_node.position[0]+pos[0], current_node.position[1]+pos[1]) # make sure within range if node_pos[0] < 0 or node_pos[0] >= map.shape[0] or node_pos[1] < 0 or node_pos[1] >= map.shape[1]: continue # mkae sure walkab mapflag = map[current_node.position[0], current_node.position[1]] != map[node_pos[0], node_pos[1]] slopeflag1 = slope[node_pos[0], node_pos[1]] == 0 or slope[current_node.position[0], current_node.position[1]] == 0 slpopeflag2 = slope[node_pos[0], node_pos[1]] != slope[current_node.position[0], current_node.position[1]] if mapflag and (slopeflag1 or slpopeflag2): continue # we need creat node first to find out if it is in the openlist or closed list new_node = node(current_node, node_pos) children.append(new_node) # loop those children # using the __eq__ to judge if it's already traveled. for child in children: if child in close_list: continue # create f,g,h for the legal child child.g = current_node.g + 1 child.h = manhattan(child.position, end_node.position) child.f = child.g + child.f # if the child is already in the open list, compare it if child in open_list: open_index = open_list.index(child) open_node = open_list[open_index] if child.g > open_node.g: continue open_list.pop(open_index) # if it is not in the open/closelist or better than that in open list, we add it. open_list.append(child)
